자료구조 만들기 #2 큐(Queue)

큐는 스택과 더불어 가장 많이 쓰이는 자료 입출력 구조이다. 스택(Stack)이 후입선출(LIFO)방식이었다면, 큐(Queue)는 선입선출(FIFO)의 구조로 입장순서에 대한 개념과 같다. 운영체제 입장에서도 중요한데 특별한 이유(Exception/우선 처리 지시 등의 예외사항)가 아니라면 무조건 먼저 들어온 프로세스를 먼저 처리하는 과정으로 동작하기 때문에 중요하다.

기본적으로 사용하는 형식은 스택을 구현했을 때와 유사하게 사용하지만, 다른점은 스택을 사용했을 때와 달리 큐를 구현할때는 마지막 노드(tail==stack의 top)와 마찬가지로 첫번째 노드 (Head)에 대한 정보가 중요하다는 것이다.

Queue.c

/**
* 큐 자료구조 구현하기
* // 단일연결리스트
* using struct
* 
*/
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Node {
	struct Node* next;
	char* data;
} Node;

typedef struct Queue {
	Node* front;	//헤드
	Node* rear;		//테일
} Queue;

void menu(int n);
bool isEmpty();
int enQueue();
int deQueue();
int search();
void printQueue();
void freeQueue();

Queue queue;

int main() {	
	queue.front = NULL;
	queue.rear = NULL;
	while (1)
	{
		int input;
		printf("1 : enQueue, 2 : deQueue, 3 : search data, 4 : print Queue, 0 : 프로그램 종료\n");
		scanf("%d", &input);
		menu(input);
	}

	return 0;
}

// 명령어 입력기
void menu(int n) {
	getchar();
	if (n == 0)
	{
		freeQueue();
		printf("프로그램을 종료합니다.\n");
		exit(0);
	}
	else if (n == 1)
	{
		enQueue();
	}
	else if (n == 2)
	{
		deQueue();
	}
	else if (n == 3)
	{
		search();
	}
	else if (n == 4)
	{
		printQueue();
	}
	else
	{
		printf("잘못된 입력입니다. 다시 입력해주세요.\n");
	}
}

bool isEmpty()
{
	if(queue.front == NULL)
	{
		printf("스택이 비어있습니다.\n");
		return true;	// return 1;
	}
	return false;		// return 0
}

int enQueue()
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	char src[256];
	printf("저장할 단어를 입력해주세요. 단어의 길이는 최대 255입니다.\n");
	fgets(src, 256, stdin);
	src[strcspn(src, "\n")] = 0;
	newNode->data = _strdup(src);
	newNode->next = NULL;

	if (queue.front == NULL)
	{
		printf("첫번째 데이터를 입력합니다.\n");
		queue.front = queue.rear = newNode;
	}
	else
	{
		queue.rear->next = newNode;
		queue.rear = newNode;
	}
	return 0;
}

int deQueue()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return 0;
	}
	Node* temp = queue.front;		//첫번째 노드 뽑아내기
	queue.front = queue.front->next; // 다음 노드 가져오기
	if (queue.front == NULL) // 큐가 모두 비워졌음을 의미한다.
	{
		queue.rear == NULL; 
	}
	printf("제거된 단어 : %s\n", temp->data);
	free(temp->data);
	free(temp);
	return 1;
}

int search()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	char src[256];
	printf("찾고싶은 단어를 입력해주세요. 단어의 길이는 최대 255입니다.\n");
	fgets(src, 256, stdin);
	src[strcspn(src, "\n")] = 0;
	Node* temp = queue.front;
	int i = 0;
	while (temp != NULL)
	{
		++i;
		if (strcmp(src, temp->data) == 0)
		{
			printf("%s의 위치는 %d입니다.\n", src, i);
			return 1;
		}
		temp = temp->next;
	}
	printf("찾으시는 단어는 스택에 없습니다.\n");
	return 1;
}

void printQueue()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	Node* temp = queue.front;
	int i = 0;
	while (temp != NULL)
	{
		++i;
		printf("큐의 위치 : %d, 저장된 단어 : %s\n", i, temp->data);
		temp = temp->next;
	}
}

void freeQueue()
{
	while (!isEmpty())
	{
		deQueue();
	}
}

Queue.cpp

/**
*
* 큐 자료구조 구현하기
* // 단일연결리스트
* 
* using class
*/

#include <iostream>
#include <string>

using namespace std;

class Node {
public:
	string data;
	Node* next;
	
	Node(string data) : data(data), next(nullptr) {}
};

class Queue {
private:
	Node* front;
	Node* rear;

public:
	// 생성자
	Queue() : front(nullptr), rear(nullptr){}

	// 소멸자
	~Queue() {
		freeQueue();
	}
	bool isEmpty();
	int enQueue();
	int deQueue();
	void search();
	void printQueue();
	void freeQueue();
};

void menu(int n, Queue& queue)
{

	switch(n)
	{
	case 0:
		queue.freeQueue();
		cout << "프로그램을 종료합니다." << endl;
		exit(0);
	case 1:
		queue.enQueue();
		break;
	case 2:
		queue.deQueue();
		break;
	case 3:
		queue.search();
		break;
	case 4:
		queue.printQueue();
		break;
	default:
		cout << "잘못된 입력입니다. 다시 입력해주세요" << endl;
	}
}

bool Queue::isEmpty()
{
	if (this->front == nullptr)
	{
		cout << "스택이 비었습니다." << endl;
		return true;
	}
	return false;
}

int Queue::enQueue()
{
	cout << "저장할 문장을 입력해주세요.\n";
	string data;
	getline(cin, data);
	Node* newNode = new Node(data);
	if (this->front == nullptr)
	{
		printf("첫번째 데이터를 입력합니다.\n");
		front = rear = newNode;
	}
	else
	{
		rear->next = newNode;	// 새 노드로 가는 길뚫기
		rear = newNode;			// 뚫은 길에 할당하기
	}
	return 1;
}

int Queue::deQueue()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return 0;
	}
	Node* temp = this->front;
	this->front = this->front->next;
	if (front == nullptr)
	{
		rear = nullptr;
	}
	cout << "제거된 문장 : " << temp->data << endl;	
	delete temp;
	return 1;
}

void Queue::search()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	cout << "찾고싶은 문장을 입력해주세요.\n";
	string str;
	getline(cin, str);
	Node* temp = front;
	int i = 1;
	while (temp != nullptr)
	{
		if (temp->data == str)
		{
			cout << str << "의 위치는 " << i << "입니다." << endl;
			return;
		}
		++i;
		temp = temp->next;
	}
	cout << "찾으시는 문장은 큐에 없습니다.\n";

}

void Queue::printQueue()
{
	if (isEmpty())
	{
		printf("단어를 저장해주세요.\n");
		return;
	}
	int i = 1;
	Node* temp = front;
	while (temp != nullptr)
	{
		
		cout << temp->data << "의 위치는 " << i << "입니다." << endl;		
		++i;
		temp = temp->next;
	}
}

void Queue::freeQueue()
{
	while (!isEmpty())
	{
		deQueue();
	}
}


int main()
{
	Queue queue;
	while (1)
	{
		int input;
		cout << "1 : enQueue, 2 : deQueue, 3 : search data, 4 : print Queue, 0 : 프로그램 종료" << endl;
		cin >> input;
		cin.ignore(numeric_limits<streamsize>::max(), '\n');
		menu(input, queue);
	}
	return 0;
}

실습 코드는 제 깃허브에 있습니다.

Workspace/자료구조 at main · cyphen156/Workspace · GitHub