（ブログ記事からの転載）
重要なデータ構造の1つにStack（スタック）とQueue（キュー）がありますが、これを実装しろという問題を取り上げます。
と言っても、こちらの解説記事にあるように、スタックもキューも配列で表現することができ、データ構造としては特別なものではありません。重要なのは以下の使われ方の違いです。
スタック データ構造に入っている要素のうち、最後に push した要素を取り出す
キュー データ構造に入っている要素のうち、最初に push した要素を取り出す
以上の関数を有するStack class, Queue classを実装します。
Implement Stack using Queues
[https://leetcode.com/problems/implement-stack-using-queues/]
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
Example:
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false
Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
まずはstackの実装から。問題タイトルにもあるように、queueを使ってstackを実装することが求められています。
queueを使うということは、可能な操作も限定されます。only push to back, peek/pop from front, size, and is empty operations are validとあるように、pushは後ろから、popは前からに限定されます。
誤答
一応やっておくと、問題の意図を無視してstackを使ってしまっても、テストは通ってしまいます。
ただ当然ながら、stackを使ってstackを作っても何の意味もないですね。
pythonではlistがstackにあたる挙動を示します。
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.stack.append(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.stack.pop()
def top(self) -> int:
"""
Get the top element.
"""
return self.stack[-1]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.stack) == 0
解法
この問題ではqueueを使ってstackを実装することを求められていますが、ポイントはpop。繰り返しになりますが、stackでは最後にpushされた要素を取り出しますが、queueでは最初にpushされた要素を取り出します。
pythonではqueue.popleft()で最初にpushされた要素を取り出せます。popleftを使って、pushを実行した際に、後にpushされた要素が先頭にくるようにqueueを並び替えるのが以下の解法です。
class MyStack:
def __init__(self):
self.queue = collections.deque()
def push(self, x: int) -> None:
q = self.queue
q.append(x)
for _ in range(len(q)-1):
q.append(q.popleft())
def pop(self) -> int:
return self.queue.popleft()
def top(self) -> int:
return self.queue[0]
def empty(self) -> bool:
return len(self.queue) == 0
時間計算量がpushで$O(n)$、popでは$O(1)$かかることになります。
ちなみに、本問題の要求のもとでは使えませんが、以下記事にあるようにcollections.deque()にはpopメソッドも存在し、時間計算量$O(1)$で後方から要素を取り出し削除することが可能です。
[https://note.nkmk.me/python-collections-deque/:embed:cite]
Implement Queue using Stacks
[https://leetcode.com/problems/implement-queue-using-stacks/]
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
次に、Queueの実装です。今度はstackを使ってqueueを実装することを求められています。
これも可能な操作が限定されます。only push to top, peek/pop from top, size, and is empty operations are validとなっています。つまりpush, peek, popについてはlist.append(x), list[-1], list.pop()のみが許容されていることになります。
解法
2つstackを用意し、pushの際はinStackに格納、peekやpopの際はinStackの要素を逆順にして格納したoutStackを用意し、処理を行うのが以下の解法です。
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.inStack, self.outStack = [], []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.inStack.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
self.peek()
return self.outStack.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if(self.outStack == []):
while(self.inStack != []):
self.outStack.append(self.inStack.pop())
return self.outStack[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.inStack) == 0 and len(self.outStack) == 0