자료구조) Queue와 Stack

Queue와 스택은 둘이 함께 잘 비교가 당한다. 오늘 이 둘을 비교해줘버리자!

Stack

stack은 FILO 구조로, 처음 들어간 요소가 나중에 나중에 나오는 구조, 나중에 들어간 요고가 처음으로 나오는 구조이다. 

stack은 요소를 삽입할때 push, 요소를 빼낼때 pop 라고한다. 둘 모두 맨 마지막에 요소를 빼고, 넣기 때문에 O(1)이다. 

스택은 대부분 array로 구현하는데, array로 구현하기 때문에, 데이터 최대 갯수를 미리 상정해 놔야 해서, 메모리 낭비가 있을 수 있다. 

또한, 스택은 재귀적인 특성을 가지기도 하는데, 재귀적인 형태로 구현을 한다면 파이썬의 경우 1000개의 데이터 까지 넣을 수 있다. 

def recursive_stack(data):
	if data <0 :
    	print(end)
    else:
    	print(data)
        reculsiv(data-1)
        print("returned", data)

이런 구조의 스택은 컴퓨터 내부 프로세스 구조, 괄호 유효성 검사, 웹브라우저 방문기록(뒤로가기), 깊이 우선 탐색(DFS)에 사용된다. 

 

파이썬에서 스택은 List로 만들 수 있다. push는 list.append(data)로 pop은 list.pop() 으로 가능하다. 

Queue

Queue는 Stack과 달리 FIFO 구조로, 처음 들어간 요소가 처음 나오는 구조이다. 

Queue를 삽입할때 Enqueue, 요소를 빼낼때 Dequeue라고 한다. Enqueue는 맨 뒤에 요소를 추가하는 것이고, Dequeue는 맨 앞의 요소를 빼내는 것이다. 

 

큐의 구현 방식은 Array-Based Queue, List-Based Queue가 있다. 

Array-Based Queue는 Array를 기반으로 만드는 것으로, Enque, Dequeue가 발생하면서 메모리가 낭비될 수 있기 때문에, Dequeue되어 빈 공간에 Enqueue하는 Circular Queue 형태로 구현하기도 한다. 물론 기존의 Array처럼 Enqueue할 공간이 부족하면 Dynamic Array 방식으로 resize하기도 한다. - Enqueue, Dequeue 모두 O(1)

List-Based Queue는 Single-Linked-List를 이용해 만드는 것으로, Enqueue의 경우, 맨 뒤 node에 데이터를 달아주고, Dequeue의 경우 head를 삭제하는 식으로 구현하기 때문에 O(1)이다. 

둘의 구현 방식은 달라도 Enqueue, Deuqueue 모두 O(1)임을 알 수 있다. 다만 Array-Based-Queue의 경우 전반적인 퍼포먼스는 좋으나, resize할 경우 급격하게 퍼포먼스가 떨어진다. List-Based-Queue의 경우 runtime마다 메모리를 할당받아서, 전반적인 런타임이 느릴 수 있다. 

 

Queue에는 여러 종류가 있는데, 

앞 뒤, 모두에서 삽입과 꺼내는 것이 가능한 Deque, 우선순위가 높은 것에 따라 더 먼저 꺼내지는 우선순위 큐(Priority Queue)가 있다. 

 

이런 큐는 프린터, CPU 등의 task Scheduling, BFS(너비 우선 탐색), 캐시 구현, 프로세스 관리 등에서 활용될 수 있다 

 

파이썬에는 Queue라는 라이브러리가 있어서 이것을 활용할수 있다. 

Queue 라이브러리에는 Queue(일반 큐), LifoQueue(스택과 같은 형태), PriorityQueue(우선 순위 큐)가 있다.

이 라이브러리를 이용할때 Enqueue는 put, Dequeue는 get을 사용한다. 

import queue

Queue1 = queue.Queue()

#Enqueue
Queue1.put(2)

#Dequeue
Queue1.get()

#size
Qeueu1.qsize()

Priority Queue의 경우 put을 할때 튜플형태로(우선순위, 데이터)를 넣는다. 

특히 Priority Queue는 (min)Heap과 완전 수행 방식이 동일하기 때문에 Heap을 살펴볼때 다시 자세히 봐보자 

 

Stack으로 Queue 구현하기, Queue로 Stack 구현하기

앞서서 둘이 자주 비교당한다 했는데, 비교당하면 애증의 관계라도 되나보는지, 서로로 서로를 구현할 수 있다. 

Stack으로 Queue 구현하기 

Stack은 FILO로 Queue는 FIFO를 구현하려고 한다면 스택 2개를 만들어서 한개에 요소를 쌓고, pop을 해야할때 다른 스택에 요소를 다 옮긴다음에 pop을 해주면 된다. 

class Queue(feat.Stack):
	def __init__(self) :
    	enStack = []
        deStack = []
        
    def Enqueue(feat.Stack)(self, data):
    	self.enStack.append(data)
    
    def Dequeue(feat.Stack)(self):
    	if not self.deStack: #deStack이 비었을때 
        	while enStack : # enStack이 빌때까지
            	self.destack.append(self.enStack.pop())
        return self.deStack.pop()

이렇게 만들었을 때, Enqueue는 O(1)이다. Dequeue할 때 DeStack이 비어있다면, EnStack에서 다 옮겨줘야 하니 O(n)이 걸리는데 , 일반적으로 pop만 해줄때는 O(1)이 걸린다고 볼 수 있으니, amortize O(1)이라고 볼 수 있다. 

 

Queue로 Stack 만들기 

FIFO인 Queue로 Stack을 만들기 위해서는 두개의 Queue를 사용해서 한 큐에다가 Enqueue하고, pop을 해야할때 Enqueue로 썼던 Queue에서 최근 한개를 남기고 모두 다른 Queue에 넣은 후 dequeue 해준다. 또 pop해야하기 때문에 queue 두개의 이름을 바꾸어 다시 반복한다. 

import queue

class Stack(feat.Queue):
	def __init__(self):
    	q1 = queue.Queue()
    	q2 = queue.Queue()
    
    def push(feat.Queue)(self, data):
    	self.q1.put(data)
        
    def pop(feat.Queue)(self):
    	while self.q1.qsize == 1 :
        	self.q2.put(self.q1.get())
        
        temp = self.q1
        self.q1 = self.q2
        self.q2 = temp
        
        return self.q2.get()

이 경우, push의 경우 그냥 Enqueue만 하면 되니 O(1)이지만 Dequeue의 경우 1개 빼고 n-1을 다른 Queue로 옮겨야 하니 O(n)이다.