스택, 큐, 덱

스택(Stack)

쌓여 있는 책/상자 같은 입출력 구조

 

후입선출 구조

마지막으로 들어온 데이터가 가장 위에 쌓이게 되고 가장 먼저 나간다.

 

<예시>

Stack에 A,B,C,D 순서대로 삽입 -> 삭제 연산 진행

 

입출력

 

연산은 스택의 맨 위에서만 발생 , 중간에 삽입/삭제 불가 

• top (스택 상단) : 스택의 맨 윗 부분, 입출력이 이루어짐 
• bottom (스택 하단) : 스택의 바닥 부분 
• element (요소) : 스택에 저장되는 데이터 
• empty stack (공백 스택) : 요소가 없는 스택 -> 입출력 불가

 

자료의 출력이 입력의 역순으로 이루어져야 할 경우에 유용

 

<스택 기본 동작 구현>

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)

 

스택과 반대로 먼저 들어온 데이터가 먼저 나가는 자료구조

 

선입선출 구조

뒤에서 새로운 데이터 추가 ,앞에서 데이터가 차례로 삭제

 

스택 vs 큐 

 

스택 - 삽입/삭제가 같은 쪽에서 진행

큐 - 삽입/삭제가 서로 다른쪽에서 진행

 

<예시>

Queue에 A,B,C,D 순서대로 삽입 -> 삭제 연산 진행

 

Class Queue:
 	def __init__(self):
 		self.items = [] #데이터 저장을 위한 리스트 준비
def enqueue(self, val):
      self.items.append(val)
 	def dequeue(self):
 		try: #pop할 아이템이 없으면
 			return self.items.pop(0)
 		except IndexError: #indexError 발생
 			print("Queue is empty")

def front(self):
 		try:
 			return self.items[0]
 		except IndexError:
 			print("Queue is empty")

	def __len__(self): # len()로 호출하면 queue의 item 수 반환
	 		return len(self.items)

def isEmpty(self):
 		return len(self)

 

원형큐

 

deque.rotate()를 사용해서 리스트 회전하기

리스트 자료형을 deque자료형으로 바꾼후 rotate()함수를 이용하면 된다. 함수안에 음수를 넣게 된다면 왼쪽회전 양수는 오른쪽회전이다.

 

>>> from collections import deque
>>> test = [1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> test = deque(test)
>>> test.rotate(2) 
>>> result = list(test)
>>> result
[8, 9, 1, 2, 3, 4, 5, 6, 7]

위 결과를 보게되면 rotate(2)를 함으로 오른쪽으로 2만큼 회전한것을 볼 수 있다.

 

덱(Dequeue)

 

두 가지 자료구조(스택 & 큐)의 기능을 합쳐놓은 자료구조

 

스택과 큐의 연산을 모두 지원하는 자료구조

왼쪽과 오른쪽 양쪽에서 삽입/삭제 가능

 

<파이썬 - collections 모듈의 deque 클래스 >

>>>from collections import deque
>>>d = deque('ghi') #deque  생성
>>>d.append('j') #오른쪽에 j  삽입
>>>d.appendleft('f') #왼쪽에 f 삽입
>>>d 
   deque(['f','g','h','i','j']) 
>>>d.pop() #가장 오른쪽 값 가져오기 
   ‘j’
>>>d.popleft() #가장 왼쪽 값 가져오기
   'f' 
>>>list(d) #리스트로 변환
   [‘g’,’h’,’i’]