자료구조 03. Stack으로 Queue구현하기

2019.03.28 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. Stack 2개로 queue 구현하기

Stack와 Queue

• Stack과 Queue는 모두 컴퓨터 자료구조 방법론에 해당한다.

• Stack : LIFO (last in first out) 후입 선출

• Stack의 ADT (operation list , operation의 시그니처만 나열)

  1. S.empty() --> Boolean (스택이 비어있으면 True, 아니면 False)
  2. S.push(data) ---> None (스택의 맨 위에 데이터를 쌓는다.) None->무조건들어간다
  3. S.pop() ---> data (스택 맨 위의 데이터를 삭제하면서 반환)
  4. S.peek() ---> data (스택 맨 위의 데이터를 반환)

• Queue : FIFO (first in first out) 선입 선출

• Queue의 ADT (operation list , operation의 시그니처만 나열)

  1. Q.empty() —> Boolean (큐가 비어있으면 true, 비어있으면 False)
  2. Q.enqueue(data) —> None (큐의 맨 뒤에 데이터를 쌓는다.)
  3. Q.dequeue(data) —> data (큐의 맨 앞에 데이터를 삭제하면서 반환)
  4. Q.peek() —> data (큐의 맨 앞의 데이터를 반환)

Stack의 ADT 구현

• ADT 구현

>>>class Stack:
>>>    def __init__(self):
>>>        self.container=list()
>>>
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>
>>>    def push(self, data):
>>>        self.container.append(data)
>>>
>>>    def pop(self):
>>>        return self.container.pop()
>>>
>>>    def peek(self):
>>>        return self.container[-1]

위와 같이 스택의 ADT를 표시할 수 있다.

Queue의 ADT 구현

• ADT 구현

>>>class Queue:
>>>
>>>    def __init__(self):
>>>        self.container = list() 
>>>    
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>    def enqueue(self, data):
>>>        self.container.append(data)
>>>
>>>    def dequeue(self):     
>>>        return self.container.pop(0)
>>>
>>>    def peek(self):
>>>        return self.container[0]

위와 같이 Queue의 ADT를 표시할 수 있다.

Stack 2개로 Queue 구현하기

• 2개의 Stack을 활용하여 Queue의 ADT를 구현해야 한다.
• Stack의 ADT를 활용할 수 있다.
• 1개의 자료는 Stack을 Stack1 --> Stack2로 한번만 이동가능하다.
• 같은 폴더 안에 Stack의 ADT가 저장되어 있다고 가정(import 사용)

실제 구현

>>> from stack import Stack 
>>>
>>> class Queue:
>>>     
>>>        def __init__(self):
>>>            self.stack1 = Stack()
>>>            self.stack2 = Stack()
>>>
>>>        def empty(self):
>>>            if self.stack1.empty() and self.stack2.empty():
>>>                return True
>>>            else:
>>>                return False
>>>
>>>        def enqueue(self, data):
>>>            self.stack1.push(data)
>>>
>>>        def dequeue(self):
>>>            if self.stack2.empty():
>>>                while not self.stack1.empty():
>>>                    self.stack2.append(stack1.pop())
>>>            return self.stack2.pop()
>>>
>>>        def peek(self):
>>>            if self.stack2.empty():
>>>                while not self.stack1.empty():
>>>                    self.stack2.append(self.stack1.pop())
>>>            return self.stack2.peek()
>>>
>>>
>>> if __name__ == "__main__":
>>>        Que = Queue()
>>>        for i in range(10):
>>>            Que.enqueue(i)        
>>>        
>>>        print(Que.peek())
>>>        print(Que.dequeue())
>>>        print(Que.dequeue())
>>>        Print(Que.empty())
>>>        print(Que.enqueue(10))
>>>        print(Que.dequeue())
>>>        
0
0
1
False
None
2

이해하기가 쉽지 않다면 유튜브 영상을 추천한다.

[추천 참고 영상] (https://youtu.be/t45d7CgDaDM)