[자료구조] #3 큐 Queue (C, C++ 구현)

유지연·2023년 4월 26일
CFIFOqueue자료구조큐
0

자료구조

목록 보기
3/5

👋 대표적인 선형 자료구조 "큐"에 대해 알아보자!

✏️ 큐 Queue

큐(queue)는 "줄, 줄을 서서 기다리다"라는 뜻을 가진 영단어이다.
맛집에 대기줄을 섰을 때를 생각해보자. 내가 가장 먼저와서 줄을 섰는데 제일 마지막에 온 사람을 먼저 들여보내주면 어떻게 될까?? 말도 안되는 일이다!!!!!!!

큐의 사전적 의미에서 유추해볼 수 있듯, 큐는 가장 먼저 들어온 데이터가 가장 먼저 나가는 후입선출의 특징을 가지는 자료구조이다. 이전 포스팅에서 다루었던 스택과 반대되는 개념이다.

✔️ 큐의 특징

  • FIFO (First In First Out), 선입선출
    First In First Out 해석 그대로 "가장 먼저 들어온 데이터가 가장 먼저 나간다"는 의미이 다. 줄을 섰을 때 먼저 온 사람이 먼저 들어가는 것처럼 우리에게는 후입선출보다 더 익숙한 섭리이다 ㅋㅋ

  • front에서 데이터 추출, rear에서 데이터 삽입
    스택은 구멍이 1개였다면 큐는 구멍이 2개인 자료구조라고 생각하면 된다. 데이터가 빠져나가 는 곳을 front, 데이터를 삽입하는 곳을 rear라고 부른다. 또한 데이터를 빼내는 것 을 dequeue, 데이터를 삽입하는 것을 enqueue라고 한다.


데이터의 삽입데이터의 추출특징
스택Top (Push)Top (Pop)LIFO
큐Rear (Enqueue)Front (Dequeue)FIFO

✔️ 큐의 대표적인 연산

  • push rear에 데이터 삽입
  • pop front 데이터 삭제
  • front 가장 먼저 삽입된 데이터 반환
  • back 가장 마지막에 삽입된 데이터 반환
  • size 큐의 크기 반환 (데이터의 개수)
  • empty 큐가 비어있는지 확인

✏️ 큐 구현하기 (배열, 링크드 리스트, C++ STL)

백준 10845번
백준 10845번 문제 조건을 참고하여 큐를 구현해보자.

❗ 배열을 이용한 원형 큐 구현 (C)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define queue_len 10001

typedef struct _Queue {
	int front;
	int rear;
	int queue_arr[queue_len];
} Queue;


int next_index(int now_index) {
	if (now_index == queue_len - 1) return 0;
	else return now_index += 1;
}

void create_queue(Queue* cq) {
	cq->front = 0;
	cq->rear = 0;
}

void enqueue(Queue* cq, int data) {
	if (next_index(cq->rear) == cq->front) printf("Queue is full");
	else {
		cq->rear = next_index(cq->rear);
		cq->queue_arr[cq->rear] = data;
	}
}

void dequeue(Queue* cq) {
	if (cq->rear == cq->front) printf("-1\n");
	else {
		printf("%d\n", cq->queue_arr[(cq->front) + 1]);
		cq->front = next_index(cq->front);
		cq->queue_arr[cq->front] = 0;
	}
}
void queue_size(Queue* cq) {
	int size = (cq->rear) - (cq->front);
	printf("%d\n", size);
}
void queue_empty(Queue* cq) {
	if (cq->rear == cq->front) printf("1\n");
	else printf("%d\n", 0);
}
void front(Queue* cq) {
	if (cq->rear == cq->front) printf("-1\n");
	else printf("%d\n", cq->queue_arr[(cq->front) + 1]);
}
void rear(Queue* cq) {
	if (cq->rear == cq->front) printf("-1\n");
	else printf("%d\n", cq->queue_arr[cq->rear]);
}

int main() {

	Queue queue;
	create_queue(&queue);
	int tc, num;
	char str[6]; //입력값 받을 문자열
	scanf("%d", &tc);

	for (int i = 0; i < tc; i++) {

		scanf("%s", str);

		if (!strcmp(str, "push")) {
			scanf("%d", &num);
			enqueue(&queue, num);
		} //push
		else if (!strcmp(str, "pop")) { dequeue(&queue); } // pop
		else if (!strcmp(str, "empty")) { queue_empty(&queue); } // empty
		else if (!strcmp(str, "size")) { queue_size(&queue); } // size
		else if (!strcmp(str, "front")) { front(&queue); } // front
		else if (!strcmp(str, "back")) { rear(&queue); } // back
		else { printf("%s", "!Wrong Input!\n"); } // 예외처리

	}

	return 0;

}

배열을 이용한 큐 구현의 경우 dequeue를 구현하는 방식에는 두 가지가 있다.

  1. front에서 데이터 추출 후 나머지 데이터를 모두 앞으로 한 칸씩 이동시키는 방법
  2. 데이터는 그대로 두고 front를 한 칸 뒤로 이동시키는 방법

1번의 경우 dequeue를 할 때마다 저장된 데이터를 매번 이동시켜야하고, 사실상 front의 역할이 없어지는 것과 같기 때문에 주로 2번 방식으로 dequeue를 구현한다. 이때, 우리가 알던 일반적인 배열의 개념을 이용한다면 정해진 배열의 size때문에 더 이상 값을 삽입하지 못하는 경우가 발생하게 된다. (dequeue로 인해 앞의 공간이 비어있는데도 말이다!)

원형 큐 (Circular Queue)

이를 보완하고자 나온 개념이 원형 큐 (Circular Queue) 이다.
간단하게 우리가 알고 있던 직선의 배열을 구부려 시작과 끝이 만나는 원형 모양의 배열을 만들었다고 보면 된다. 이것을 구현하기 위해서는 기존의 배열에 한 가지 논리만 추가해주면 된다.

front나 rear의 index값이 내가 지정한 배열의 끝이 되었을 때, 그 다음 위치의 index 값은 배열의 맨 앞인 0 이 되어 원형 큐를 이루게 만드는 것이다. 위 그림을 예시로 보면 index 7의 다음위치가 0인 것을 알 수 있다. 또한 위 코드에서는 next_index 함수가 이 작업을 해주고 있다.

하지만 원형 큐 사용시 문제점이 아직 남아있다. 우리는 원형 큐가 empty인 경우와 full인 경우를 구분할 수 없다는 것이다! empty인 경우와 full인 경우 모두 front index 값이 rear index 값보다 1이 큰 상태이다. 이를 해결하기 위해서 길이가 N인 원형 큐라면 데이터가 N-1개가 되었을 때를 full로 간주할 것이다.

그렇다면 empty인 경우는 front와 rear의 index 값이 같아지고, full인 경우는 front의 index 값이 rear 보다 1만큼 큰 상태가 되어 구분이 가능해진다.

❗ 링크드 리스트를 이용한 구현 (C)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Queue {
	struct _Queue* next_node;
	int data;
} Queue;

typedef struct _Queue_head {
	Queue* front;
	Queue* rear;
	int size;
} Queue_head;


void create_queue(Queue_head* head) {
	head->front = NULL;
	head->rear = NULL;
	head->size = 0;
}

void enqueue(Queue_head* head, int data) {
	Queue* newnode = malloc(sizeof(Queue));
	newnode->next_node = NULL;
	newnode->data = data;

	if (head->size == 0) {
		head->front = newnode;
		head->rear = newnode;
	}
	else {
		head->rear->next_node = newnode;
		head->rear = newnode;
	}
	head->size += 1;
}

void dequeue(Queue_head* head) {
	if (head->size == 0) printf("-1\n");
	else {
		Queue* delete_node = head->front;
		printf("%d\n", delete_node->data);
		head->front = head->front->next_node;
		free(delete_node);
		head->size -= 1;
	}
}
void queue_size(Queue_head* head) {
	printf("%d\n", head->size);
}
void queue_empty(Queue_head* head) {
	if (head->size == 0) printf("1\n");
	else printf("%d\n", 0);
}
void front(Queue_head* head) {
	if (head->size == 0) printf("-1\n");
	else printf("%d\n", head->front->data);
}
void rear(Queue_head* head) {
	if (head->size == 0) printf("-1\n");
	else printf("%d\n", head->rear->data);
}

int main() {

	Queue_head* queue = malloc(sizeof(Queue_head));
	create_queue(queue);
	int tc, num;
	char str[6]; //입력값 받을 문자열
	scanf("%d", &tc);

	for (int i = 0; i < tc; i++) {

		scanf("%s", str);

		if (!strcmp(str, "push")) {
			scanf("%d", &num);
			enqueue(queue, num);
		} //push
		else if (!strcmp(str, "pop")) { dequeue(queue); } // pop
		else if (!strcmp(str, "empty")) { queue_empty(queue); } // empty
		else if (!strcmp(str, "size")) { queue_size(queue); } // size
		else if (!strcmp(str, "front")) { front(queue); } // front
		else if (!strcmp(str, "back")) { rear(queue); } // back
		else { printf("%s", "!Wrong Input!\n"); } // 예외처리

	}

	free(queue);
	return 0;

}

링크드 리스트를 사용하는 경우에는 동적할당한 데이터에 대해 메모리 관리를 해주는 것이 가장 중요하다. 그 외는 오히려 배열보다 훨씬 구현이 간단하다고 느꼈다. dequeue에서도 포인터 값을 조정해주는 것으로 간단하게 구현이 가능하다.

✔️ C++ STL stack

C++에서는 다양한 자료구조를 직접 구현하지 않고도 사용할 수 있도록 STL (Standard Template Library)를 제공해준다. 큐 역시 STL을 사용하여 간단하게 사용할 수 있다!

  • queue.push( ) 데이터의 삽입
  • queue.pop( ) 데이터의 삭제
  • queue.front( ) 가장 최근의 데이터 반환
  • queue.back( ) 가장 최근의 데이터 반환
  • queue.size( ) 스택의 크기 반환
  • queue.empty( ) 스택이 비어있는지 확인

❗ STL 사용 (C++)

#include <iostream>
#include <queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tc;
	string command;
	queue<int> queue;
	cin >> tc;

	for (int i = 0; i < tc; i++) {
		cin >> command;

		if (command == "push") {
			int n;
			cin >> n;
			queue.push(n);
		}
		else if (command == "pop") {
			if (queue.size() == 0) cout << -1 << "\n";
			else {
				cout << queue.front() << "\n";
				queue.pop();
			}
		}
		else if (command == "size") cout << queue.size() << "\n";
		else if (command == "empty") {
			if (queue.size() == 0) cout << 1 << "\n";
			else cout << 0 << "\n";
		}
		else if (command == "front") {
			if (queue.size() == 0) cout << -1 << "\n";
			else cout << queue.front() << "\n";
		}
		else if (command == "back") {
			if (queue.size() == 0) cout << -1 << "\n";
			else cout << queue.back() << "\n";
		}
		else cout << "Wrong Input!" << "\n";
	}
	return 0;
}

오늘은 C와 C++을 이용하여 큐를 다양한 방법으로 구현해보았다!

구현하는 과정에서 스택과 유사한 점이 많아서 어렵지 않게 구현했던 것 같다. 스택과 큐는 배운지 오래되었고 각각의 특성들은 알고 있었는데 그래도 직접 구현을 해보니 더욱 확실하게 머리에 들어 온 것 같다. 이제 스택과 큐를 끝냈으니 비선형으로 넘어가서 트리를 다루어 볼 예정이다. 그리구 알고리즘 공부도 쫌 하자!!!! 백준 골드가 껌이 되는 그날까지...💪💪

[이미지 출처] https://www.programiz.com/dsa/stack

profile
유지연
Keep At It
이전 포스트

[자료구조] #2 스택 Stack (C, C++ 구현)

다음 포스트

[자료구조]#4 트리 Tree (C++ 구현)

0개의 댓글