[자료구조] 스택, 큐, 덱(Stack, Queue, Dequeue)

스택, 큐, 덱이란?

• 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료구조이다.
• (배열/리스트와 유사하게) 값을 저장(insert 또는 set)하는 연산과 저장된 값을 꺼내는(remove 또는 get) 연산이 제공된다. 그러나 매우 제한적인 규칙(LIFO, FIFO)등을 따른다.

 

스택(Stack): LIFO - 후입선출

• 스택은 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 저장된 값이 먼저 나간다. - LIFO(Last In First Out) 원칙
• 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다.

https://medium.com/@1991dharapatel/javascript-stacks-and-queues-136fabab8359

class Stack:
	def __init__(self):
		self.items = []	# 데이터 저장을 위한 리스트 준비
	def push(self, val):
		self.items.append(val)
	def pop(self):
		try:	# pop할 아이템이 없으면
			return self.items.pop()
		except IndexError:	# indexError 발생
			print("Stack is empty")
	def top(self):
		try:
			return self.items[-1]
		except IndexError:
			print("Stack is empty")
	def __len__(self):	# len()로 호출하면 stack의 item 수 반환
 		return len(self.items)
	def isEmpty(self):
		return self.__len__() == 0

 

큐(Queue): FIFO - 선입선출

• 큐는 스택과 동일하게 가장 최근에 저장된 값 다음에 새로운 값이 저장되지만 가장 오래전에 저장된 값부터 나간다는 차이가 있다. - FIFO(First In First Out, 선착순) 원칙
• 스택과 마찬가지로 리스트는 큐의 모든 연산을 지원하지만, 리스트는 동적 배열로 구현되어 큐의 연산을 수행하기엔 효율적이지 않다. 따라서 파이썬에서 큐를 구현할 땐 후술할 덱을 사용한다.

https://medium.com/@1991dharapatel/javascript-stacks-and-queues-136fabab8359

class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self,val):
        self.items.append(val)
    def dequeue(self):
        try:
            return self.items.pop(0)
        except IndexError:
            print("Queue is empty")
    def front(self):
        try:
            return self.items[0]
        except IndexError:
            print("Queue is empty")
    def __len__(self):
        return len(self.items)
    def isEmpty(self):
        return len(self)

 

덱(Dequeue): Stack + Queue

• 덱은 스택과 큐의 연산을 모두 지원하는 자료구조이다.
• 왼쪽과 오른쪽에서 모두 삽입과 삭제가 가능한 큐다.
• 파이썬에선 collections라는 모듈에 deque란 클래스로 덱이 이미 구현되어 있다.

deque class

https://commons.wikimedia.org/wiki/File:Deque.gif

참고

Data Structures with Python(신찬수 저)

파이썬 알고리즘 인터뷰(박상길 저)