스택(Stack), 큐(Queue), 데크(Deque) 개념/비교/간단한 구현

큐 (QUEUE)란

선입선출(FIFO : First In First Out)원칙을 따르는 자료구조로 먼저 들어온 데이터가 먼저 나가는 구조이다. 일상생활에서의 대기줄과 유사하다고 생각할 수 있다.

특징

• 데이터는 한쪽 끝(rear)에서 삽입되고, 다른 쪽 끝(front)에서 삭제된다.
• 주로 순서대로 처리해야하는 작업을 관리하는데 사용된다.

주요 연산

• Enqueue : 데이터를 큐의 rear에 추가합니다.
• Dequeue : 큐의 front에서 데이터를 제거하고 반환합니다.
• Peek/Front : 큐의 front에 있는 데이터를 제거하지 않고 반환합니다.
• IsEmpty : 큐가 비어 있는지를 확인합니다.
• put : 큐의 Rear에 삽입
• get : 큐의 Front에서 가져옴

파이썬에서의 구현

from queue import Queue
#
# 큐 생성
q = Queue()
#
# 요소 추가
q.put(1)
q.put(2)
q.put(3)
#
# 요소 제거 및 출력
print(q.get())  # 출력: 1
print(q.get())  # 출력: 2
print(q.get())  # 출력: 3

파이썬에서 라이브러리를 사용하지 않고 직접 구현

class Queue:
    def __init__(self):
        self.queue = []
	#
    # Enqueue 연산: 큐의 뒤에 데이터 추가
    def enqueue(self, item):
        self.queue.append(item)
        print(f"Enqueued {item} to queue")
	#
    # Dequeue 연산: 큐의 앞에서 데이터 제거 및 반환
    def dequeue(self):
        if self.is_empty():
            print("Queue is empty, cannot dequeue")
            return None
        else:
            item = self.queue.pop(0)
            print(f"Dequeued {item} from queue")
            return item
	#
    # Peek 연산: 큐의 앞에 있는 데이터를 반환 (제거하지 않음)
    def peek(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        else:
            return self.queue[0]
	#
    # isEmpty 연산: 큐가 비어 있는지 확인
    def is_empty(self):
        return len(self.queue) == 0
#
# 큐 사용 예시
queue = Queue()
queue.enqueue(1)  # Output: Enqueued 1 to queue
queue.enqueue(2)  # Output: Enqueued 2 to queue
queue.enqueue(3)  # Output: Enqueued 3 to queue
#
print("Front element is:", queue.peek())  # Output: Front element is: 1
#
queue.dequeue()  # Output: Dequeued 1 from queue
queue.dequeue()  # Output: Dequeued 2 from queue
#
print("Front element is:", queue.peek())  # Output: Front element is: 3
#
queue.dequeue()  # Output: Dequeued 3 from queue
queue.dequeue()  # Output: Queue is empty, cannot dequeue

사용 사례

• 프린터의 인쇄 대기열
• 프로세스 관리 : CPU 스케쥴링에서 프로세스 관리
• 너비 우선 탐색(BFS) 알고리즘 : 너비 우선 탐색에서 방문할 노드를 관리

스택 (STACK)이란

후입선출(LIFO : Last In First Out)원칙을 따르는 자료구조이다. 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조로, 책을 쌓아올린 모습과 유사하다.

특징

• 데이터는 한 쪽 끝(top)에서만 삽입과 삭제가 이루어진다.
• 주로 함수 호출, 실행 취소 기능 등에 사용된다.

주요 연산

• Push: 데이터를 스택의 맨 위에 추가한다.
• Pop: 스택의 맨 위에 있는 데이터를 제거하고 반환한다.
• Peek/Top: 스택의 맨 위에 있는 데이터를 제거하지 않고 반환한다.
• IsEmpty: 스택이 비어 있는지를 확인한다.

파이썬에서의 구현

# 스택 생성
stack = []
#
# 요소 추가 (push)
stack.append(1)
stack.append(2)
stack.append(3)
#
# 요소 제거 (pop) 및 출력
print(stack.pop())  # 출력: 3
print(stack.pop())  # 출력: 2
print(stack.pop())  # 출력: 1
'''

스택의 각 주요함수 직접 구현

class Stack:
    def __init__(self):
        self.stack = []
	#
    # Push 연산: 스택에 데이터 추가
    def push(self, item):
        self.stack.append(item)
        print(f"Pushed {item} to stack")
	#
    # Pop 연산: 스택의 가장 위에 있는 데이터 제거 및 반환
    def pop(self):
        if self.is_empty():
            print("Stack is empty, cannot pop")
            return None
        else:
            item = self.stack.pop()
            print(f"Popped {item} from stack")
            return item
	#
    # Peek 연산: 스택의 가장 위에 있는 데이터를 반환 (제거하지 않음)
    def peek(self):
        if self.is_empty():
            print("Stack is empty")
            return None
        else:
            return self.stack[-1]
	#
    # isEmpty 연산: 스택이 비어 있는지 확인
    def is_empty(self):
        return len(self.stack) == 0
#
# 스택 사용 예시
stack = Stack()
stack.push(1)  # Output: Pushed 1 to stack
stack.push(2)  # Output: Pushed 2 to stack
stack.push(3)  # Output: Pushed 3 to stack
#
print("Top element is:", stack.peek())  # Output: Top element is: 3
#
stack.pop()  # Output: Popped 3 from stack
stack.pop()  # Output: Popped 2 from stack
#
print("Top element is:", stack.peek())  # Output: Top element is: 1
#
stack.pop()  # Output: Popped 1 from stack
stack.pop()  # Output: Stack is empty, cannot pop

사용 사례

• 웹 브라우저의 뒤로 가기 기능
• 괄호 검사 알고리즘
• 깊이 우선 탐색(DFS) 알고리즘

데크 (Deque)란

덱(Deque)은 "Double-Ended Queue"의 줄임말로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다. 큐와 스택의 특성을 모두 가지고 있다.

특징

• 양쪽 끝에서 삽입과 삭제가 가능하다.
• 큐와 스택의 기능을 모두 수행할 수 있어 유연히다.

주요 연산

• AddFront: 데이터를 데크의 앞에 추가한다.
• AddRear: 데이터를 데크의 뒤에 추가한다.
• RemoveFront: 데이터를 데크의 앞에서 제거하고 반환한다.
• RemoveRear: 데이터를 데크의 뒤에서 제거하고 반환한다.
• PeekFront: 앞쪽 데이터를 제거하지 않고 반환한다.
• PeekRear: 뒤쪽 데이터를 제거하지 않고 반환한다.

파이썬에서의 구현

from collections import deque
#
# 덱 생성
d = deque()
#
# 요소 추가
d.append(1)      # 오른쪽에 추가
d.appendleft(2)  # 왼쪽에 추가
d.append(3)
#
print(d)  # 출력: deque([2, 1, 3])
#
# 요소 제거
print(d.pop())      # 오른쪽에서 제거, 출력: 3
print(d.popleft())  # 왼쪽에서 제거, 출력: 2
#
print(d)  # 출력: deque([1])
'''

사용 사례

• 덱 기반 캐시 구현 : LRU(Least Recently Used) 캐싱에서 자주 사용됩니다.
• 양방향 탐색 : 데크를 이용해 앞뒤로 탐색이 필요한 알고리즘에서 활용됩니다.
• 작업 스케쥴링