파이썬 배열로 큐 구현하기 (자료구조 변환)
파이썬 배열로 큐 구현하기 (자료구조 변환) — #배열큐 #자료구조 #자료구조변환 #파이썬배열 #파이썬큐 #파이썬배열큐 AI스쿨 msa기반 java 백엔드 코...
#배열큐 #자료구조 #자료구조변환 #파이썬배열 #파이썬큐 #파이썬배열큐
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
자료구조 변환
이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.
예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.
스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.
배열로 큐 구현하기
ArrayQueue
이전글을 통해 배열, 링크드리스트, 큐로 스택을 구현하였습니다. 이번에는 배열, 링크드리스트, 스택을 사용하여 큐를 구현하고자 합니다. .
그중에서 오늘은 배열을 사용하여 큐를 구현해 볼겁니다. 배열과 스택의 기능들은 이전글을 참고해주세요.
사용할 배열
이전글을 통해 구현한 배열을 가져왔습니다.
| 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) |
|---|
배열의 기능으로는 idx의 값을 가져오기, 수정하기, 초기 사이즈&값 셋팅하기 + 배열의 크기를 반환하기 등입니다.
ArrayQueue 기본구조
| class ArrayQueue: def \_\_init\_\_(self): self.array = Array(10) def push(self, value): pass def pop(self): pass |
|---|
ArrayQueue도 Queue의 한 종류이기 때문에 기본 구조는 Queue와 동일합니다. 다만 차이점은 처음 ArrayQueue를 시작할때 초기 배열을 선언해줘야 합니다. 이때 배열의 크기는 임의로 설정해 주세요.
ArrayQueue.push()
push()
| class ArrayQueue: def \_\_init\_\_(self): self.array = Array(10) self.current = 0 def push(self, value): self.array.set(self.current, value) self.current += 1 def pop(self): pass |
|---|
배열은 기본적으로 값들이 셋팅되어 있습니다. 제가 사용한 배열의 경우에는 None으로 값이 셋팅되어 있는데요. size를 처음에 10으로 설정하였으니 self.array.data는 \[None, None, None, ...., None\]이 될것입니다.
이때 ArrayQueue.push()를 사용할 경우 처음값부터 하나씩 바뀌도록 구현하는 것이 좋습니다. 그래서 ArrayQueue 초기 선언시 self.current = 0으로 설정하고 push할 때마다 +1 씩 증가시킵니다.
이후 self.array.set(self.current, value)를 사용하여 앞에서 부터 값들을 하나씩 바꿔줍니다.
ArrayQueue.push() 예외처리
배열의 크기를 넘어설 때
배열은 크기가 고정되어있습니다. ArrayQueue에 사용된 배열은 크기가 10입니다.
이때ArrayQueue,push()를 10번 이상하면 어떻게 될까요? self.current >= 10이되어 배열의 index를 벗어납니다. 즉 이 ArrayQueue에는 10개의 요소밖에 담지 못하는 것입니다.
Queue의 순기능에는 크기 제한이 없습니다. 하지만, 배열을 사용하면 이런식으로 크기에 제한이 걸려 제대로된 Queue기능을 하지 못합니다.
이를 위해서 ArrayQueue에서 배열을 재선언 하여 크기를 늘려주는 것이 좋습니다. 아래와 같은 코드를 추가합니다.
| class ArrayQueue: def \_\_init\_\_(self): self.array = Array(10) self.current = 0 self.head = 0 def push(self, value): if self.current >= self.array.len(): new\_array = Array(self.array.len() \* 2) for i in range(self.array.len()): new\_array.set(i, self.array.get(i)) self.array = new\_array self.array.set(self.current, value) self.current += 1 def pop(self): pass |
|---|
해당코드는 self.current >= 10일때 배열을 재선언하고 이전 값을 새로운 배열에 모두 옮긴 후, self.data로 재 선언하는 방법입니다.
ArrayQueue.pop()
pop()
자 이제 구현이 끝나가는군요. 마지막 ArrayQueue의 요소를 제거하는 일만 남았습니다. ArrayQueue의 가장 첫번째 요소를 제거해야합니다. 첫번째 요소를 제거해줬으니 이후 요소들을 한칸씩 앞으로 땡겨줘야합니다.
또한 제거할때는 배열은 크기가 줄어들면 안돼기 때문에 해당값을 초깃값 None으로 되돌려 주는 방법으로 구현하면 됩니다.
| class ArrayQueue: def \_\_init\_\_(self): self.array = Array(10) self.current = 0 self.head = 0 def push(self, value): if self.current >= self.array.len(): new\_array = Array(self.array.len() \* 2) for i in range(self.array.len()): new\_array.set(i, self.array.get(i)) self.array = new\_array self.array.set(self.current, value) self.current += 1 def pop(self): first\_value = self.array.get(self.head) self.array.get(self.head) self.array.set(self.head, None) for i in range(self.head + 1, self.current + 1): self.array.set(i - 1, self.array.get(i)) self.current -= 1 return first\_value |
|---|
그전에 ArrayQueue의 항상 첫 값의 index를 따로 저장해두었습니다(self.head). 이제 pop()을 사용할 경우 항상 맨처음 값을 반환하고 None으로 세팅될 것입니다.
맨 처음값이 None이 되면 이전 값들을 옮겨줄 필요가 있습니다. 이를 위해서 반복문을 사용하여 이전 값들을 앞으로 모두 옮겼습니다.
자료구조 총정리