首页 > 代码库 > 【LeetCode OJ 232】Implement Queue using Stacks

【LeetCode OJ 232】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.
Notes:
  • You must use only standard operations of a stack -- which means only push to toppeek/pop from topsize, 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).
解题思路:题目要求用栈来实现队列,并实现其入队列、出队列、查看队首元素和推断队列是否为空四个操作。大致的思路是:用两个栈来模拟实现队列,栈s1作为存储空间,栈s2作为暂时缓冲区。
入队时:将元素压入s1
出队时:首先推断s2是否为空,如不为空,则直接弹出栈顶元素,假设为空,则将s1的元素逐个"倒入"s2,把最后一个元素弹出并出队。

演示样例代码例如以下:
/**
 * 用两个栈模拟实现队列基本操作
 * @author 徐剑
 * @date 2016-02-25
 *
 */
public class Solution
{
	Stack<Integer> s1 = new Stack<>();
	Stack<Integer> s2 = new Stack<>();
	// Push element x to the back of queue.
	public void push(int x)
	{
		s1.push(x);

	}
	// Removes the element from in front of queue.
	public void pop()
	{
		if (!s2.empty())
		{
			s2.pop();
		} else if (s1.isEmpty())
		{
			return;
		} else
		{
			while (!s1.isEmpty())
			{
				int temp = s1.pop();
				s2.push(temp);
			}
			s2.pop();
		}
	}
	// Get the front element.
	public int peek()
	{
		if (!s2.isEmpty())
			return s2.pop();

		else if (s1.isEmpty())
		{
			return -1;
		} else
		{
			while (!s1.isEmpty())
			{
				int temp = s1.pop();
				s2.push(temp);
			}
			return s2.peek();
		}
	}
	// Return whether the queue is empty.
	public boolean empty()
	{
		return s1.isEmpty() && s2.isEmpty();
	}
}

【LeetCode OJ 232】Implement Queue using Stacks