알고리즘 : 자료구조(2) 큐 (Queue) (C++로 구현)

큐 (Queue)

큐(queue)는 스택(stack)과 다르게 FIFO(First In First Out-선입선출)의 구조를 가지고 있다. 편의점 아르바이트를 해보신 분들은 특히 잘 아시겠지만 가장 먼저 들어온 것을 가장 앞에 배치하여 가장 먼저 나갈 수 있도록 하는 것이다.

은행의 번호표를 생각해보자. 100번째 번호표를 뽑은 상태이고 현재 손님이 많이 몰린 탓이 96번째 손님까지 서비스를 받고 있다. 그렇다면 다음 손님의 번호와 새로온 손님의 번호를 기억하기 위해서는 어떻게 해야할까? 바로 큐를 이용하면 된다.

Enqueue : 큐 맨 뒤에 요소 추가
Dequeue : 큐 맨 앞에 요소 삭제
Peek : front에 위치한 데이터 (가장 일찍 들어온 요소)
Front : 맨 앞의 위치
Rear : 맨 뒤의 위치

큐의 기본 용어는 이와 같다.

 

class Queue {
private:
	int size = 100;
	int* queue;
	int front = -1;
	int rear = -1;
	int top = -1;
public:
	Queue();
	~Queue();
	void enqueue(int element);
	void dequeue();
	void show_queue();
};

Queue::Queue() {
	queue = new int[size];
}

Queue::~Queue() {
	delete[] queue;
}

배열을 이용해 queue를 구현하도록 하겠다. c++로 함수를 차근차근 작성해보았다.

 

 

1. Enequeue & Dequeue

void Queue::enqueue(int element) {
	if (rear == size - 1) 
		cout << "Queue Overflow" << endl;
	else {
		if (front == -1)
			front = 0;
		cout << "Insert the element in queue: " << element << "\n";
		queue[++rear] = element;
	}
}

void Queue::dequeue() {
	if (front == -1 || front > rear)
		cout << "Queue is empty\n";
	else
		cout << "Element deleted from queue is : " << queue[front++] << "\n";

 

2. Show Queue

void Queue::show_queue() {
	if (front == -1) 
		cout << "Queue is empty" << endl;
	else {
		cout << "Queue elements are : ";
		for (int i = front; i <= rear; i++) cout << queue[i] << " ";
		cout << endl;
	}
}

 

 

3. 최종 코드

int main() {
	Queue q;
	int ch = 0, val;
	cout << "1) Insert element to queue" << endl;
	cout << "2) Delete element from queue" << endl;
	cout << "3) Display all the elements of queue" << endl;
	cout << "4) Exit\n";
	while (ch != 4) {
		cout << "Enter your choice : ";
		cin >> ch;
		switch (ch) {
		case 1: {
			cout << "Enter value to be pushed: ";
			cin >> val;
			q.enqueue(val);
			break;
		}
		case 2: {
			q.dequeue();
			break;
		}
		case 3: {
			q.show_queue();
			break;
		}
		case 4: cout << "Exit" << endl;
			break;
		default: cout << "Invalid choice" << endl;
		}
	}
	return 0;
}

간단하게 구현을 해보았다.

 

 

4. STL을 이용한  Queue 구현

#include <queue> 
queue<int> q;

c++ STL을 이용해서 Queue을 구현할 수도 있다.

 

q.push(element); // back 데이터추가
q.pop(); // front 데이터삭제
q.front(); // front 데이터 반환
q.back(); // back 데이터 반환
q.size(); // 큐 현재 사이즈 반환
q.empty(); 큐 비어있는지 확인
swap(queue1, queue2); // 큐 1과 큐 2의 내용 바꾸기

이러한 함수를 사용할 수 있다.

 

이 자료구조는 그래프와 BFS에서 집중적으로 다루게 될 것이다.

 

https://velog.io/@kon6443/Data-Structure-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-C-%EC%8A%A4%ED%83%9D-%ED%81%90

[Data Structure] 자료구조 / C++ / 스택 / 큐

위 티스토리를 참고하였다.

 

활용

BFS 알고리즘