파이썬 스택큐 구현하기 (자료구조 변환)

파이썬 스택큐 구현하기 (자료구조 변환) — #파이썬 #파이썬스택 #파이썬큐 #스택큐 #자료구조변환 #자료구조 AI스쿨 msa기반 java 백엔드 코스 중에...

#자료구조#Naver Blog

#파이썬 #파이썬스택 #파이썬큐 #스택큐 #자료구조변환 #자료구조

AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다

자료구조 변환

이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.

예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.

스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.

스택큐 구현하기
StackQueue

큐의 마지막 시리즈 스택으로 큐를 구현합니다. 스택과 큐의 기능은 이전글을 참고해주세요..

사용할 스택

이전글 을 통해 구현한 스택을 사용합니다.

# 스택class Stack: def \_\_init\_\_(self): self.data = \[\] def push(self, value): self.data.append(value) def pop(self): if len(self.data) == 0: return None last\_value = self.data.pop() return last\_value def len(self): return len(self.data)

기존 구현된 스택에서 스택의 크기를 구하는 len()함수를 추가하였습니다. 이 기능은 StackQueue에서 요긴하게 쓰이게 됩니다.

스택큐(StackQueue) idea
두개의 스택 사용하기

이전글(링크 필요)을 통해 큐스택을 구현하는 방법을 배웠는데요. 큐스택을 구현한 방법과 매우 비슷합니다!

바로 스택 2개를 사용하여 한쪽에만 값을 차례대로 쌓습니다. 그럼 맨처음 들어간 값이 맨 안쪽에 쌓이게됩니다.

구현할 StackQueue는 본질은 Queue이기 떄문에 pop()을 사용할 경우 맨 처음에 넣은 값을 밖으로 빼줘야 합니다. (FIFO)

맨처음 이전까지의 값을 모두 stack2로 옮기고(stack1.pop() -> stack2) , stack1의 처음값을 반환(stack1.pop())해주면 됩니다.

이후 본래대로 자료를 유지하기 위해 다시 stack2 -> stack1으로 값을 이동해주면 됩니다.

스택큐(StackQueue) 선언하기
\_\_init\_\_

class StackQueue: def \_\_init\_\_(self): self.stack1 = Stack() self.stack2 = Stack() def push(self, value): pass def pop(self): pass

StackQueue를 구현하기 위한 stack 두개를 선언해줍니다.

StackQueue,push()
스택큐

class StackQueue: def \_\_init\_\_(self): self.stack1 = Stack() self.stack2 = Stack() def push(self, value): self.stack1.push(value) def pop(self): pass

딱히 틀별할 것없이 stack1에 데이터를 넣기만 하면 됩니다.

StackQueue.pop()
스택큐 pop()

위에서 고안한 idea처럼 스택큐를 만들어 봅시다! 이때 Stack에 미리 만들어둔 len()함수를 활용하여 stack1에 값을 하나 남길 수 있습니다.

class StackQueue: def \_\_init\_\_(self): self.stack1 = Stack() self.stack2 = Stack() def push(self, value): self.stack1.push(value) def pop(self): for i in range(self.stack1.len() - 1): self.stack2.push(self.stack1.pop()) first\_value = self.stack1.pop() for i in range(self.stack2.len()): self.stack1.push(self.stack2.pop()) return first\_value

stack1에서 가장 첫번째 요소 빼고 모두 stack2로 옮겨줍니다. 이후 가장 첫번째 요소를 first\_value 변수로 담고 함수의 마지막에 반환합니다.

stack2에 옮긴 요소들은 다시 stack1에 삽입해주면 됩니다. stack1의 요소가 거꾸로(맨끝에서 부터) 담겨있으니 stack1으로 옮길떄는 정상적인 순서대로 들어갑니다.

자료구조 총정리