자료구조 - 스택(Stack), 큐(Queue) 개념 정리

배경설명

---

자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.

자료구조에 따라서 해결할 수 있는 문제와, 더욱 시간을 단축할 수 있는 알고리즘들이 존재ㅎ나다.

그 중, 오늘 설명할 스택과 큐는 Push와 Pop이라는 두가지 함수를 중심으로 작동한다.

 

두 연산의 경우 Overflow와 Underflow 문제를 야기할 수 있기 때문에 함께 고민해야 한다.

 

삽입(PUSH)	자료구조에 데이터를 삽입한다.
삭제(POP)	자료구조에 있는 데이터를 삭제한다.
Overflow	특정한 자료구조가 수용할 수 있는 데이터의 크기를 넘어선 상태에서 데이터를 삽입하는 연산을 수행할 때 발생한다. (수용 가능 용량이 초과한 상태에서 PUSH 연산을 하는 경우)
Underflow	특정 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 없기에 발생하는 오류이다. (비어있는 자료구조에 POP연산을 수행하는 경우)

 

오늘 설명한 Stack과 Queue의 경우, Push와 Pop 두 가지 연산 만으로 동작한다.

데이터를 넣고 빼기만 하는데, 두 가지 자료구조는 데이터를 빼는 방식이 다르다. 

 

스택 (Stack)

---

스택이란, 박스를 쌓는 것을 생각하면 된다.

박스는 보통 바닥부터 위로 차곡차곡 쌓으며, 꺼낼 때는 위에서 부터 차례로 꺼낸다.

 

이러한 구조를 선입후출 (First In Last Out) 또는 후입선출 (Last In First Out)이라고 한다.

 

즉, 가장 먼저 들어간 데이터는 제일 나중에 꺼낼 수 있다.

후에 언급될 그래프 연산 중, DFS (깊이 우선 탐색)에서 사용되는 자료구조이다.

따라서 익혀두는 것이 많이 도움이 된다.

 

PUSH 연산

POP 연산

 

위 그림과 같이, Push하면 차례로 넣고

Pop하면 역순으로 데이터를 추출한다.

 

이러한 자료구조를 Stack이라고 한다.

만약 파이썬으로 이를 구현한다면 어떻게 해야 할까?

 

C++이나 타 언어와 달리, 파이썬에서는 기본 자료형인 List를 활용하여 Stack을 구현한다.

append 함수로 push연산을 수행하면 되고, pop 함수로 pop 연산을 하면 된다.

위 그림을 코드로 나타내면 아래와 같다.

stack = []

stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)

stack.pop() # 4 제거
stack.pop() # 3 제거
stack.pop() # 2 제거
stack.pop() # 1 제거

 

Stack의 구조를 활용한 문제 풀이는 나중에 집중적으로 진행하도록 하고,

지금은 코드와 개념에 익숙해지자

큐 (Queue)

---

큐는 흔히 놀이공원에서 볼 수 있는 대기줄로 생각하면 된다.

먼저 서있는 사람은 먼저 놀이기구를 탈 수 있게 된다.

따라서 나중에 온 사람은 나중에 들어가게 되며, 이를 공정한 자료구조라고 설명한다.

또한 이러한 구조는 First In First Out (선입선출) 구조라고 한다.

 

간단하게, 하나에 파이프에 물을 넣는다고 생각하면 된다.

먼저 들어간 물은 먼저 나오게 될 것이다. Queue는 이러한 형태의 자료구조이다.

 

또한 큐는 그래프 탐색 연산 중, BFS (넓이 우선 탐색)에서 사용되는 자료구조이다.

 

Push 연산	Pop 연산

 

큐는 위 그림처럼 차례로 넣으면 넣은 순서대로 나오게 된다.

 

이 또한 append나 pop으로 구현할 수 있으나,

Queue 같은 경우는 collections 라이브러리의 deque를 활용하는 것이 좋다.

리스트 자료형보다 속도도 빠른 편이고, 더욱 직관적이기 때문이다.

 

Queue는 한 방향으로 흐르는 듯이 데이터가 이동하는데,

Deque란, 양방향에서 데이터를 넣고 뺄 수 있어서 양방향 큐라고 한다.

 

주로 코딩테스트에서는 collections 모듈과 같은 기본적인 라이브러리들은 사용할 수 있도록 해주기에,

문제를 해결함에 있어서 활용할 수 있도록 익혀두는 편이 좋다.

 

파이썬으로 위의 큐를 순서대로 구현한 코드는 아래와 같다.

 

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

queue.popleft() # 1 제거
queue.popleft() # 2 제거
queue.popleft() # 3 제거
queue.popleft() # 4 제거

 

 앞서 설명한 것과 같이, deque의 경우 양방향 큐이기 때문에, pop함수가 방향별로 나뉘어져 있다.

 

따라서 우리는 deque가 queue처럼 작동할 수 있게 popleft를 통해 첫번째 원소를 빼낼 수 있다.

 

또한 deque의 경우, list(queue)를 하면 리스트 자료형으로 변환할 수 있다.