Byeonguk Kim

안녕하세요. 29살의 조금은 늦은 나이로 새롭게 개발자로 시작하는 신입 개발자입니다. 포트폴리오 [https://deaguowl.github.io]

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

28 Mar 2019 » 자료구조

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)

Related Posts