stack 2개로 queue 만들기

stack 2개를 이용하면 queue를 만들 수 있다.

 

stack은 LIFO (Last In First Out)

queue 는 FIFO (First In First Out)

 

즉, stack을 두개를 이용해서 빈 스택에 다른 스택을 담고 다시 빼는 식으로 queue를 만들 수 있는 것이다.

 

구현 코드 예시

# stack 2개로 queue 만들기
class Stack:
    def __init__(self):
        self.stack = []
        
    def __repr__(self):
        return f"{self.stack}"
    
    def push(self,item):
        self.stack.append(item)
        
    def pop(self):
        return self.stack.pop()
        
    def is_empty(self):
        if len(self.stack) == 0 : return True
        else : return False
 
 
st = Stack()
st.push(1)
st.push(2)
st.push(3)

print(st)
[1,2,3]
st.pop()
3
print(st)
[1,2]


class Queue:
    def __init__(self):
        self.qu = Stack()
        self.stack2 = Stack()
    
    def __repr__(self):
        return f"{self.qu}"
        
    def push(self,item):
        self.qu.push(item)
        self.que = self.qu
        
    def pop(self):
        while not self.qu.is_empty():
            self.stack2.push(self.qu.pop())
        
        result = self.stack2.pop()
        
        while not self.stack2.is_empty():
            self.qu.push(self.stack2.pop())
        
        return result


qu  = Queue()
qu.push(1)
qu.push(2)
qu.push(3)

print(qu)
[1,2,3]
qu.pop()
1
print(qu)
[2,3]