[자료구조] 스택, 큐

스택과 큐는 비슷해보이지만 다른 구조이다.

우선 공통점으로는 둘 다 데이터를 쌓고 이를 하나씩 내보낼 수 있는 점이 있다.

차이점은 이 두가지 구조의 특징을 잘 나타내고 있는데, 아래와 같이 정리 할 수 있다.

 

< 스택 Stack >

위 그림 처럼 입구와 출구가 같은 구조 이다.

입력은 A -> B -> C 순으로 이루어지고, 출력은 C -> B -> A 순으로 이루어진다고 생각하면 쉽다.

이를 후입 선출, LIFO (Last In First Out) 이라고 부른다.

언어마다 조금은 다를 수 있지만 대게 데이터를 넣는 것을 push, 빼는 것을 pop 이라 한다.

이때 pop은 마지막 데이터를 리턴해주고, 스택에서는 제거하는 연산임을 주의하면 된다.

 

참고로 파이썬에서 스택은 리스트를 이용하여 구현하고, push는 append(), pop은 pop()을 사용한다.

 

< 큐 Queue >

위 그림 처럼 입구와 출구가 반대인 구조를 큐라고 한다.

입력과 출력 모두 A -> B -> C 순이라고 생각하면 쉽다.

먼저 들어온 데이터가 먼저 나가기 때문에, 이를 선입 선출, FIFO (First In First Out) 이라고 부른다.

입력이 이루어지는 곳은 rear, 출력(삭제)가 이루어지는 곳을 front 라 하며,

rear에서 이뤄지는 삽입 연산을 Enqueue, front에서 이뤄지는 삭제 연산을 Dequeue라 한다.

 

파이썬에서 큐 역시 스택 처럼 리스트로 구현 후 append(), pop(0)으로 큐를 구현 할 수 있다.

하지만 이는 시간 복잡도가 스택에서의 O(1)과 달리 O(n)이 되므로 효율성이 떨어지기 때문에

Queue 클래스의 put()_삽입 연산, get()_삭제 연산으로 진행하거나

collections의 deque를 이용해 append()와 popleft()를 이용한다.

 

deque(Double Ended Queue-덱)는 큐와 비슷하지만 양방향에서 데이터를 넣고 뺄수 있는 구조로

파이썬에서는 append(), pop(), popleft()를 이용할 수 있고, 

pop()을 사용하면 스택, popleft()를 사용하면 큐를 구현 할 수 있다.