[Data-Structure] Stack, Queue, Deque

Stack과 Queue는 선형 자료구조의 특징을 공통적으로 가지고 있다.

 

Stack  :

 Last In First Out (LIFO) - 후입 선출 (후에 들어간 원소가 먼저 배출)

 First In Last Out (FILO) - 선입 후출 (먼저 들어간 원소가 나중에 배출)

이것은 Stack의 가장 큰 특징이며 차곡차곡 쌓이는 구조로 이해하면 된다.

그렇기에 늦게 들어간 녀석들은 점차 쌓이게 되고 호출 시 가장 위에 있는 원소가 나오는 구조이다.

 

ex ) 바구니에 물건을 담았다가 위에서부터 꺼냄

---

Queue :

First In First Out (FIFO). - 선입 선출 (먼저 들어간 원소가 먼저 배출)

Stack과 다르게 들어간 원소가 쌓이는 것은 마찬가지이나 들어간 순으로 배출된다는 것이 특징이다.

 

ex ) 놀이공원에서 대기줄의 앞부터 순서대로 입장하는 것

---

Deque :

Stack과 Queue의 특징을 모두 합한 구조이다.

타 구조처럼 데이터가 순차적으로 쌓이는 것은 동일하다.

하지만 배출되는 과정에서 차이가 있다.

 

원소는 가장 먼저 들어간 원소나 가장 마지막에 들어간 원소들을 양방향으로 배출가능한 것이 특징이다.

 

ex ) 빨대에 방향에 상관없이 물체가 빠져나갈 수 있는 것

• Python에는 collections라는 라이브러리에서 deque를 이용할 수 있다.

Example : 

from collections import deque

deque_list = [1,2,3,4,5]

deque = deque(deque_list)

# 가장 왼쪽 원소를 배출하여 출력 
print(deque.popleft())

# 가장 오른쪽 원소를 배출하여 출력
print(deque.pop())

print(deque.popleft())

print(deque.pop())

print(deque.popleft())

 

Result :

1
5
2
4
3