Python | 스택, 큐
Stack
- 파이썬에서 리스트가 사실상 스택의 모든 연산을 지원하기 때문에 간단하게 정리하고 넘어간다.
- 메소드
- push(e) : 요소를 컬렉션에 추가
- pop() : 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거
- peek() : 가장 최근에 삽입된 요소 확인
- 간단한 구현 2가지 ( 리스트, 연결 리스트 )
class Stack(list):
push = list.append
def peek(self):
return self[-1]
# pop은 내장함수에 있어 구현 Xclass Node:
def __init__(self, item, next):
self.item = item
self.next = next
class Stack:
def __init__(self):
self.last = None
def push(self, item):
self.last = Node(item, self.last)
def pop(self):
item = self.last.item
self.last = self.last.next
return item
def peek(self):
return self.last.itempush()는 연결 리스트에 요소를 추가하고, 가장 마지막 값을 next로 지정하면서, (Node의 self.last ) 포인터인 last는 가장 마지막으로 이동시킨다. (self.last 는 Node를 가리킴)
pop()은 가장 마지막 아이템을 끄집어내고, (return item) last포인터를 한칸 앞으로 전진시킨다.(self.last = self.last.next)
스택이므로 last 포인터는 가장 마지막에 들어온 Node를 가리키고 있어야 하고, 각각의 노드는 이전에 들어온 값들을 가리키고 있다.
Queue
- 큐 또한 파이썬에서 리스트가 큐의 모든 연산을 지원하기 때문에 간단하게 정리하고 넘어가겠다.
- 하지만, 리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서 Deque라는 별도 자료형을 사용해야 좋은 성능을 낼 수 있다.
- 간단한 구현 (리스트)
class Queue:
put = list.append
def peek(self):
return self[0]
def get(self):
return self.pop[0]연결 리스트도 추가할까 했지만, 지금 생각나는 건 get()을 할 때 self.last=None일때까지 돌아야 해서 pop(0)을 하는 것과 비슷한 방식이라고 생각되어 적지 않았다.
하지만 아래 출처의 책에서, 스택 2개를 이용하여 큐를 구현한 좋은 예시가 있었다.
class Queue:
def __init__(self):
self.input = []
self.output = []
def put(self, item):
self.input.append(item)
def get(self):
self.peek()
return self.output.pop()
def peek(self):
# output이 없다면, output에 input의 내용을 재입력한다.
if not self.output:
while self.input:
self.output.append(self.input.pop())
return self.output[-1]먼저 input, output스택을 만든다.
item이 들어올 경우 input 스택에 채워둔다. get을 할때, peek함수를 먼저 실행시키는데, peek함수에는 output이 없다면 input에서 하나씩 꺼내와 output 스택에 다시 채운다. FIFO인 큐의 연산을 구현하기 위해 FILO의 input 스택 연산을 한번 실행해 output 스택에서는 순서가 뒤집힌 상태로 들어가 있다. 따라서 get을 할때 처음에 넣었던 값이 나오게 되는 것이다.
책에서는 output의 값이 모두 pop되기 전까지는 다시 재입력이 일어나지 않아, 분할 상환 분석에 따른 시간 복잡도는 여전히 O(1)이라고 서술하고 있다.
 |
|