[자료구조]큐 Queue [C++]

큐(Queue)의 개념

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 구조(FIFO)로 저장하는 형식을 말한다.

 

큐(Queue)의 기본 구조

 

 

그림과 같이 Enqueue하면 데이터가 큐 리스트안에 삽입되고, Dequeue하면 데이터가 큐 리스트에서 삭제된다.

 

 

큐(Queue)의 구현

#include <iostream>

using namespace std;

#define SIZE 10

int list[SIZE];
int front = 0;
int rear = 0;

void Enqueue(int);
int Dequeue();

int main()
{
	cout << "(1) Enqueue. (2) Dequeue (3) Print (4) Exit" << endl;
	int menu;
	cin >> menu;

	while (menu != 4)
	{
		switch (menu)
		{
		case 1:
		{
			int temp;
			cout << "Enter a enqueue value:";
			cin >> temp;

			Enqueue(temp);
		}
		break;
		case 2:
		{
			cout << Dequeue() << "is dequeued" << endl;
		}
		break;
		case 3:
		{
			for (int i = front; i < rear; i++)
			{
				cout << "[" << i + 1 << "]" << list[i] << " ";
			}
			cout << endl;
		}
		break;
		default:
			cout << "Wrong Input!" << endl;
		}

		cout << "(1) Enqueue. (2) Dequeue (3) Print (4) Exit" << endl;
		cin >> menu;
	}



}

void Enqueue(int val)
{
	if (rear > SIZE - 1)
		return;

	list[rear++] = val;
}

int Dequeue()
{
	if (rear < front)
		return -1;

	return list[front++];
}

큐(Queue)의 문제점

배열로 구현하게 되면 front rear가 각각 밀려남에 따라 앞부분은 사용하지 못하게 된다. 즉 메모리 낭비가 생긴다는 것이다. 이를 해결하기 위한 방법이 있는데, 링크드리스트와 원형큐(Circular Queue) 이다. 원형 큐는 따로 만들어 업로드 할 예정이니 링크드리스트 구현을 해보도록 하겠다.

 

큐(Queue)의 링크드리스트 구현

#include <iostream>
#include <stdlib.h>

typedef struct node
{
	int val;
	node* next;
}NODE;

typedef struct
{
	NODE * front;
	NODE * rear;
}QUEUE;

void EnQueue(QUEUE * queue, int val);
int DeQueue(QUEUE * queue);
int Queue_Empty(QUEUE * queue);
int Queue_Full(QUEUE * queue);
void Print(QUEUE* queue);

using namespace std;

int main()
{
	QUEUE * queue = (QUEUE*)malloc(sizeof(QUEUE));
	queue->front = queue->rear = NULL;

	while (1)
	{
		int n;
		cout << "Enqueue(1)  Dequeue(2)  print(3) exit(4): ";

		cin >> n;

		switch (n)
		{
		case 1:
		{
			if (Queue_Full(queue))
			{
				cout << "Stack is Full";
				break;
			}
			int temp;
			cout << "Enter a integer please: ";
			cin >> temp;
			EnQueue(queue, temp);
		}
		break;
		case 2:
		{
			if (Queue_Empty(queue))
			{
				cout << "Stack is Empty";
				break;
			}
			int temp = DeQueue(queue);
			cout << temp << "is deleted";
		}
		break;
		case 3:
		{
			if (Queue_Empty(queue))
			{
				cout << "Queue is empty";
				break;
			}
			Print(queue);
		}
		break;
		case 4:
		{
			return 0;
		}
		default:
			cout << "error";
			break;
		}
		cout << endl;
	}

	return 0;
}

void EnQueue(QUEUE * queue, int val)
{
	NODE * newNode = (NODE*)malloc(sizeof(NODE));
	newNode->val = val;
	newNode->next = NULL;

	if ((queue->front == NULL) && (queue->rear == NULL))
	{
		queue->front = queue->rear = newNode;
	}
	else
	{
		queue->rear->next = newNode;
		queue->rear = newNode;
	}
}

int DeQueue(QUEUE * queue)
{
	NODE * temp = queue->front;
	queue->front = queue->front->next;

	int fValue = temp->val;
	free(temp);

	return fValue;
}

int Queue_Empty(QUEUE * queue)
{
	return queue->front == NULL || queue->rear == NULL;
}

int Queue_Full(QUEUE * queue)
{
	QUEUE *test = (QUEUE *)malloc(sizeof(QUEUE));
	if (test == NULL)
		return 1;
	else
	{
		free(test);
		return 0;
	}
}

void Print(QUEUE * queue)
{
	NODE * nNode = queue->front;
	while (nNode != NULL)
	{
		printf("%d ", nNode->val);
		nNode = nNode->next;
	}
}