游戏设计 网站,网站的类型和特色,杭州企业展厅设计公司,官方百度app下载目录
前言
一、读懂题目
二、思路分析
三、代码呈现
总结 前言 当我们需要实现队列的先进先出特性时#xff0c;可以使用栈来模拟队列的行为。本文将介绍如何使用两个栈来实现队列#xff0c;并给出具体的思路和代码实现。 一、读懂题目 题目#xff1a;用两个栈实现一…目录
前言
一、读懂题目
二、思路分析
三、代码呈现
总结 前言 当我们需要实现队列的先进先出特性时可以使用栈来模拟队列的行为。本文将介绍如何使用两个栈来实现队列并给出具体的思路和代码实现。 一、读懂题目 题目用两个栈实现一个队列。队列的声明如下请实现它的两个函数 appendTail 和 deleteHead分别完成在队列尾部插入结点和在队列头部删除结点的功能。 当我们需要利用栈来实现队列先进先出的特性时考虑到单个栈对存入的一组数据push后再逐位pop取出对应的序列和输入的顺序相反那我们是否可以用两个栈抽象类似于负负得正的手法使得top位逐个取出得到的序列和插入时是相同的
二、思路分析
首先基础类定义如下我们只需要补充里面 appendTail 和 deleteHead 两函数的定义即可
// 用两个栈实现队列
templatetypename T
class MyQueue
{
public:void appendTail(const T n);T deleteHead();
private:stackT st1;stackT st2;};
为了便于表示和说明设定一组数据 {a, b, c, d, e} 作为测试序列。
我们看到两个栈都可存储数据那我们不妨先将数据全部存入st1中那么根据栈先进后出的特性两栈中数据的存储此时应该是这样的 既然我们想到试试“负负得正”这种方法那要是把st1中的元素再一 一取出放入st2中是不是相当于把序列的顺序调转再调转这样当我们不断取 st2.top() 时最后按照取出的序列就是原来顺序的初始序列
我们模拟一下这个过程
1对st1执行两次取首压入st2中 2将剩余元素从st1中全部压入st2中此时st1为空 3最后每当该模拟队列执行一次 front() 操作就返回 top2 所指向的值每次 pop() 就从 st2 取出栈顶元素前提是st1为空直到 st2 栈为空 那如果在执行 front() 过程中夹杂着新的push()指令应该将新元素放入st1还是st2呢如果st1不为空要先将st1全部按照上面的规则移入st2后再插入还是先放入st1栈顶再统一移入st2呢
首先我们明确每个元素都需要经历“负负得正”的过程所以首先新加元素肯定要先经过st1才能进入st2中。那是否需要st1及时清空呢
我们不妨以 {a, b, c, d}, {e} 模拟两批次对模拟队列执行push()指令
假定我们在每批操作结束就将该批的元素依次弹出并置入st2中那么当需要输入上面第二组即{e}时st1和st2的存储情况如下 接下来该插入第二批数据了但是实际功能调用过程中不可能每次单批次插入操作之间是连续的中间可能会有删除队列中已有元素的操作所以我们不妨在两次 push() 指令中间加一句 pop_front() 指令那么当接着执行一次pop_front() 指令时对于st2而言应该将 a 元素剔除。同时我们注意到 a 元素正如我们所料位于st2的栈顶当 st2.pop() 操作执行时取出 a 元素符合队列先进先出的特性。此时st1为空st2顶部元素为b如下图 下一步我们进行第二批插入将元素 e 执行 push() 操作时显然 e 需要先进st1中所以st1中此时不为空元素即为st1栈顶元素 那么此时我们要不要把st1中的所有元素这里仅有 e 顺手植入st2中呢
1如果移入st2中 现在面临一个问题如果我们一次性取出st2中的元素亦或是仅取st2栈顶元素执行 st2.pop() 来获得理想的队列头却发现得到的结果并不满足我们的设计需求两轮输入的总序列为 {a, b, c, d, e} 而取出序列为 {a, e, ... }显然不符合先进先出的原则。
那是否意味着第二批的输入元素应该先保存在st1中并非单批输入结束后就将其接着压入st2中那为什么首批输入的数据就可以直接经st1后全部置入st2呢
难道因为开始时候 st2 为空吗那如果后续其他批次插入时也遵循 st2 为空后再将 st1 中所有元素置于 st2 中会不会发生这样的冲突
不妨我们按照这样的设计思路进行测试
首先给出部分功能的此思路代码
1清空 st1 容器功能代码
templatetypename T
void MyQueueT::appendOver()
{if (st2.empty()) // 只有满足st2为空才清空st1{while (!st1.empty()){st2.push(st1.top());st1.pop();}}
} 2模拟 front() , push() 和 pop() 的函数功能
templatetypename T
T MyQueueT::front()
{if (!st1.empty()){appendOver();}assert(!st2.empty());return st2.top();
}templatetypename T
void MyQueueT::appendTail(const T n)
{st1.push(n);
}templatetypename T
T MyQueueT::deleteHead()
{assert(!empty()); // 不能同时为空if (st2.empty()){appendOver();}T tmp_poped st2.top();st2.pop();return tmp_poped;
} 3实际测试代码
void test1()
{MyQueueint mq;// queue.push()模拟尾插for (int i 10; i 0; i--){mq.appendTail(i);} // 1 2 3 4 5 6 7 8 9 10 右侧栈顶// queue.front()模拟取首元素// appendTail()--push()模拟入队列操作// deleteHead()--pop()模拟删除队列首元素mq.deleteHead(); // st1中空 st2中1 2 3 4 5 6 7 8 9 右侧栈顶mq.appendTail(100); // st1中100 st2中1 2 3 4 5 6 7 8 9 右侧栈顶// 由于st2不为空st1中元素不发生迁移// 经过上面两步 st1中100 st2中1 2 3 4 5 6 7 8 9// 假设我们再进行一组类似操作mq.deleteHead(); // st1中100 st2中1 2 3 4 5 6 7 8 右侧栈顶mq.appendTail(55); // st1中55 100 st2中1 2 3 4 5 6 7 8 右侧栈顶int val mq.deleteHead(); // st1中55 100 st2中1 2 3 4 5 6 7 右侧栈顶printf(val %d\n, val); // 8PopAndPrintMyQueueint(mq);
}
按理来说结果应该和各行代码后面的理想推测相同我们看看最后两行执行结果
可以看到和我们推测的结果完全一致我们不仅在上面完成了一组插入删除后额外执行了一组插入和删除操作最后打印整个模拟队列中剩余元素时呈现的结果和传入的顺序也相同同样可以采用其他各种操作统计每次取出的元素组成的序列是否满足先进先出的特性结果终究是符合的。
三、代码呈现
下面直接给出代码
// 用两个栈实现队列
templatetypename T
class MyQueue
{
public:void appendTail(const T n);T deleteHead();T front();bool empty();
private:void appendOver(); // 将st1中元素的全部移入st2中 --- 前提st2不为空stackT st1;stackT st2;};templatetypename T
void MyQueueT::appendTail(const T n)
{st1.push(n);
}templatetypename T
void MyQueueT::appendOver()
{if (st2.empty()) // 只有满足st2为空才清空st1{while (!st1.empty()){st2.push(st1.top());st1.pop();}}
}templatetypename T
bool MyQueueT::empty()
{if (st1.empty() st2.empty()){return true;}return false;
}templatetypename T
T MyQueueT::deleteHead()
{assert(!empty()); // 不能同时为空if (st2.empty()){appendOver();}T tmp_poped st2.top();st2.pop();return tmp_poped;
}templatetypename T
T MyQueueT::front()
{if (st2.empty()){appendOver();}assert(!st2.empty());return st2.top();
}templatetypename T
void PopAndPrintMyQueue(MyQueueT my_q)
{while (!(my_q.empty())){cout my_q.front() \t;my_q.deleteHead();}cout endl;
}void test1()
{MyQueueint mq;// queue.push()模拟尾插for (int i 10; i 0; i--){mq.appendTail(i);} // 1 2 3 4 5 6 7 8 9 10 右侧栈顶// queue.front()模拟取首元素// appendTail()--push()模拟入队列操作// deleteHead()--pop()模拟删除队列首元素mq.deleteHead(); // st1中空 st2中1 2 3 4 5 6 7 8 9 右侧栈顶mq.appendTail(100); // st1中100 st2中1 2 3 4 5 6 7 8 9 右侧栈顶// 由于st2不为空st1中元素不发生迁移// 经过上面两步 st1中100 st2中1 2 3 4 5 6 7 8 9// 假设我们再进行一组类似操作mq.deleteHead(); // st1中100 st2中1 2 3 4 5 6 7 8 右侧栈顶mq.appendTail(55); // st1中55 100 st2中1 2 3 4 5 6 7 8 右侧栈顶int val mq.deleteHead(); // st1中55 100 st2中1 2 3 4 5 6 7 右侧栈顶printf(val %d\n, val); // 8PopAndPrintMyQueueint(mq);
}值得注意的是上面对重要功能的安全性检查中下面两种写法其本质是相同的
// 1.
if (st2.empty())
{appendOver();
}
assert(!st2.empty());// 2.
assert(!empty()); // 不能同时为空
if (st2.empty())
{appendOver();
} 总结 本文详细介绍了如何利用栈来实现队列的先进先出特性。通过使用两个栈我们可以将插入的顺序和取出的顺序保持一致。文章讨论了具体的实现思路并通过代码实例进行了测试。通过测试结果我们验证了模拟队列的各种操作都满足先进先出的特性。这种使用栈实现队列的方法在实际应用中具有重要的意义。
