[Python] 스택, 큐, 데크

스택

 

입/출력 한쪽 끝단에서 모두 발생하며, 후입선출 특징을 가지는 자료구조입니다.

 

후입선출(LIFO: Last In First Out) 특성을 가지는 자료구조

 

스택의 기본 연산

- push : 스택의 맨 위의 새로운 요소를 추가
- pop : 스택의 맨 위에 있는 요소를 제거하고 반환
- peek : 스택의 맨 위에 있는 요소를 제거하지 않고 반환
- isEmpty : 스택이 비어있는지 확인

 

 

활용 예시로는 다음과 같이 있습니다.

 

1. 실행취소(Undo) 기능
2. 웹 브라우저의 뒤로가기
3. 함수 호출 스택

 

스택 코드 예시

 

Stack 클래스 구현

 

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()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("peek from empty stack")

    def is_empty(self):
        return len(self.stack) == 0

    def __str__(self):
        return str(self.stack)

 

collections의 deque를 사용하여 구현

 

from collections import deque

if __name__ == "__main__":
    # 스택 생성
    stack = deque()
    
    # push 연산
    stack.append(1)
    stack.append(2)
    stack.append(3)
    
    print("스택 상태:", list(stack)) # 출력: 스택 상태: [1, 2, 3]
    
    # pop 연산
    popped_element = stack.pop()
    print("pop된 요소:", popped_element) # 출력: pop된 요소: 3
    print("스택 상태:", list(stack)) # 출력: 스택 상태: [1, 2]
    
    # peek 연산
    top_element = stack[-1] if stack else None
    print("스택의 최상단 요소:", top_element) # 출력: 스택의 최상단 요소: 2
    print("스택 상태:", list(stack)) # 출력: 스택 상태: [1, 2]
    
    # is_empty 연산
    is_empty = len(stack) == 0
    print("스택이 비어 있는가?", is_empty) # 출력: 스택이 비어 있는가? False

 

---

 

큐(Queue)

 

한쪽에서는 입력만, 안쪽에서는 출력만 일어나는 선입선출 특성의 자료구조입니다.

 

선입선출(FIFO: First In First Out) 특징을 갖는 자료구조

줄을 서는 것과 비슷한 개념으로, 먼저 들어간 데이터가 먼저 출력됩니다.

 

큐의 기본 연산

- enqueue : 큐의 끝에 요소를 추가
- dequeue : 큐의 앞에서 요소를 제거하고 반환

 

 

큐의 활용 예시로는 다음과 같습니다.

 

1. 프린터 대기열 : 먼저 요청된 인쇄 작업부터 차례대로 처리
2. 프로세스 스케줄링
3. 데이터 스트림 처리

 

큐 예시 코드

 

Queue 클래스 구현

 

class Queue:
	  def __init__(self):
	      self.items = []
	
	  def enqueue(self, item):
	      self.items.append(item)
	
	  def dequeue(self):
	      if not self.is_empty():
	          return self.items.pop(0)
	      else:
	          raise IndexError("dequeue from empty queue")
	
	  def peek(self):
	      if not self.is_empty():
	          return self.items[0]
	      else:
	          raise IndexError("peek from empty queue")
	
	  def is_empty(self):
	      return len(self.items) == 0
	
	  def __str__(self):
	      return str(self.items)

 

collections의 deque를 활용하여 queue 구현

 

from collections import deque

# 큐 생성
queue = deque()

# enqueue 연산
queue.append(1)  # 또는 queue.append(1)
queue.append(2)  # 또는 queue.append(2)
queue.append(3)  # 또는 queue.append(3)

print("큐 상태:", list(queue))  # 출력: 큐 상태: [1, 2, 3]

# dequeue 연산
removed_element = queue.popleft()  # 또는 queue.popleft()
print("제거된 요소:", removed_element)  # 출력: 제거된 요소: 1
print("큐 상태:", list(queue))  # 출력: 큐 상태: [2, 3]

# peek 연산
front_element = queue[0] if queue else None  # 또는 queue[0] if queue else None
print("큐의 앞에 있는 요소:", front_element)  # 출력: 큐의 앞에 있는 요소: 2
print("큐 상태:", list(queue))  # 출력: 큐 상태: [2, 3]

# isEmpty 연산
is_empty = len(queue) == 0
print("큐가 비어 있는가?", is_empty)  # 출력: 큐가 비어 있는가? False

 

---

 

데크(Deque)

 

큐와 유사하지만 양쪽 끝단에서 모두 입출력이 가능한 자료구조입니다.

 

양쪽 끝에서 데이터 추가 및 제거 가능: 앞쪽이나 뒤쪽에서 데이터를 넣고 뺄 수 있습니다.

유연한 자료구조 : 덱은 스택처럼 사용할 수도, 큐처럼 사용할 수도 있습니다.

 

데크의 기본 연산

- addFirst(e) : 요소를 데크의 앞에 삽입합니다.
- addLast(e) : 요소를 데크의 뒤에 삽입합니다.
- removeFirst() : 데크의 앞에서 요소를 제거하고 반환합니다.
- removeLast() : 데크의 뒤에서 요소를 제거하고 반환합니다.
- peekFirst() : 데크의 앞 요소를 제거하지 않고 반환합니다.
- peekLast() : 데크의 뒤 요소를 제거하지 않고 반환합니다.

 

 

데크 예시 코드

 

from collections import deque


# Deque 생성
deque_obj = deque()

# 앞에 요소 추가
deque_obj.appendleft(1)
deque_obj.appendleft(2)
deque_obj.appendleft(3)
print("Deque 상태 (앞에 추가):", list(deque_obj))  # 출력: [3, 2, 1]

# 뒤에 요소 추가
deque_obj.append(4)
deque_obj.append(5)
print("Deque 상태 (뒤에 추가):", list(deque_obj))  # 출력: [3, 2, 1, 4, 5]

# 앞에서 요소 제거
front = deque_obj.popleft()
print("앞에서 제거된 요소:", front)  # 출력: 3
print("Deque 상태 (앞에서 제거):", list(deque_obj))  # 출력: [2, 1, 4, 5]

# 뒤에서 요소 제거
back = deque_obj.pop()
print("뒤에서 제거된 요소:", back)  # 출력: 5
print("Deque 상태 (뒤에서 제거):", list(deque_obj))  # 출력: [2, 1, 4]

# 앞 요소 확인
peek_front = deque_obj[0] if deque_obj else None
print("앞 요소:", peek_front)  # 출력: 2

# 뒤 요소 확인
peek_back = deque_obj[-1] if deque_obj else None
print("뒤 요소:", peek_back)  # 출력: 4

# 비어 있는지 확인
is_empty = len(deque_obj) == 0
print("Deque가 비어 있는가?", is_empty)  # 출력: False