파이썬 배열로 스택 구현하기 (자료구조의 변환)
파이썬 배열로 스택 구현하기 (자료구조의 변환) — #파이썬배열스택 #배열로스택 #자료구조 #배열스택 AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을...
#파이썬배열스택 #배열로스택 #자료구조 #배열스택
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
자료구조 변환
이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.
예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.
스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.
배열로 스택 구현하기
ArrayStack
배열을 사용하여 스택을 구현합니다. 배열과 스택의 기능은 이전글을 참고해주세요.
"배열로 스택을 구현한다"는 개념이 처음에는 잘 잡히지 않으리라 생각됩니다. 하다보면 감이 좀 잡히시는데, 우선 배열의 성질을 이용하여 스택을 구현하는 것으로 이해해주세요.
"정확히는 배열을 사용하여 스택을 구현하는 것" 입니다.
배열 & 스택 뼈대
이전글을 통해 구현한 배열을 가져왔습니다. 배열의 성질을
| class Array: def get(self, idx): return self.data\[idx\] def set(self, idx, value): self.data\[idx\] = value # return self.data def \_\_init\_\_(self, size): self.data = \[None\] \* size def len(self): return len(self.data)class ArrayStack: def \_\_init\_\_(self): pass def push(self, value): pass def pop(self): pass |
|---|
스택의 기능을 넣은 코드를 추가했습니다. 이제 배열로 구현해 봅시다. 참고로 배열 코드는 여기에만 작성하겠습니다. 아래 부터는 배열코드를 생략할테니 배열이 잇는 것으로 가정하고 코드를 봐주세요!
배열스택 선언하기
\_\_init\_\_
| class ArrayStack: def \_\_init\_\_(self): self.data = Array(10) def push(self, value): def pop(self): pass |
|---|
우선 stack으로 사용할 배열을 먼저 선언해 줍니다. 배열은 초기 값을 선언한 상태로 값이 바뀌지 않는다는 점을 유의해주세요.
배열스택 push구현하기
ArrayStack
| class ArrayStack: def \_\_init\_\_(self): self.data = Array(10) self.idx = 0 def push(self, value): self.data.set(self.idx, value) self.idx += 1 def pop(self): pass |
|---|
stack은 값이 뒤쪽부터 쌓이게 만들 수 있습니다. 이는 배열에서 set을 사용하여 구현이 가능합니다. 배열의 경우 set에는 idx와 value값이 필요하기 때문에 idx를 임의로 설정해줄 필요가 있습니다.
self.idx = 0으로 우선 선언해주고, push가 일어날때마다 +1 씩 증가시키면 됩니다.
배열스택 push 예외처리
ArrayStack
push를 하다보면 문제가 생깁니다. 배열의 크기가 고정되어 있기 때문인데요. 배열의 크기 이상으로 push될 경우 배열의 크기를 늘려주겠습니다.
| class ArrayStack: def \_\_init\_\_(self): self.data = Array(10) self.idx = 0 def push(self, value): if self.idx >= self.data.len(): new\_data = Array(self.data.len() \* 2) self.data = new\_data #이전 데이터 옮기기 for i in range(self.data.len()): self.data.set(i, self.data.get()) self.data.set(self.idx, value) self.idx += 1def pop(self): self.idx -= 1 self.data.get(self.idx) self.data.set(self.idx, None) |
|---|
배열의 마지막 요소에 값을 넣고나면 idx = 10이됩니다. 이후 값을 넣을때 공간이 없기때문에 배열의 크기를 두배로 재설정해주고, 이전 값을 모두 옮겨줍니다. 이후에는 idx = 10 자리가 생겼기 떄문에 그대로 새로운 값을 넣어주면됩니다.
배열스택 pop 구현하기
ArrayStack
마지막으로 배열스택의 값을 삭제하는 방법입니다. 우선 push가 이루어 지면서 self.idx값은 계속 증가하게 되는데요. 이때 self.idx값이 곧 마지막 값의 위치가됩니다.
| class ArrayStack: def \_\_init\_\_(self): self.data = Array(10) self.idx = 0 def push(self, value): self.data.set(self.idx, value) self.idx += 1def pop(self): self.idx -= 1 self.data.get(self.idx) self.data.set(self.idx, None) |
|---|
배열은 delete기능이 존재하지 않기때문에, set을 사용하여 마지막 위치의 값을 None(초기값)으로 설정해주면 됩니다.
주의할점은 push사용시 최종 idx가 +1 된 상태기때문에 self.dat.get(self.idx)를 해주면 None값이 반환됩니다. 마지막 값을 출력하기 위해 idx를 -1해준 상태로 get을 사용해주세요!