파이썬스택배열 구현하기 (자료구조 변환)
파이썬스택배열 구현하기 (자료구조 변환) — #파이썬배열 #파이썬스택배열 #스택배열 #자료구조변환 #스택으로배열 AI스쿨 msa기반 java 백엔드 코스 ...
#파이썬배열 #파이썬스택배열 #스택배열 #자료구조변환 #스택으로배열
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
자료구조 변환
이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.
예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.
스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.
스택으로 배열 구현하기
StackArray
이번에는 스택을 사용하여 배열을 구현해보겠습니다. 배열과 스택의 기능은 이전글을 참고해주세요.
이전글인 ArrayStack과 비교하면서 보셔도 좋을 것 같네요 :D
사용할 스택
이전글을 통해 구현한 스택을 가져왔습니다. 스택의 기본기능에 len()함수를 추가하였습니다.
| 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) |
|---|
StackArray 선언하기
\_\_init\_\_
| class StackArray: def get(self, idx): pass def set(self, idx, value): pass def \_\_init\_\_(self, size): self.stack1 = Stack() self.stack2 = Stack() for i in range(size): self.stack1.push(None) |
|---|
StackArray역시 배열이기 때문에 크기를 먼저 설정해줘야합니다. 우선 모든 요소들을 stack1에 다 담았습니다.
StackArray.get(idx)
idea
get함수를 구현하기 이전에 먼저 아이디어를 떠올려봅시다. 모든 요소가 stack1에 일단 들어가 있습니다.
get(idx)변수가 들어오면, 끝에서부터 stack1.pop()을 실행하여 stack2에 push해줍니다.
이후 stack1.pop()값을 외부로 반환하고, 바로 다시 넣습니다. 이후에는 stack2.pop()을 실행한 값들을 stack1에 다시 push해줍니다.
| class StackArray: def get(self, idx): for i in range(self.stack1.len(), idx + 1, -1): self.stack2.push(self.stack1.pop()) self.get\_value = self.stack1.pop() self.stack1.push(self.get\_value) for i in range(self.stack2.len()): self.stack1.push(self.stack2.pop()) return self.get\_value def set(self, idx, value): pass def \_\_init\_\_(self, size): self.stack1 = Stack() self.stack2 = Stack() for i in range(size): self.stack1.push(None) |
|---|
원하는 idx까지 pop()을 실행해야 하기 때문에 범위를 끝에서 부터 뺐습니다. 크기가 10인 배열의 idx =3은 4번째에 위치합니다. 6번만 pop()을 실행해줘야 하기 때문에 크기 - (idx + 1)번 실행되도록 반복문의 범위를 정해줘야합니다.
StackArray.set(idx, value)
idea
StackArray.get()을 완성했다면 set은 간단합니다. idx에 위치한 stack1의 값을 바꿔서 다시 넣어주면 되기 때문입니다!
| class StackArray: def get(self, idx): for i in range(self.stack1.len(), idx, -1): self.stack2.push(self.stack1.pop()) self.get\_value = self.stack1.pop() self.stack1.push(self.get\_value) for i in range(self.stack2.len()): self.stack1.push(self.stack2.pop()) return self.get\_value def set(self, idx, value): for i in range(self.stack1.len(), idx + 1, -1): self.stack2.push(self.stack1.pop()) self.set\_value = self.stack1.pop() self.set\_value = value self.stack1.push(self.set\_value) for i in range(self.stack2.len()): self.stack1.push(self.stack2.pop()) def \_\_init\_\_(self, size): self.stack1 = Stack() self.stack2 = Stack() for i in range(size): self.stack1.push(None) |
|---|
중간에 set\_value를 value로 바꾼 것을 잘 확인하시면 될 것 같습니다 :D
자료구조 총정리