CS 공부 & 면접 맛보기 0x01 [자료구조] : 스택(Stack)과 큐(Queue)의 차이점

자료구조: 스택(Stack)과 큐(Queue)의 차이점

질문

스택(Stack)과 큐(Queue)의 차이점은 무엇인가요?

---

답변

스택(Stack)과 큐(Queue)는 모두 선형 자료구조로, 데이터를 저장하고 관리하는 방식이 다릅니다.

• 스택(Stack): 선입후출(LIFO, Last In First Out) 방식.
• 큐(Queue): 선입선출(FIFO, First In First Out) 방식.
• 공통점: 배열이나 연결 리스트를 사용해 구현할 수 있음.
• 특이점: Python의 리스트는 기본적으로 스택 동작만 지원하며, 큐를 구현하려면 별도의 라이브러리를 사용하거나 스택 2개를 조합하여 구현 가능.

---

질문과 답변에 대한 설명

1. 스택(Stack)이란?

스택은 데이터를 한쪽 끝에서만 삽입(Push)하고 삭제(Pop)하는 구조입니다.

• 특징: 마지막에 추가된 데이터가 가장 먼저 제거됩니다(LIFO).
• 사용 사례:
  • 함수 호출의 순서 관리 (Call Stack).
  • 뒤로가기/앞으로가기 기능 (브라우저 기록).
  • 수식 계산 (괄호 검증, 후위 표기법).

Python 코드 예시:

stack = []
stack.append(10)  # Push
stack.append(20)
print(stack.pop())  # Pop -> 20
print(stack)  # Output: [10]

 

2. 큐(Queue)란?

큐는 데이터를 한쪽 끝에서 삽입(Enqueue)하고 반대쪽 끝에서 삭제(Dequeue)하는 구조입니다.

• 특징: 먼저 들어온 데이터가 먼저 나갑니다(FIFO).
• 사용 사례:
  • 작업 대기열 (Job Scheduling).
  • BFS(너비 우선 탐색)와 같은 그래프 탐색.
  • 프린터 작업 관리.

Python 코드 예시 (deque 사용):

from collections import deque

queue = deque()
queue.append(10)  # Enqueue
queue.append(20)
print(queue.popleft())  # Dequeue -> 10
print(queue)  # Output: deque([20])

 

3. 공통점

• 둘 다 선형 자료구조로 데이터를 순차적으로 관리합니다.
• 배열(Array)나 연결 리스트(Linked List)로 구현 가능합니다.
• 데이터 삽입/삭제가 주된 작업입니다.

4. 차이점 요약

스택(Stack), 큐(Queue)

작동 방식	LIFO (Last In First Out)	FIFO (First In First Out)
삽입 위치	끝에서 삽입 (Top)	한쪽 끝 (Rear)
삭제 위치	끝에서 삭제 (Top)	반대쪽 끝 (Front)
파이썬 기본 지원	list.append, list.pop	collections.deque 필요

 

5. 응용: 스택 두 개로 큐 구현하기

스택 두 개를 사용하여 큐를 구현할 수 있습니다.

• 하나의 스택을 데이터 삽입용으로 사용.
• 다른 스택을 데이터 삭제용으로 사용.
• 삭제 스택이 비어있을 때, 삽입 스택의 데이터를 모두 옮기면 FIFO 방식이 유지됩니다.

Python 코드 예시:

class QueueWithStacks:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, item):
        self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop() if self.out_stack else None

queue = QueueWithStacks()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue())  # Output: 10
print(queue.dequeue())  # Output: 20