[Data Structure] Stack & Queue & Deque

in Computer Science on Data Structure


제한된 접근(삽입, 삭제)만 허용 (Stack, Queue, Dequeue 모두 동일)

출처 : https://gohighbrow.com/stacks-and-queues/
스택과 큐의 구조를 가장 잘 보여주는 예시

Stack 스택

class Stack:
    def __init__(self):
        self.items = [].  #데이터 저장을 위한 리스트 준비
    
    def push(self, val):
        self.items.append(val)

    def pop(self):
	try:
	    return self.items.pop()   #pop할 item이 없으면
	except IndexError:
	    print("Stack is empty")   #indexError 발생
    
    def top(self):
        try:
	    return self.items[-1]
	except IndexError:
	    print("Stack is empty")

    def __len__(self):
        return len(self.items)   #len()로 호출하면 Stack의 item 수 반환
파이썬에서 스택은 범용 자료구조인 List를 활용하여 사용할 수 있다.

특징

  • LIFO : Last In First Out
  • 가장 최근에 push된 요소가 먼저 pop된다 (후입선출)
  • append → push
  • pop → pop

활용 예시

  • 웹 브라우저 뒤로 가기 : 가장 최근에 열린 페이지부터 다시 보여줌
  • 실행 취소 (Ctrl + Z) : 가장 나중에 실행된 작업을 되돌려줌

Queue 큐

class Queue:
    def __init__(self):
        self.items = []   #빈 리스트
	self.front_index = 0
	
    def enqueue(self, val):
	self.item.append(val)
	
    def dequeue(self):
	if self.front_index == len(self.items):
	    print("Queue is empty")
	    return None
	else:
	    x = self.items[front_index]
	    self.front_index += 1
	    return x
List를 활용해서 큐를 사용할 수 있는 클래스를 만들 수도 있다.
from queue import Queue

que = Queue()
que.put(val)
que.get()
파이썬에 내장되어 있는 queue 모듈을 활용하여 보다 쉽게 코드를 작성할 수 있다.

특징

  • FIFO : First In First Out
  • enqueue된 순서대로 dequeue된다 (선입선출)
  • front에서 dequeue되고 Rear에서 enqueue된다.
  • append → enqueue → put
  • pop → dequeue → get

queue 모듈의 Queue 클래스에 대한 자세한 내용은 여기 파이썬 공식 레퍼런스 참고

활용 예시

  • 은행 번호표 : 가장 먼저 온 사람의 번호를 먼저 띄워 줌
  • 프린터 인쇄 대기열 : 우선 순위가 같은 작업 중 가장 먼저 들어 온 문서부터 인쇄함

Dequeue (double-end-queue) 덱

from collections import deque

makeDeque()   #덱 생성
appendleft()   #맨 앞(왼쪽)에 자료 추가
pop()   #맨 앞(왼쪽)에 자료 삭제
append()   #맨 뒤(오른쪽)에 자료 추가
popleft()   #맨 뒤(오른쪽)에 자료 삭제deque(maxlen=n)
reverse()   #deque의 순서 뒤집음
count(x)   #deque에 포함된 x의 개수 반환
clear()   #deque 값 모두 삭제
덱은 collections 모듈의 deque 클래스를 활용하면 보다 쉽게 코드를 작성할 수 있다.

특징

  • Stack과 Queue를 합친 형태
  • 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조

list와 deque 비교

시간 복잡도insert, remove, popleftindexing, slicing
listO(n)O(1)
dequeO(n)O(n)

고정된 길이 내에서 접근, 검색, 슬라이싱을 하는 데에는 list가 유리
데이터를 추가 or 삭제할 땐 deque이 유리

참고

신찬수 교수님 유튜브



© 2021. by hminkim