파이썬 연결리스트 큐 구현하기 (자료구조변환)
파이썬 연결리스트 큐 구현하기 (자료구조변환) — #파이썬연결리스트 #연결리스트큐 #연결리스트 #큐 #자료구조 #자료구조변환 AI스쿨 msa기반 java 백엔드...
#파이썬연결리스트 #연결리스트큐 #연결리스트 #큐 #자료구조 #자료구조변환
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
자료구조 변환
이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.
예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.
스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.
연결리스트로 큐 구현하기
ListQueue
이번에는 연결리스트를 이용하여 큐를 구현합니다. 리스트와 큐의 기능은 이전글을 참고해주세요.
사용할 연결리스트
LinkedList()
이전글을 통해 구현한 연결리스트입니다. 연결리스트의 기능을 생각하시면서 코드를 봐주새요.
ListQueue() 선언하기
\_\_init\_\_
| class ListQueue: def \_\_init\_\_(self): self.list = LinkedList() def push(self, value): pass def pop(self): pass |
|---|
ListQueue역시 Queue의 형태기 때문에 똑같은 뼈대를 가지고 있습니다. ListQueue의 경우는 우선적으로 LinkedList를 선언해줘야합니다.
ListQueue.push()
push
ListQueue를 만들기 위해 사용한 LinkedList의 경우 빈값에서 add될 경우 아래와 같은 방법으로 노드가 연결됩니다.
- 초기상태
None
- add(value)
new\_node(current) -> None
- add2(value2)
new\_node2(current) -> new\_node -> None
이런 방법으로 노드가 연결되어 가장 처음에 넣은 값이 끝 위치에 놓이게 됩니다.
| class ListQueue: def \_\_init\_\_(self): self.list = LinkedList() self.count = 0 def push(self, value): self.list.add(value) self.list.move\_front() self.list.add(value) self.count += 1 for i in range(self.count - 1): self.list.move\_next() def pop(self): pass |
|---|
저는 ListQueue의 psuh()가 끝난상태에서 현재위치를 항상 끝에 위치하게끔 구현하고자 하였습니다. 만약 ListQueue의 새로운 push()가 발생한다면, 항상 처음값(self.head)로 current를 옮기고 push()하도록 구현합니다.
또한 노드의 갯수를 세는 self.count변수를 만들고 맨 마지막 노드로 현재위치를 옮겨줍니다.
예상 실행은 이렇습니다.
- None
2.new\_node1(c) -> None
3.new\_node2 -> new\_node1(c) -> None
push()
4.1. new\_node2(c) -> new\_node1 -> None
4.2. new\_node3(c) -> new\_node2 -> new\_node1 -> None
4.3. new\_node3 -> new\_node2 -> new\_node1(c) -> None
이런방법으로 현재위치를 항상 맨 마지막에 두면 pop()을 간단하게 구현할 수 있습니다.
ListQueue.pop()
pop()
위의 4.3. new\_node3 -> new\_node2 -> new\_node1(c) -> None에서 ListQueue.pop()이 행해진 상황을 생각해봅시다.
일단 구현된 LinkedList.delete()를 사용하면 4.3은 다음과 같은 형태가 됩니다.
new\_node3 -> new\_node2 -> None(c)
앞서 우리는 항상 현재위치를 마지막에 두기로 정하였습니다. 이를위해서 다음과 같은 코드를 작성할 수 있습니다.
| 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): current\_value = self.list.current.data self.list.delete() self.count -= 1 self.list.move\_front() for i in range(self.count - 1): self.list.move\_next() return current\_value |
|---|
일단 self.list에서 delete()를 실행하면 위에서 본 new\_node3 -> new\_node2 -> None(c) 형태가 됩니다.노드의 수가 줄어들었으니 self.count를 1 감소시킵니다.
이후 맨 처음으로 이동한 후, self.count -1만큼 다시 앞으로 이동해줍니다.
이로써 항상 현재값이 맨끝으로 위치하게끔 ListQueue를 구현하였습니다.
해당글은 효율성을 고려하지 않고 다양한 관점에서 ListQueue를 구현하는 것에 초점을 두었습니다.
자료구조 총정리