[자료구조] C++로 쉽게 풀어쓴 자료구조 : 4장, Queue

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 4장. queue. deque

 

Queue의 ADT

데이터: 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모음

 

연산:

- enqueue(e): 주어진 요소 e를 큐의 맨 뒤에 추가한다.

- dequeue(): 큐가 비어 있지 않으면 맨 앞 요소를 삭제하고 반환한다.

- isEmpty(): queue가 비어있는지의 유무를 bool값으로 반환

- isFull(): queue가 가득 차있는지의 유무를 bool값으로 반환

- peek(): queue가 비어있지 않으면 맨 앞의 요소를 확인해본다.

- size(): queue의 모든 요소들의 개수를 반환

- display(): queue 내의 모든 요소를 출력

 

원형 큐의 구현

template화 시킨 코드로 교제내용 변경

 

CircularQueue.h

#pragma once
#include <iostream>
#include <cstdio>
#include <cstdlib>

const int MAX_QUEUE_SIZE = 100;

inline void error(const char* message) {
	printf("%s\n", message);
	exit(1);
}

template <typename T>
class CircularQueue {
protected:
	int _front;
	int _rear;
	T data[MAX_QUEUE_SIZE];
public:
	CircularQueue() : _front(0), _rear(0) {}
	void enqueue(const T& value);
	T dequeue();
	T peek();
	void display();
	bool isEmpty() { return _front == _rear; }
	bool isFull() { return (_rear + 1) % MAX_QUEUE_SIZE == _front; }
};

template <typename T>
void CircularQueue<T>::enqueue(const T& value) {
	if (isFull()) error("큐가 가득참!\n");
	else {
		_rear = (_rear + 1) % MAX_QUEUE_SIZE;
		data[_rear] = value;
	}
}

template <typename T>
T CircularQueue<T>::dequeue() {
	if (isEmpty()) error("큐가 비어있음!\n");
	else {
		_front = (_front + 1) % MAX_QUEUE_SIZE;
		return data[_front];
	}
}

template <typename T>
T CircularQueue<T>::peek() {
	if (isEmpty()) error("큐가 비어있음!\n");
	else {
		return data[(_front + 1) % MAX_QUEUE_SIZE];
	}
}

template <typename T>
void CircularQueue<T>::display() {
	std::cout << "[queue]: ";
	int max = (_front < _rear) ? _rear : _rear + MAX_QUEUE_SIZE;
	for (int i = _front + 1; i < max; i++)
	{
		std::cout << data[i] << " ";
	}
	std::cout << std::endl;
}

 

 

main.cpp

#include "CircularQueue.h"
using namespace std;

int main()
{
	CircularQueue<double> q;
	for (double i = 0.5; i < 15; i++)
		q.enqueue(i);
	q.display();

	q.dequeue();
	q.dequeue();
	q.dequeue();
	q.dequeue();

	q.display();

	return 0;
}

 

결과는 다음과 같다.

 

Deque의 ADT

deque(덱) 은 double-ended queue의 줄임말로써 queue의 앞, 뒤 모두에서 삽입과 삭제가 가능한 큐를 말한다.

 

데이터: 전단과 후단을 통한 접근을 허용하는 요소들의 모음

 

연산:

- addFront(e): 인자로 넘겨받은 e를 deque의 맨 앞에 추가.

- deleteFront(): deque이 비어있지 않다면 맨 앞 요소를 삭제후 반환.

- addRear(e): 주어진 요소 e를 deque의 맨 뒤에 추가.

- deleteRear(): deque이 비어있지 않다면 맨 뒤 요소를 삭제후 반환.

- isEmpty(): deque이 비어있는지의 유무를 bool값으로 반환

- isFull(): deque이 가득 차있는지의 유무를 bool값으로 반환

- getFront(): deque이 비어있지 않다면 맨 앞 요소를 반환

- getRear(): deque이 비어있지 않다면 맨 뒤 요소를 반환

- display(): deque의 모든요소 출력

 

덱은 위에서 사용한 원형큐(CircularQueue.h)를 상속받아서 원형덱을 구현하면된다!

CircularQueue.h 에서 이미 addRear, deleteFront, getFront는 구현해논것이다. 따라서 나머지 deleteRear, addFront, getRear 연산만 추가해주면 된다.

 

교제에서는 int형만을 사용하지만 저의 코드는 template화 시킨 코드입니다.

CircularQueue.h

#pragma once
#include "CircularQueue.h"

template <typename U>
class CircularDeque : public CircularQueue<U> {
public:
	CircularDeque() : CircularQueue<U>() {}
	void addRear(U value) { CircularQueue<U>::enqueue(value); }
	U deleteFront() { return CircularQueue<U>::dequeue(); }
	U getFront() { return CircularQueue<U>::peek(); }

	void addFront(const U& value);
	U deleteRear();
	U getRear();
	void display();
};

template <typename U>
void CircularDeque<U>::addFront(const U& value) {
	if(CircularQueue<U>::isFull()) error("덱이 가득참!\n");
	else {
		CircularQueue<U>::data[CircularQueue<U>::_front] = value;
		CircularQueue<U>::_front = (CircularQueue<U>::_front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	}
}

template <typename U>
U CircularDeque<U>::deleteRear() {
	if (CircularQueue<U>::isEmpty()) error("덱이 비어있음!\n");
	else {
		int temp = CircularQueue<U>::data[CircularQueue<U>::_rear];
		CircularQueue<U>::_rear = (CircularQueue<U>::_rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
		return temp;
	}
}

template <typename U>
U CircularDeque<U>::getRear() {
	if (CircularQueue<U>::isEmpty()) error("덱이 비어있음!\n");
	else return CircularQueue<U>::data[CircularQueue<U>::_rear];
}

template <typename U>
void CircularDeque<U>::display() {
	std::cout << "[deque]: ";
	int max = (CircularQueue<U>::_front < CircularQueue<U>::_rear) ? CircularQueue<U>::_rear : CircularQueue<U>::_rear + MAX_QUEUE_SIZE;
	for (int i = CircularQueue<U>::_front + 1; i <= max; i++)
		std::cout << CircularQueue<U>::data[i% MAX_QUEUE_SIZE] << " ";
	std::cout << std::endl;
}

 

 

main.cpp

#include "CircularDeque.h"
using namespace std;

int main()
{
	CircularDeque<int> deq;
	for (int i = 1; i < 10; i++)
	{
		if (i % 2) deq.addFront(i);
		else deq.addRear(i);
	}
	deq.display();

	deq.deleteFront();
	deq.deleteRear();
	deq.deleteFront();

	deq.display();

	return 0;
}

 

결과는 다음과 같다.

DFS(Depth First Search)

스택을 사용하는 것 은 그래프의 여러가지 탐색 기법들 중에서 깊이 우선 탐색(DFS) 전략을 사용하는 것 이다. 이 방식은 일단 최대한 도달할 수 있는곳 까지 가보고 막히면 다시 다른 길을 찾는 방식이다.

 

BFS(Breadth First Search)

미로 탐색 문제는 큐를 이용해서도 풀수있다. 이 방식은 그래프 탐색에서 너비우선탐색(BFS) 전략을 사용하는 것 으로, 탐색의 순서에서 깊이보다는 폭을 우선으로 취한다.

---

2) 나의 현황

● 흠 4장에서 은행 시뮬레이션 문제가있었는데 설명이 너무 빈약하다. 이런 문제는 그냥 차라리 빼고 좀더 간결한 문제를 첨부해줬으면 하는 소망이 있다. 아니면 최소한 sudo코드로 알고리즘을 한번 설명해줬어야 왜 이런식으로코드를 짰는지 이해할수 있는데, 이번 문제는 그냥 코드 한행한행 원리만 설명했지 왜 그런 흐름으로 가는지는 전달하지 못한것 같다.

​

이글의 모든 사진과 내용의 출처는 천인국, 최영규 님께 있습니다.