스택과 큐

03-5 스택과 큐

스택과 큐의 핵심 이론

스택

스택(stack)은 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다. 다음 그림을 살펴보자.

그림을 보면 새 값이 스택에 들어가면 top이 새 값을 가리킨다. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 되는 것이다. 파이썬에서는 리스트를 이용하여 쉽게 스택을 구현할 수 있다.

파이썬의 스택

• 위치
  • top: 삽입과 삭제가 일어나는 위치를 뜻한다.
• 연산(리스트 이름이 s일때)
  • s.append(data): top 위치에 새로운 데이터를 삽입하는 연산이다.
  • s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
  • s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 알고리즘에 효과적이므로 반드시 알아 두어야 한다. 후입 선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.

큐

큐(queue)는 삽입과 삭제 연산이 선입선출로 이뤄지는 자료주고이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이뤄진다.

그림을 보면 새 값 추가는 큐의 rear에서 이뤄지고, 삭제는 큐의 front에서 이뤄진다. 파이썬에선 일반적으로 deque(덱)를 이용하여 큐를 구현한다.

파이썬의 큐

• 위치
  • rear: 큐에서 가장 끝 데이터를 가리키는 영역이다.
  • front: 큐에서 가장 앞의 데이터를 가리키는 영역이다.
• 연산(리스트 이름이 s일때)
  • s.append(data): rear 부분에 새로운 데이터를 삽입하는 연산이다.
  • s.popleft(): front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
  • s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.

큐는 너비 우선 탐색(BFS)에서 자주 사용하므로 이 역시도 스택과 함께 잘 알아두어야 하는 개념이다.