파이썬링크드리스트로 스택 구현하기 (자료구조의 변환)
파이썬링크드리스트로 스택 구현하기 (자료구조의 변환) — #파이썬링크드리스트 #파이썬스택 #링크드리스트 #링크스택 #자료구조변환 AI스쿨 msa기반 java 백엔드 ...
#파이썬링크드리스트 #파이썬스택 #링크드리스트 #링크스택 #자료구조변환
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
자료구조 변환
이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.
예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.
스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.
리스트로 스택 구현하기
ListStack
이번에는 링크드 리스트를 사용하여 스택을 구현합니다. 각 자료구조의 기능은 이전글을 참고해주세요.
배열스택과 마찬가지로 링크드(특징을 활용)를 사용해서 스택을 구현합니다.
링크드리스트 & 스택 뼈대
링크드 리스트는 이전글을 통해 만든 코드를 가져왔습니다. 구현방법에 대해 잘 모르시는 분들은 사전에 하급하고 돌아와주세요!
| class Node: def \_\_init\_\_(self, data): self.data = data self.next = None class LinkedList: def \_\_init\_\_(self): self.head = None self.current = None def move\_next(self): if self.current is None: return self.current = self.current.next def get(self): if self.current is None: return None return self.current.data def modify(self, value): if self.current is None: return self.current.data = value def add(self, value): prev\_node = None if self.current is not self.head: prev\_node = self.head while prev\_node.next != self.current: prev\_node = prev\_node.next new\_node = Node(value) new\_node.next = self.current if self.current is not self.head: prev\_node.next = new\_node else: self.head = new\_node self.current = new\_node def delete(self): if self.current is None: return prev\_node = None if self.current is not self.head: prev\_node = self.head while prev\_node.next != self.current: prev\_node = prev\_node.next if self.current is not self.head: prev\_node.next = self.current.next else: self.head = self.current.next self.current = self.current.next def move\_front(self): self.current = self.head |
|---|
리스트 스택의 뼈대입니다. 스택과 별 차이가 없습니다.
| class ListStack: def \_\_init\_\_(self): pass def push(self, value): pass def pop(self): pass |
|---|
링크드 리스트 코드는 너무 길기때문에, 여기서만 한번 작성하고 차후에는 링크드 리스트가 있다는 가정하에 코드를 작성합니다.
링크스택 선언하기
\_\_init\_\_
| class ListStack: def \_\_init\_\_(self): self.data = LinkedList() def push(self, value): pass def pop(self): pass |
|---|
LinkStack에 사용할 링크드 리스트를 self.data로 선언해줍니다. 더 필요한 변수들은 구현해보면서 천천히 생각해봅시다.
링크스택 push구현
LinkStack.push(value)
구현된 링크드리스트에 새로운 값을 추가할 경우 값의 위치가 하나씩 밀리게 구현하였습니다. 값n을 n번째로 넣은 값이라고 가정한다면 링크드리스트의 형태는 값3 -> 값2 -> 값1 이 될 것입니다. 항상 최신값이 제일 마지막에 넣은 값임을 기억해주세요.
| class ListStack: def \_\_init\_\_(self): self.data = LinkedList() def push(self, value): self.data.add(value) def pop(self): pass |
|---|
push가 head에서 멀어지면서 쌓이는 구조가 완성됩니다.
링크스택 pop구현
LinkStack.pop()
값3 -> 값2-> 값1 순서대로 값이 쌓이고 있습니다. pop은 가장 최근에 넣은 값을 삭제하는 기능을 가져야합니다.
| class ListStack: def \_\_init\_\_(self): self.data = LinkedList() def push(self, value): self.data.add(value) def pop(self): self.data.delete() |
|---|
우리는 링크드 리스트의 head부분만 삭제를 신경쓰면 됩니다. 근데 이미 링크드 리스트 head 부분이 삭제되면 자동으로 다음 부분이 head가 되도록 구현되어있습니다.
그렇습니다... 링크드리스트가 이미 stack과 같은 형태로 구현되어 있어 딱히 건드릴 부분이 없습니다.
자료구조 총정리