LeetCode 232: Implement Queue using Stacks
2024-08-22 19:49:35
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
operations are valid.
is empty - 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).
题目要求通过栈来模拟队列的行为。与此类似的还有通过队列模拟栈(http://blog.csdn.net/sunao2002002/article/details/46482673),此题是算法导论第十章的一道题。算法例如以下:
堆栈a和b。a用作入队,b出队
(1)判队满:假设a满且b不为空,则队满
(2)判队空:假设a和b都为空,则队空
(3)入队:首先判队满。
若队不满:(1)栈a若不满,则直接压入栈a
(2)若a满,则将a中的全部元素弹出到栈b中,然后再将元素入栈a
(4)出队:(1)若b空就将a中的全部元素弹出到栈b中。然后出栈
(2)b不空就直接从b中弹出元素
代码例如以下:
class Queue {
public:
// Push element x to the back of queue.
stack<int> in;
stack<int> out;
void push(int x) {
in.push(x);
} void move(){
while(!in.empty())
{
int x = in.top();
in.pop();
out.push(x);
}
}
// Removes the element from in front of queue.
void pop(void) {
if (out.empty())
{
move();
}
if (!out.empty())
{
out.pop();
}
} // Get the front element.
int peek(void) {
if (out.empty())
{
move();
}
if (!out.empty())
{
return out.top();
} } // Return whether the queue is empty.
bool empty(void) {
return in.empty() && out.empty(); }
};
最新文章
- LeetCode 344. Reverse String
- css 水平垂直居中总结
- css通用小笔记01——导航背景
- 诊断一句SQL不走索引的原因
- Android Phonebook编写联系人UI加载及联系人保存流程(一)
- linux包之procps之pmap命令
- 导出excel小结(C#,.NET,Wpf)
- android之TextView
- sa命令从/var/account/pacct原始记账数据文件读取信息并汇总
- oracle 两表数据对比---minus
- Flume+Kafka+Storm整合
- 【总结】字符串hash
- 利用ONENET平台控制MPC
- webpack热更新和常见错误处理
- 4. 文本相似度计算-CNN-DSSM算法
- sql server 视图的操作
- spark 任务运行原理
- 500 OOPS: vsftpd: cannot locate user specified in &#39;chown_username&#39;:whoever
- Codeforces Round #299 (Div. 1) A. Tavas and Karafs 水题
- HDFS原理分析之HA机制:avatarnode原理