파이썬 큐스택 구현하기 (자료구조의 변환)
파이썬 큐스택 구현하기 (자료구조의 변환) — #파이썬큐 #파이썬스택 #파이썬큐스택 #큐스택구현하기 #자료구조변환 AI스쿨 msa기반 java 백엔드 코스 ...
#파이썬큐 #파이썬스택 #파이썬큐스택 #큐스택구현하기 #자료구조변환
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
자료구조 변환
이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.
예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.
스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.
큐스택
QueueStack
마지막으로 Queue를 사용하여 스택을 구현합니다. 큐와 스택의 기능은 이전글을 참고해주세요.
QueueStack(큐스택) idea
처음에 큐스택을 구현하는 방법이 떠오르지 않을 수 있습니다. 본격적으로 코드를 들어가기에 앞서 먼저 큐스택을 구현하는 아이디어를 생각해봅시다.
2개의 큐를 사용합니다. 첫번째 queue1에만 값을 push합니다.
이후 QueueStack에서 pop()을 실행할 경우 queue1에서 마지막 요소빼고 모두 queue2로 옮겨줍니다. 그러고 queue1에서 마지막 요소를 꺼냅니다. queue2에 옮겨진 값은 다시 queue1으로 넣습니다.
사용할 Queue
이전글을 통해 구현한 큐를 가져왔습니다.
| class Queue: def \_\_init\_\_(self): self.data = \[\] def push(self, value): self.data.append(value) def pop(self): # 처음 넣은 값 삭제,, first\_value = self.data.pop(0) return first\_value def len(self): return len(self.data) |
|---|
추가로 len()함수를 queue의 기능으로 추가하였습니다. len()함수는 해당 queue 데이터의 크기를 반환합니다. 큐 -> 큐로 데이터를 옮길때 요긴한게 사용될 예정입니다.
큐스택 선언하기
QueueStack()
| class QueueStack: def \_\_init\_\_(self): self.queue1 = Queue() self.queue2 = Queue() def push(self, value): pass def pop(self): pass |
|---|
우선 앞서서 고안한 아이디어대로 queue 두개를 선언합니다. queue1을 push용으로 사용합니다.
큐스택 push
QueueStack.push(value)
| class QueueStack: def \_\_init\_\_(self): self.queue1 = Queue() self.queue2 = Queue() def push(self, value): self.queue1.push(value) def pop(self): pass |
|---|
QueueStack에 push를 사용할때 queue1에만 값을 넣습니다.
큐스택 pop
QueueStack.pop()
| class QueueStack: def \_\_init\_\_(self): self.queue1 = Queue() self.queue2 = Queue() def push(self, value): self.queue1.push(value) def pop(self): for i in range(self.queue1.len() - 1): self.front\_value = self.queue1.pop() self.queue2.push(self.front\_value) self.last\_value = self.queue1.pop() for i in range(self.queue2.len()): self.queue1.push(self.queue2.pop) return self.last\_value |
|---|
QueueStack에 pop()을 사용하면 위에서 제시한 idea대로 구현을 완료하였습니다. queue2에 담은 값은 다시 queue1에 넣어줘야 한다는 점을 잊지 마세요!
queue1의 마지막 값은 출력해줍니다.
자료구조 총정리