[C++] 자료구조 : 큐 정리

아래 내용들은 'c++로 쉽게 풀어쓴 자료구조 (천인국,최영규)' 책을 읽으며 개인적으로 공부하며 정리한 것입니다.

잘못된 점이 있으면 고치겠습니다.

Chapter03

 

Queue (큐)

Queue (큐)
: 선입선출(FIFO : first in first out) 의 접근 방법을 유지하는 요소들의 모음

기능

• enqueue(e) : 주어진 요소 e를 큐의 맨 위에 추가한다.
• dequeue() : 큐가 비어있지 않으면 맨 앞 요소를 삭제하고 반환한다
• isEmpty() : 큐가 비어있으면 true를 아니면 false를 반환한다
• peek() : 큐가 비어있지 않으면 맨 앞에 있는 요소를 삭제하지 않고 반환한다
• ifFull() : 큐가  가득 차 있으면 true를 아니면 false를 반환한다
• size() : 큐 내의 모든 요소들의 개수를 반환한다
• display() : 큐가 내의 모든 요소들을 출력한다

스택에서는 top으로 불리는 변수 하나만을 이용하여 삽입, 삭제 연산의 위치를 알 수 있었지만,

큐에서는 삽입과 삭제가 후단(rear)와 전단(front)에서 각각 독립적으로 이루어지므로 양쪽의 위치를 기억해야 하고, 따라서 두 개의 변수가 필요하다.

활용 예

• 키보드와 컴퓨터 사이에 큐(입력 버퍼)가 필요하다.
• 컴퓨터와 프린터 사이에도 인쇄 작업 큐가 존재.

큐의 종류

• 선형 큐
  • front : 큐의 첫 번째 요소를 가리키고
  • rear : 큐의 마지막 요소를 가리킴
  • front와 rear의 값이 계속 증가하여, 언젠가는 배열의 끝에 도달하고, 앞부분이 비어있어도 더 이상 삽입하지 못함 -> 문제점
• 원형 큐
  • 선형 큐의 문제점을 보완 => front, rear 의 값이 배열의 끝인 MAX_SIZE_QUEUE - 1 에 도달하면 다음에 증가되는 값은 0이 되도록 함. (실제 원형 X , 개념상 원형으로 배열의 인덱스 변화시킴)
  • front : 큐의 첫 번째 요소의 하나 앞
  • rear : 마지막 요소
  • front = rear (front 와 rear 의 값이 같으면) 공백상태

원형 큐의 공백 상태와 포화 상태 및 오류 상태 ( 오류 상태 : 원형 큐에서 한 자리는 항상 비워두는데 이를 비워두지 않을 경우 )

 

원형 큐 구현 

원형 큐의 다이어그램

//1CircularQueue.h

#include <iostream>
#define MAX_QUEUE_SIZE 100
using namespace std;

class CircularQueue {
protected:
	int front, rear;
	// front : 큐의 첫 번째 요소의 하나 앞
	// rear : 큐의 마지막 요소
	int data[MAX_QUEUE_SIZE];
public:
	CircularQueue() { front = rear = 0; }
	bool isEmpty() { return front == rear; }
	bool isFull() { return (rear + 1) % MAX_QUEUE_SIZE == front; }
	void enqueue(int val)
	{
		if (!isFull())
		{
			rear = (rear + 1) % MAX_QUEUE_SIZE;
			data[rear] = val;
		}
	}
	int dequeue() { // 첫 항목을 queue에서 빼서 반환
		if (!isEmpty())
		{
			front = (front + 1) % MAX_QUEUE_SIZE;
			return data[front];
		}
	}
	int peek() // 첫 항목을 단순 반환
	{
		if (!isEmpty())
		{
			return data[(front + 1) % MAX_QUEUE_SIZE];
		}
	}
	void display()
	{
		cout << "[큐 요소 출력]" << "\n";
		int max = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
		for (int i = front + 1 ; i <= max; i++)
		{
			cout << "[" << i << "]번째 요소: " << data[i % MAX_QUEUE_SIZE]<<"\n";
		}
	}


};

//2CircularQueueTest.cpp

#include "1CircularQueue.h"

void main() {
	CircularQueue s;
	for (int i = 1; i < 10; i++)
	{
		s.enqueue(i);
	}
	s.display();
	s.dequeue();
	s.dequeue();
	s.dequeue();
	s.dequeue();
	s.display();

	return;
}