[DS] 스택과 큐 (Stack & Queue)

스택은 데이터구조 수업을 듣는다면 당연히 알게되는 자료구조다. 

그래서 익숙하기도 하지만 실제로 알고리즘 문제를 풀 때도 유용하게 사용된다. 

 

Stack 정의

스택은 LIFO(Last-In-First-Out) 리스트인데 가장 나중에 들어간 element가 pop했을 때에 가장 먼저 나오는 구조라고 볼 수 있다. 실생활에서 비슷한 예제로는 수건을 쌓아놓았을 때에 가장 위에 있는 수건을 사용하기 때문에 제일 밑에 있는 수건은 사용이 잘 안되는 것으로 이해할 수 있다. 아래의 사진이 스택을 간단하게 설명해준다. 

이미지 출처 : https://dev.to/rinsama77/data-structure-stack-and-queue-4ecd

Stack Functions

스택을 사용할 때에 중요한 function들이 있다. 

시작하기 전에, 스택의 top은 스택에 item이 저장될 공간을 가르키기 때문에 중요하다. Top이라고 이름붙여진 이유는 말그대로 스택의 가장 위기 때문이다. 

 

Stack Push(stack, item) - 스택에 item을 집어넣기 위한 기능이다. push를 했다면 스택의 top에 item을 저장한 것이다.

element Pop(stack) -  스택의 top에 있는 item을 삭제하고 이 item을 return 값으로 가져오는 기능

boolean isFull - 스택을 직접 구현한다면 스택이 꽉차있는지 확인하기 위한 중요한 기능이다. 스택에 push된 element의 갯수가 스택의 사이즈와 같다면 full이라고 판단해서 true 값을 리턴하고 아니라면 false를 리턴한다. 

boolean isEmpty - 스택이 비어있는지 확인하는 기능이다. 스택에 item이 없다면 true 값을 리턴하고 아니라면 false를 리턴한다. 

 

Stack을 직접 구현한다면 배열을 사용해서 직접 구현할 수 있다. 

하지만 C++을 사용한다면 STL에 잘 구현된 Stack Library가 있다. 이걸 활용하면 stack을 편하게 이용할 수 있다. 

#include <stack>
#include <iostream>

using namespace std;

int main(){
	stack <int> s; //int 값을 저장하는 스택
    
    s.push(1);
    s.push(2);
    s.push(3);
    
    cout << "top: " << s.top() << endl;
    s.pop();
    
	return 0;
}

 

개인적으로 DFS를 구현할 때에 재귀함수를 쓰지 않는 경우에 스택을 자주 사용하는데 이와 관련해서는 따로 적어보겠다. 

 

Queue 정의

큐(Queue)는 스택과 반대로 FIFO(First-In-First-Out) list다. 가장 먼저 들어온 아이템이 먼저 나가는 방식이다. 실생활에서의 예제는 은행에서 번호표를 뽑고 기다리면 순서대로 처리되는 것을 생각해볼 수 있다. 그렇기 때문에 스택에서는 top이라는 위치알림이가 하나만 필요했지만 큐는 pop될 때 나갈 element의 위치, 그리고 새로 들어올 element의 위치를 알려주기 위해 front와 rear라는 두 개의 인덱스가 필요하다. 

이미지 출처: https://medium.com/basecs/to-queue-or-not-to-queue-2653bcde5b04

Queue에 element를 push하는 것은 enqueue, pop하는 것은 dequeue라고도 하는데 C++ STL을 사용할 때에는 그냥 push(item), pop() 을 사용하면 된다. 참고로 내가 참고한 책에서는 addq, deleteq라는 term을 사용한다. 

 

아래는 queue를 배열로 구현했을 때에 간단한 모습이다. 참고로 책에 있는 내용이고 구현을 위한 가이드라인이기 때문에 복붙해서 실행되지 않는다. 참고해서 직접 구현해보면 큐가 익숙해질 것이다. 

#define MAX_QUEUE_SIZE 100
typedef struct{
	int key;
} element;

element queue[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;

boolean isEmptyQ(queue){
	if(front==rear) return true;
    else return false;
}

boolean isFullQ(queue){
	if(rear == MAX_QUEUE_SIZE - 1) return true;
    else false;
}

void addq(element item){
	if(rear == MAX_QUEUE_SIZE - 1)
    	queueFull();		/* 큐가 꽉차있다고 오류 처리 */
    queue[++rear] = item;
}

element deleteq(){
	if(front == rear)
    	return queueEmpty(); /* 큐가 비었다고 오류 처리*/
    reutrn queue[++front];
}

 

큐는 BFS를 구현할 때에도 유용하게 사용되지만 컴퓨터의 정말 많은 부분에서 쓰인다. 그 예로 운영체제의 job scheduling이 있다. 

위처럼 정해진 배열에서 큐를 사용할 수도 있지만 작업이 진행될 수록 front와 rear는 오른쪽으로 이동하기 때문에 제일 오른쪽으로 갔을 때에 원점으로 되돌아올 수 있게 해주어야 한다. 이를 circular queue라고 부른다. 

이미지 출처: https://www.geeksforgeeks.org/circular-queue-set-1-introduction-array-implementation/

Queue 또한 C++에서는 STL로 쉽게 구현할 수 있다. 

#include <queue>
#include <iostream>

int main(){
	queue<int> q;
    
    q.push(1);
    q.push(2);
    q.push(3);
    
    cout << q.front() << endl; /* prints 1 */
    cout << q.back() << endl; /* prints 3 */
    q.pop();
    cout << q.front() << endl; /* prints 2 */
    cout << q.back() << endl; /* prints 3 */
    
	return 0;
}

참고자료

Fundamentals of Data Structures in C