【数一线性代数】007入门

Index

- 本文稍后补全，推荐阅读：https://blog.csdn.net/weixin_60702024/article/details/140939599
- 分析实现
- - 总结

本文稍后补全，推荐阅读：https://blog.csdn.net/weixin_60702024/article/details/140939599

用两个栈来实现一个队列, 使用n个元素来完成n次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。保证操作合法，即pop操作执行使队列不为空。

要求: 时间复杂度 $O(n^2)$ , 空间复杂度 $O (n)$ 。

分析实现

通俗来讲栈和队列都是一种操作受限的线性表，通过这种操作上的限制封装好的数据结构，可以安全又便捷地完成一些特定的任务和实现更高级的算法。
二者具体限制如下：

栈（Stack）：只能从一侧入栈(push)，从同一侧出栈(pop)（多个元素连续入栈时，先进后出）
队列（Queue）：只能从一侧入队，从另一侧出队（多个元素连续入栈时，先进先出）

从上图可以直观地看出——对于栈，入栈顺序与出栈顺序为逆序（先进后出）；而对于队列，入栈顺序与出栈顺序为原序（先进先出）。

类比负负得正这样的思路，出队操作时可将所有stack1内元素出栈先加入到stack2中，然后对stack2进行出栈，这样得到的元素就是原序了。
在这里插入图片描述

#include <iostream>
#include <stack>
using namespace std;
stack<int> stack1;
stack<int> stack2;void enqueue(int x){// 入队时元素暂存于stack1中stack1.push(x);
}
void dequeue(){// 出队时分两种情况 (题中保证出队时队列不为空, 故不再考虑异常情况)// 1. stack2不为空, 直接出栈if (!stack2.empty()){int t = stack2.top();stack2.pop();cout << "出队元素为: " << t << endl;return;}// 2. stack2为空, 将stack1中元素全部转移到stack2中, 再出栈while (!stack1.empty()){int t = stack1.top();stack1.pop();stack2.push(t);}int t = stack2.top();stack2.pop();cout << "出队元素为: " << t << endl;
}

总结

本题从实现角度看，实用性不大（好好的栈为什么要转成队列啊 x_x）。

但通过本题可以更好地理解栈和队列的性质，此外本题所用到的思想还是比较有用的——两次序列反转得到正序序列（类似与用数组逆置实现数组循环左移的思路，明天会介绍一下）。

另附测试所用主函数:

int main(){while (1){cout << "请输入要执行操作(1.入队 2.出队 3.退出): ";int op;cin >> op;if (op == 1){cout << "请输入入队元素: ";int t;cin >> t;// 执行push操作enqueue(t);}else if (op == 2){// 执行pop操作dequeue();}else if (op == 3){cout<<"程序结束"<<endl;break;}else{cout << "输入错误, 请重新输入: ";}}return 0;
}