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

解题思路：题目要求用栈来实现队列，并实现其入队列、出队列、查看队首元素和推断队列是否为空四个操作。大致的思路是：用两个栈来模拟实现队列，栈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

最新文章

热门文章