스택으로 큐 구현 및 큐로 스택 구현
개요
LIFO, FIFO를 실현하는 데이터 구조로서 각각 스택과 큐를 들 수 있습니다만, 본 기사에서는 이들의 한쪽을 이용해 다른 쪽을 실장하는 수법을 소개하고 싶습니다.
Stack으로 Queue 구현
두 개의 스택을 준비하고 둘 중 하나에 요소를 저장합니다. 다만 큐의 요건인 FIFO(first in first out)를 실현하기 위해, 다른 쪽 스택을 이용해 낡은 요소가 위로 오도록(듯이) 스택에 쌓아 갑니다.
Push
팝
위의 Push 조작으로 가장 오래된 요소가 스택 S1의 Top에 위치하므로 그대로 Pop합니다.
구현 예
두 개의 스택을 사용하여 큐 구현
class MyQueue(object):
def __init__(self):
# 2つのスタックを用意する
self.s1 = []
self.s2 = []
def push(self, x):
# s1からs2に要素を移す
while self.s1:
self.s2.append(self.s1.pop())
# 空になったs1に要素を追加する
self.s1.append(x)
# s2からs1に要素を戻す
while self.s2:
self.s1.append(self.s2.pop())
def pop(self):
return self.s1.pop()
def peek(self):
if len(self.s1) > 0:
return self.s1[-1]
else:
return None
def is_empty(self):
return len(self.s1) == 0
보충
위의 예와는 반대로, push시는 그대로 스택에 쌓아 올려, pop시에 한쪽의 스택을 이용해 역순으로 pop 하도록 해도 OK입니다.
Queue로 Stack 구현
두 개의 대기열을 준비하고 둘 중 하나에 요소를 저장합니다. 다만 스택의 요건인 LIFO(last in first out)를 실현하기 위해, 다른 큐를 이용해 직전에 저장된 값을 pop 하도록(듯이) 합니다.
Push
Push 시에는 한 큐에 그대로 요소를 추가해 갑니다.
팝
구현 예
두 개의 대기열을 사용하여 스택 구현
from collections import deque
class MyStack(object):
def __init__(self):
# 2つのキューを用意する
self.q1 = deque()
self.q2 = deque()
def push(self, x):
if self.q1:
self.q1.append(x)
else:
self.q2.append(x)
def pop(self):
# 要素を一つだけ残して一方から一方に移動し、最後に残った要素をpopする
if self.q1:
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
return self.q1.popleft()
else:
while len(self.q2) > 1:
self.q1.append(self.q2.popleft())
return self.q2.popleft()
def top(self):
if self.q1:
return self.q1[-1]
else:
return self.q2[-1]
def is_empty(self):
return len(self.q1) == 0 and len(self.q2) == 0
보충
위의 예와는 반대로 push시에 하나의 큐를 이용하여 역순으로 설정되도록 하고, pop시는 그대로 큐에서 꺼내도록 해도 OK입니다.
Reference
이 문제에 관하여(스택으로 큐 구현 및 큐로 스택 구현), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/maebaru/items/579afe3c30edc143968d텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
