ch9-4(leetcode 225). 큐를 이용한 스택 구현

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 225번 ( https://leetcode.com/problems/implement-stack-using-queues/description/ )

 

풀이방법.

보통 큐나 스택은 배열이나 연결 리스트(linked-list)로 많이 구현하는데, 이 문제는 특이하게 스택을 큐로 구현하는 문제였다. 큐와 스택은 배열이나 연결 리스트처럼 실제로 구현된 자료구조 형태가 아닌 추상적인 자료구조(ADT, abstract data types)이다. 그래서 실제 사용할 때는 다른 자료구조를 이용하여 구현한다. 

 

파이썬에는 스택의 push()와 pop(), 큐의 enqueue(), dequeue() 메소드가 모두 구현된 데크(deque) 자료형이 있다. 그러나 이 문제에서는 큐 ADT에서만 사용할 수 있는 메소드(enqueue, dequeue)만 가지고 스택을 구현해야 한다. 

 

데크에서는 popleft(), append()가 각각 enqueue(), dequeue()와 같은 기능을 한다.

 

스택과 큐는 원소를 추가할 때는 리턴되는 값이 없고 원소를 빼낼 때 값을 리턴하는데, 리턴하는 값의 순서가 다르다. 그러므로 원소를 넣을 때나 뺄 때 추가로 정렬 작업이 필요하다. 

여기서는 원소를 넣을 때 정렬 작업을 해 주었다. 

class Stack:
	
	def __init__(self):
		self.queue = collections.deque()
        
	def push(self, val):
		self.queue.append(val)
		self.queue.append(self.queue.popleft())
            
	def pop(self):
		return self.queue.popleft()
        
	def peek(self):
		return self.queue[0]
        
	def empty(self):
		return len(self.queue) == 0