## 题目描述：

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.

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).

## 题目大意：

• push(x) -- 将元素x加至队列尾部
• pop() -- 从队列头部移除元素
• peek() -- 获取队头元素
• empty() -- 返回队列是否为空

“双栈法”或者“单栈法”均可。

## Python代码：

class Queue:
# initialize your data structure here.
def __init__(self):
self.inStack = []
self.outStack = []

# @param x, an integer
# @return nothing
def push(self, x):
self.inStack.append(x)

# @return nothing
def pop(self):
self.peek()
self.outStack.pop()

# @return an integer
def peek(self):
if not self.outStack:
while self.inStack:
self.outStack.append(self.inStack.pop())
return self.outStack[-1]

# @return an boolean
def empty(self):
return len(self.inStack) + len(self.outStack) == 0

## Python代码：

class Queue:
# initialize your data structure here.
def __init__(self):
self.stack = []

# @param x, an integer
# @return nothing
def push(self, x):
swap = []
while self.stack:
swap.append(self.stack.pop())
swap.append(x)
while swap:
self.stack.append(swap.pop())

# @return nothing
def pop(self):
self.stack.pop()

# @return an integer
def peek(self):
return self.stack[-1]

# @return an boolean
def empty(self):
return len(self.stack) == 0

Pingbacks已关闭。

1. 硅藻泥缺点 发布于 2015年7月7日 14:26 #

[路过这儿]

2. 熹儿 发布于 2015年12月14日 12:32 #

博主好，我是初学者，想请教一下，单栈法那里的push 为什么不能直接用self.stack.append(x)呢，感觉这样也是符合最新的item进入list的最后呢

3. 在线疯狂 发布于 2015年12月14日 20:56 #

队列的特点是FIFO，先进先出的；而栈是FILO，先进后出的。所以不能直接用self.stack.append(x)