스택(Stack)과 큐(Queue)는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나로, 그중에서도 스택(Stack)은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조다. 스택(Stack)은 LIFO(후입선출), 큐(Queue)는 FIFO(선입선출)로 처리된다.
- 스택(Stack)
: 잔뜩 쌓아둔 접시를 떠올려보자. 쌓을 때 차곡차곡 쌓고 다시 꺼낼 때 다시 위에서부터 제일 먼저 꺼내게 된다.
※ 스택(stack)은 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다.
- push() : 요소를 컬렉션에 추가한다.
- pop() : 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다.
- 큐(Queue)
: 맛집에 입장하기 위해 줄을 서는 사람들을 떠올려 보자. 먼저 온 사람이 먼저 나가는 것처럼 선입선출로 빠져나가는 구조이다. 큐는 상대적으로 스택에 비해서는 쓰임새가 적다. 그러나 스택에 비해서 그렇다는 얘기일 뿐, python에서의 Deque 같은 변형들은 여러 분야에서 매우 유용하게 쓰인다.
- 데크(Deque)
: 데크는 스택과 큐의 연산을 모두 갖고 있는 python의 사기적인 복합 자료형이다. 물론 리스트로도 큐의 기능을 할 수 있지만, 시간 복잡도를 따지면 큐의 기능이 필요할 땐 데크를 쓰는 것이 더 효율적이다.
파이썬(Python)은 스택 자료형을 별도로 제공하지는 않지만, 리스트(List)가 사실상 스택의 모든 연산을 지원한다. 큐 또한 마찬가지다. 리스트(List)는 큐의 모든 연산을 지원한다. 다만 리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서는 데크(Deque)라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다. 그러나 굳이 성능을 고려하지 않는다면 리스트(List)는 스택과 큐의 모든 연산을 지원하기 때문에 사실상 리스트를 잘 사용하기만 해도 충분하다.
