14. 큐

 FIFO(first in first out)로 처리되는, 줄을 서는 것에 비유할 수 있는 큐는 상대적으로 스택에 비해서는 쓰임새가 적다. 그러나 스택에 비해서 그렇다는 얘기일 뿐, 이후에 살펴보게 될 데크나 우선순위 큐 같은 변형들은 여러 분야에서 매우 유용하게 쓰인다.

 

 

1. 큐를 이용한 스택 구현

 - push() 할 때 큐를 이용해 재정렬

class MyStack:
    def __init__ (self):
        self.q=collections.deque()
        
    def push(self,x):
        self.q.append(x)

        # 요소 삽입 후 맨 앞에 두는 상태로 재정렬
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()
    
    def top(self):
        return self.q[0]

    def empty(self):
        return len(self.q)==0

 

2. 스택을 이용한 큐 구현

 이 문제를 스택의 연산만을 사용해서 풀기 위해서는 2개의 스택이 필요하다.

class MyQueue:
    def __init__ (self):
        self.input=[]
        self.output=[]

    def push(self,x):
        self.input.append(x)

    def pop(self):
        self.peek()
        return self.output.pop()

    def peek(self):
        # output이 없으면 모두 재입력
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        
        return self.output[-1]

    def empty(self):
        return self.input==[] and self.output==[]

 

 

3. 원형 큐 디자인

 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작 위치와 연결되는 다음 그림과 같은 원형 구조를 띠기 때문에 링 버퍼라고도 부른다.

class MyCircularQueue:
    def __init__ (self,k):
        self.q=[None] * k
        self.maxlen=k
        self.p1=0
        self.p2=0

    # enQueue(): rear 포인터 이동
    def enQueue(self,value):
        if self.q[self.p2] is None:
            self.q[self.p2]=value
            self.p2=(self.p2 + 1) % self.maxlen
            return True

        else:
            return False
        
    # deQueue(): front 포인터 이동
    def deQueu(self):
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1]=None
            self.p1=(self.p1 + 1) % self.maxlen
            return True

    def Front(self):
        return -1 if self.q[self.p1] is None else self.q[self.p1]

    def Rear(self):
        return -1 if self.q[self.p2 -1] is None else self.q[self.p2 - 1]

    def isEmpty(self):
        return self.p1==self.p2 and self.q[self.p1] is None