스택(Stack) & 큐(Queue)

개발자 강세영·2023년 6월 14일

cpp queue stack 데크 링크드 큐 순환 큐 스택 우선순위 큐 자료구조 큐 파이썬

TIL

목록 보기

58/66

스택(Stack) ADT

스택이란 뭔가를 쌓아 올린 것을 말한다. 즉, 추상 자료형 스택은 데이터를 바닥에서부터 쌓아 올리는 구조이다.
스택은 가장 마지막에 들어간 데이터가 제일 먼저 나오고(Last In First Out, LIFO) 가장 먼저 들어간 데이터는 가장 나중에 나오는(First In Last Out, FILO) 후입선출 구조이다.
스택에서 요소의 삽입과 삭제는 맨 위에서만 이루어진다.
스택의 핵심 기능은 삽입(push)과 제거(pop) 연산이다.
스택에 요소를 삽입하거나 삭제하려면 무조건 맨 위(top)에서 처리하면 되므로 시간 복잡도는 $O(1)$ 이 된다.
스택의 특정 요소에 접근하거나 검색하려면 위에서부터 차례대로 찾아야 하므로 시간 복잡도는 $O(n)$ 이 된다.
스택이 활용되는 대표적인 사례
- 변수를 선언하고, 그 변수의 수명이 끝나면 자동으로 제거하는 자동 메모리(메모리 레이아웃의 스택)는 스택 기반으로 구현되어 있다.
- 대부분의 네트워크 프로토콜은 스택 기반으로 구현되어 있다.
- 재귀적인 함수 또는 알고리즘
- 컴파일러의 구문 분석기
- 후위 표기식 계산
- 각종 편집 프로그램의 되돌리기(undo) 기능

큐(Queue) ADT

큐를 다른 말로 대기행렬이라고 하는데 대기는 기다리는 것이고 행렬은 줄이므로 큐는 기다리는 줄이라고 할 수 있다.
추상 자료형 큐는 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나오는 선입선출(First In First Out, FIFO 또는 First Come First Serve, FCFS) 구조이다.
큐의 핵심 기능은 스택과 마찬가지로 삽입(enqueue)과 제거(dequeue) 연산이다.
큐의 가장 앞 위치를 전단(front), 가장 끝 위치를 후단(rear)이라고 부른다.
큐의 요소의 제거는 전단에서, 삽입은 후단에서 수행된다.
스택과 비슷하게 요소의 삽입과 삭제를 하는 위치가 정해져 있으므로 시간 복잡도는 $O(1)$ 이 된다.
큐의 요소에 접근하거나 탐색하려면 스택과 마찬가지로 순차적으로 접근해야 하므로 시간 복잡도는 $O(n)$ 이 된다.
큐가 활용되는 대표적인 사례
- 데이터의 임시 저장 공간으로 사용되는 버퍼(buffer)
- 탐색 알고리즘에서의 상태 공간
- 병렬 처리 시스템에서 작업들을 관리하기 위한 작업 큐(Job Queue)

순환 큐(Circular Queue)

단순하게 배열로 큐를 구현하고 삽입을 하다보면 결국 후단이 배열의 끝에 도달하게 되므로 더 이상 큐에 요소를 삽입할 수 없게 된다. 또한 제거 연산을 할수록 전단의 위치가 후단에 가까워진다.
이러한 전단과 후단의 위치 문제 때문에 큐의 실제 가용 공간보다 활용 가능 공간이 적어지게 되는 문제가 있다.
큐의 요소를 제거할 때마다 모든 요소의 위치를 한 칸 앞으로 재배치하면 문제가 해결되지만 남아 있는 n개의 요소들 만큼 재배치해야 하므로 비효율적이다.
순환 큐를 이용하면 이런 문제를 해결할 수 있다.
시작과 끝을 연결해서 효율적인 삽입과 삭제 연산이 가능하도록 고안된 큐를 순환 큐 또는 원형 큐라고 한다.
순환 큐의 후단 또는 전단 값이 배열의 끝에 있을 때 삽입 또는 제거를 하면 후단 또는 전단 값을 초기화하는 방법이 있다. 이렇게 하면 배열의 요소를 재배치하지 않으면서도 배열의 공간을 모두 활용할 수 있다.
순환 큐의 전단과 후단 변수의 위치가 동일하면 공백 상태로 볼 수 있지만 포화 상태로 볼 수도 있기 때문이 이 두 상태를 구별하는 로직이 필요하다.
다른 방법으로는 순환 큐 배열을 생성할 때 실제로 필요한 용량보다 1만큼 더 크게 생성하고 그 부분(더미 노드)에 후단이 위치할 경우 포화 상태로 보는 방법이 있다. 이 방법 또한 전단과 후단이 배열의 끝을 넘으면 초기화 해야한다.
- (후단 == 전단)이면 큐가 공백 상태이다.
- (후단 > 전단) 이고 ((후단 - 전단) == 큐의 용량)이면 큐가 포화 상태이다.
- (후단 < 전단) 이고 ((후단 + 1) == 전단)이면 큐가 포화 상태이다.

링크드 큐(Linked Queue)

링크드 큐는 연결 리스트와 비슷하게 구성 요소가 서로 연결된 노드로 이루어진 큐이다.
링크드 큐에서의 삽입 연산은 삽입할 노드에 후단을 연결하고, 제거 연산은 전단 바로 다음 노드의 전단에 대한 포인터를 null 포인터로 만드는 방식으로 구현된다.
링크드 큐는 순환 큐와는 다르게 배열보단 연결 리스트에 가깝기 때문에 크기를 정하지 않고 생성할 수 있다.
따라서 요소를 삽입할 때 큐가 가득 찬 상태인지 확인할 필요가 없다.

데크(Double-ended Queue, deque)

데크란 맨 앞과 맨 뒤 양쪽에서 요소의 삽입과 삭제가 모두 가능하도록 만든 큐 이다.
데크는 보통 이중 연결 리스트로 구현되기 때문에 일반적인 큐와는 달리 맨 앞과 맨 뒤 양 쪽에서 삽입과 삭제를 할 수 있으며 이에 대한 시간 복잡도는 $O(1)$ 이다.
맨 앞이나 맨 뒤의 요소를 조회하는 시간 복잡도는 $O(1)$ 이지만 그 외의 요소를 조회하려면 순차적으로 접근해야하므로 $O(n)$ 이 걸린다.

우선순위 큐(Priority Queue)

우선순위 큐란 각 요소에 우선순위가 추가로 부여되어있는 큐를 말한다.
우선순위 큐에서 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 처리된다.
우선순위가 같은 요소의 처리 순서를 결정하기 위해 우선순위 외에 추가적인 정렬 기준을 사용할 수 있다.
- FIFO (First-In, First-Out): 우선순위가 같은 요소 중에서 먼저 삽입된 요소가 먼저 처리되는 방식이다.
  즉, 큐의 선입선출과 같다.
- LIFO (Last-In, First-Out): 우선순위가 같은 요소 중에서 나중에 삽입된 요소가 먼저 처리되는 방식이다.
  즉, 스택의 후입선출과 같다.
- 그 외에도 요소의 크기 등을 고려하여 우선순위를 결정할 수 있다.

스택과 큐의 비교

스택과 큐 모두 요소의 삽입과 삭제가 정해진 순서대로 이루어지지만 그 위치가 다르다.
스택은 후입선출(LIFO)이고 큐는 선입선출(FIFO)이다.
스택은 요소의 삽입과 삭제가 맨 위(top)에서만 수행된다.
큐는 요소의 삽입은 후단(rear)에서, 삭제는 전단(front)에서 수행된다.
스택과 큐의 시간/공간 복잡도는 서로 같다.
- 요소 삽입 또는 삭제: $O(1)$
- 요소 조회: $O(n)$
- 요소 탐색: $O(n)$
- 공간 복잡도: $O(n)$

제약을 갖는 자료구조의 필요성

스택이나 큐와 같은 제약을 갖는 자료구조를 사용하면 다음과 같은 장점이 있다.
첫째는 잠재적인 버그를 막을 수 있다. 선입선출이나 후입선출로 요소를 다뤄야만 하는 알고리즘에서는 이러한 순서를 지키지 않으면 치명적인 버그를 일으킬 수 있는데, 스택이나 큐를 사용하도록 만들면 이러한 버그를 예방할 수 있다.
둘째는 문제해결에 도움이 된다. 선입선출이나 후입선출 순서를 따라야 하는 문제가 많은데 이러한 문제를 위해 추상화한 자료구조가 바로 스택과 큐다.
또한 스택이나 큐 같은 자료구조의 속성을 활용해서 작성한 코드는 다른 개발자에게도 익숙하게 읽힌다. 예를 들어 어떤 알고리즘 구현에 스택에 관련된 코드가 있다면 그 알고리즘은 후입선출에 기반하여 동작함을 바로 알 수 있다.

언어 별 스택과 큐 사용

파이썬

파이썬의 리스트(list)는 사실상 스택과 큐의 모든 연산을 지원하므로 성능이 중요하지 않은 경우 스택과 큐에 대해 모두 리스트를 사용하면 된다.
파이썬 내장 모듈 queue에서 FIFO 큐, LIFO 큐, 우선순위 큐 등 다양한 큐 클래스를 제공한다. 또한 이 모듈은 스레드 세이프를 보장한다.
queue 모듈의 PriorityQueue 같은 클래스들은 스레드 세이프를 보장하지만 GIL 때문에 파이썬(CPython)에선 멀티 스레딩을 활용하기 어렵기 때문에 이 클래스를 사용하는 이득이 크지 않다.
우선순위 큐에 대해서는 heapq 모듈도 활용할 수 있다. 이 모듈은 우선순위 큐 또는 힙(heap)을 구현한 파이썬 내장 모듈이다.
데크에 대해선 collections 모듈의 deque를 사용할 수 있다.