[자료구조 멘토링] 스택, 큐, 덱 (feat.Python)

1. 스택

1-1. 스택이란?

 

스택은 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last-in-First-out) 자료구조로, 후입선출방식이라고도 부른다.

즉, 마지막에 추가된 요소가 가장 먼저 제거되는 자료구조이다.

 

1-2. 파이썬에서의 스택

파이썬은 스택 자료구조를 따로 제공하지 않지만, list 클래스를 사용하여 스택을 구현할 수 있다.

 

1-3. 사용 방법

class Stack:
    def __init__(self):
        """ 스택을 초기화하는 생성자 """
        self.stack = []

    def push(self, item):
        """ 스택에 요소 추가 """
        self.stack.append(item)

    def pop(self):
        """ 스택에서 요소 제거 (후입선출) """
        if not self.is_empty():
            return self.stack.pop()
        return None  # 빈 스택이면 None 반환

    def top(self):
        """ 스택의 가장 위에 있는 요소 반환 (제거하지 않음) """
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        """ 스택이 비어있는지 확인 """
        return len(self.stack) == 0

    def size(self):
        """ 스택의 크기 반환 """
        return len(self.stack)

 

2. 큐

2-1. 큐란?

큐(Queue)는 FIFO(First-in, First-out) 방식 자료구조로, 선입 선출 방식이다.

즉, 먼저 들어온 데이터가 먼저 나가는 구조를 의미한다.

 

2-2. 파이썬에서의 큐

파이썬은 스택 자료구조를 따로 제공하지 않지만, list 클래스를 사용하여 스택을 구현할 수 있다.

다만, list를 이용한 큐 구현은 비효율적일 수 있기 때문에, collections.deque또는 deque.Queue를 사용하는 것이 권장된다.

 

 

2-3. 배열(List)을 이용한 큐 구현

class Queue:
    def __init__(self):
        """ 큐 초기화 """
        self.queue = []

    def enqueue(self, item):
        """ 큐의 끝에 요소 추가 (삽입) """
        self.queue.append(item)

    def dequeue(self):
        """ 큐의 앞에서 요소 제거 (삭제) """
        if not self.is_empty():
            return self.queue.pop(0)  # 리스트의 첫 번째 요소 제거
        return None

    def front(self):
        """ 큐의 맨 앞 요소 반환 (제거하지 않음) """
        if not self.is_empty():
            return self.queue[0]
        return None

    def is_empty(self):
        """ 큐가 비어있는지 확인 """
        return len(self.queue) == 0

    def size(self):
        """ 큐의 크기 반환 """
        return len(self.queue)

 

3. 덱

3-1. 덱(Deque)이란?

덱은 양쪽 끝에서 요소를 삽입하거나 삭제할 수 있는 자료구조이다. 일반적인 큐와 달리 앞쪽과 뒤쪽 모두에서 삽입 및 삭제가 가능하다.

 

 

• append(): 덱의 뒤쪽에 요소 삽입
• appendleft(): 덱의 앞쪽에 요소 삽입
• pop(): 덱의 뒤쪽 요소 제거
• popleft(): 덱의 앞쪽 요소 제거

 

 

3-2. 덱(Deque)를 이용한 큐 구현

## deque 생성
from collections import deque

dq = deque()  # 빈 deque 생성
dq = deque([1, 2, 3])  # 초기값 설정

## 요소 추가 (append, appendleft)
dq.append(4)        # 오른쪽 끝에 4 추가
dq.appendleft(0)    # 왼쪽 끝에 0 추가
print(dq)  # deque([0, 1, 2, 3, 4])

## 요소 제거 (pop, popleft)
dq.pop()           # 오른쪽 끝 요소 제거
dq.popleft()       # 왼쪽 끝 요소 제거
print(dq)  # deque([1, 2, 3])

## 최대 길이 설정 (maxlen)
dq = deque(maxlen=3)  # 최대 3개까지 저장 가능
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)  # 1은 자동 삭제됨
print(dq)  # deque([2, 3, 4], maxlen=3)

## 요소 순환 (rotate)
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)  # 오른쪽으로 2칸 회전
print(dq)  # deque([4, 5, 1, 2, 3])

dq.rotate(-2)  # 왼쪽으로 2칸 회전
print(dq)  # deque([1, 2, 3, 4, 5])

## 모든 요소 제거 (clear)
dq.clear()
print(dq)  # deque([])

## 특정 값 개수 세기 (count)
dq = deque([1, 2, 3, 1, 1, 4, 1])
print(dq.count(1))  # 4

 

3-3. 덱을 이용한 큐 와 스택 구현

## 큐로 사용 (popleft)
dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)

print(dq.popleft())  # 1
print(dq.popleft())  # 2
print(dq.popleft())  # 3
✅ FIFO(선입선출) 방식으로 작동 → 큐(Queue)로 활용 가능

## 스택으로 사용 (pop)
dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)

print(dq.pop())  # 3
print(dq.pop())  # 2
print(dq.pop())  # 1
✅ LIFO(후입선출) 방식으로 작동 → 스택(Stack)으로 활용 가능