자료구조 중에서 Stack과 Queue, Deque이 있다. 이 세가지는 얼핏 비슷한 듯 보이면서도 엄연히 서로 다른 자료구조로, 주로 사용되는 분야나 문제도 다르다.
- Stack : 스택
Stack이란, '쌓아 올린다'는 의미가 있다. 즉, 스택은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조이다. 위의 이미지처럼 동일한 구조와 크기의 자료를 같은 방향으로만 쌓을 수 있다. 따라서, 자료를 넣을 수 있는 곳과 삭제할 수 있는 곳이 동일한 한 군데로 정해져있다. 이때, 삽입하는 연산을 'push', 삭제하는 연산을 'pop'이라 한다.
따라서, 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제된다. 이러한 구조를 후입선출(LIFO)이라고 한다.
- 단점
데이터의 삽입 및 삭제가 진행되는 곳(top)이외에 데이터의 접근 할 수 없다. 즉, 중간에 위치한 데이터의 접근할 수 없다. - 활용
재귀 알고리즘, DFS 알고리즘, 역추적 작업이 필요할 때
- Queue : 큐
Queue란, '무언가를 기다리는 사람이나 자동차 등의 줄' 혹은 '줄을 서서 기다리는 것'이라는 의미가 있다. 따라서, 큐는 스택과 달리 자료를 넣을 수 있는 곳과 삭제할 수 있는 곳이 각각 따로 존재한다.
따라서, 큐는 가장 먼저 삽입된 자료가 가장 먼저 삭제된다. 이러한 구조를 선입선출(FIFO)이라고 한다.
- 단점
중간에 위치한 데이터의 접근할 수 없다.
- 활용
BFS 알고리즘, 대기 순서 관리, 데이터를 입력한 순서대로 처리해야 할 때
- Deque : 덱
Deque이란, Double - Ended Queue 의 줄임말이다. 큐의 경우에는 한쪽에서는 삽입만, 다른 한쪽에서는 삭제만 가능했지만 양쪽에서 삽입과 삭제가 가능한 자료구조를 덱이라 한다. 스택과 큐에서는 중간에 위치한 데이터의 접근할 수 없었지만, 덱에서는 index를 통해서 접근이 가능하다. 중간에 데이터가 삽입되는 경우 다른 요소들을 앞뒤로 밀 수 있다.
- 단점
스택, 큐에 비해 비교적 구현이 어렵다.
- In Python
나는 코딩테스트를 python으로 준비하고 있다. 그래서 스택, 큐, 덱을 파이썬에서 어떻게 사용하는지에 대해서 간단히 정리하려고 한다.
-
스택
특정 라이브러리는 없는 것 같고 그냥 기본 제공하는 리스트로 구현가능하다. append를 이용하면 자료가 맨 우측에 삽입되고 pop을 이용하면 맨 우측에 자료만 빼낼 수 있다. -
큐와 덱
큐는 queue안에 Queue라는 것을 이용한다.from queue import Queue를 이용해서 큐를 사용한다. Queue에서는 append와 pop대신 put과 get을 쓴다. 대신에 방향성이 없어 색인하면 에러가 난다.
이럴때는 collections안에 deque를 사용한다.from collections import deque를 사용하여 덱을 사용한다. 방향성이 있기에 색인도 가능하고 append와 pop은 자료구조 우측에 삽입 / 삭제된다. appendleft와 popleft도 있는데 자료구조 좌측에 삽입 / 삭제된다.
