首页 > 代码库 > 【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.
- You must use only standard operations of a stack -- which means only
push to top,peek/pop from top,size, andis emptyoperations 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。