[자료구조] 스택(stack)과 큐(queue)

🌱 스택 (Stack)

스택(Stack)

1. 기본 개념

스택은 기본적으로 LIFO(Last In First Out), 혹은 선입후출 구조라고 한다. 즉, 나중에 들어간 것이 맨 처음 나온다. 다시 말 하면 처음 들어간 것이 맨 뒤에 나오는 구조이다. 동굴을 떠올리면 스택 구조를 쉽게 상상할 수 있다.

2. 이상 상태

스택은 고정된 크기를 갖는 자료구조이다. 따라서 고정된 크기에서 벗어나는 액션을 취할 때 두 가지 이상 상태를 가질 수 있다.

1. 오버플로우(Overflow): 자료구조가 수용 가능한 범위를 가득 채운 상태해서, 초과하여 삽입 연산을 수행하려고 할 때 발생하는 현상

2. 언더플로우(Underflow): 자료구조에 데이터가 들어 있지 않은 상태에서 삭제 연산을 수행하려고 할 때 발생하는 현상

* 예전에는 위 두 용어가 연산 범위에서도 사용되었다고 하지만 현재에는 자료구조에서만 사용된다고 한다. (참고: 팔만코딩경 블로그)

 

3. 파이썬에서의 구현

별도의 라이브러리를 사용하지 않는다. 기본 리스트에 대해 append(), pop() 메소드를 이용하여 스택을 구현할 수 있다.

스택을 요구하는 상당수의 알고리즘의 경우 재귀함수를 함께 활용하면 도움이 된다고 한다. (대표 예시: BFS)

 

🌱 큐 (Queue)

큐와 덱

1. 기본 개념

큐는 스택과 반대로 먼저 들어오면 먼저 나간다. 선입선출이라고 하며, 영어로는 FIFO(First In First Out)라고 한다. 일반적으로 우리가 놀이동산이나 식당에 가면 서는 줄과 같다. 우리가 이렇게 일반적으로 말하는 큐는 선형 큐(Linear Queue)이다. 자료구조의 한 쪽에서는 입력(push)만 처리되며, 반대쪽에서는 출력(pop)만 처리된다.

그런데 큐는 덱(Dequeue)이라는 개념도 함께 알아두면 좋다. 큐의 확장된 버전으로 구현할 때에는 주로 이 덱을 많이 활용하기 때문이다.

덱은 양 방향에서 입출력이 모두 가능하다. 스택과 큐의 장점을 모두 사용할 수 있으며, 데이터의 삽입/제거 속도가 리스트보다 빠르다고 한다.

 

2. 파이썬에서의 구현

파이썬에서는 collections의 dequeue 클래스를 사용하면 쉽게 큐를 구현할 수 있다.

from collections import deque

queue = deque()

queue.append(5) # 5 삽입
queue.popleft() # 삭제
queue.reverse() # 역순으로 바꾸기