栈和队列数据结构的相互实现[LeetCode]
栈是先进后出，队列是先进后出，这里讨论一下两种数据结构之间的相互实现。
一.用两个栈实现队列
我们用一个栈来实现队列的进队操作（栈A），用另一个栈来实现队列的出队操作（栈B）。
1.入队列：
把元素放进栈A即可。假如栈A已满并且栈B为空，可以先把栈A中的所有元素先弹出并放入栈B中；假如栈B不为空，则出错了（不能插入）。
2.出队列：
假如栈B不为空，直接弹出。假如栈B为空，由于队列是先进先出的，因此要出队列时，我们要先把栈A中的元素全部放进栈B中，然后再从栈B中弹出栈顶元素。
3.例子：
进行以下操作：
（1）插入1：
栈A：1
栈B：空
（2）插入2（左边为栈顶）：
栈A：2 1
栈B：空
（3）出队列：
栈B为空，先把栈A的元素弹出插入栈B：
栈A：空
栈B：1 2
栈B弹出：
栈A：空
栈B：2
（4）出队列
栈B不为空，直接弹出：
栈A：空
栈B：空
这样，进队列的顺序为1 2，出队列的顺序为1 2，满足队列的特性。
4.LeetCode相关题目
232. Implement Queue using Stacks（https://leetcode.com/problems/implement-queue-using-stacks/description/）：
这道题的考虑的东西很少，没考虑一些特殊情况：
#include <iostream>
#include <stack>
using namespace std;
class MyQueue {
public:
stack<int> in;
stack<int> out;
/** Initialize your data structure here. */
MyQueue() {
} /** Push element x to the back of queue. */
void push(int x) {
in.push(x);
} /** Removes the element from in front of queue and returns that element. */
int pop() {
if (!out.empty()) {
int temp = out.top();
out.pop();
return temp;
}
else {
if (in.empty()) {
return -;
}
else {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
int temp = out.top();
out.pop();
return temp;
}
}
} /** Get the front element. */
int peek() {
if (!out.empty()) {
return out.top();
}
else {
if (in.empty()) {
return -;
}
else {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
return out.top();
}
}
} /** Returns whether the queue is empty. */
bool empty() {
return in.empty() && out.empty();
}
}; /**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/
二.用两个队列实现栈：
1.用队列实现栈有两种方法，两种方法的入栈和出栈的时间复杂度不相同，按需使用：
假设有两个队列，一个队列A，不为空，一个队列B，为空。队列A中的元素符合栈操作的前提。
（1）入栈O(n)，出栈(1)
入栈时，直接把元素放进空的队列B，然后把队列A所有的元素按顺序放到队列B中。队列A就变为空了。此时，最后一个“入栈”的元素就成了队列头，需要弹出直接从队列B中弹出即可。这样就满足了栈后进先出的特性了。之后的操作两个队列交替就行了。
（2）入栈O(1)，出栈(n)
入栈时，直接把元素放进不为空的队列A的队尾；出栈时，把栈A的前n-1个元素放入栈B中，栈A中剩下一个的元素就是最新插入的元素，直接出队列，也满足栈的特性了。
2.LeetCode相关题目
225. Implement Stack using Queues（https://leetcode.com/problems/implement-stack-using-queues/description/）
这道题用第（1）种方法会快一点，说明出栈操作多一点吧。
方法（1）：
class MyStack {
public:
/** Initialize your data structure here. */
queue<int> a;
queue<int> b;
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
if (a.empty() && b.empty()) {
a.push(x);
return;
}
if (a.empty()) {
a.push(x);
while (!b.empty()) {
a.push(b.front());
b.pop();
}
}
else {
b.push(x);
while (!a.empty()) {
b.push(a.front());
a.pop();
}
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
if (a.empty()) {
int temp = b.front();
b.pop();
return temp;
}
else {
int temp = a.front();
a.pop();
return temp;
}
}
/** Get the top element. */
int top() {
return a.empty() ? b.front() : a.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return a.empty() && b.empty();
}
};
方法（2）：
class MyStack {
public:
/** Initialize your data structure here. */
queue<int> a;
queue<int> b;
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
if (a.empty() && b.empty()) {
a.push(x);
return;
}
if (!a.empty()) {
a.push(x);
}
if (!b.empty()) {
b.push(x);
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
if (!a.empty()) {
while (a.size() != ) {
b.push(a.front());
a.pop();
}
int temp = a.front();
a.pop();
return temp;
}
else {
while (b.size() != ) {
a.push(b.front());
b.pop();
}
int temp = b.front();
b.pop();
return temp;
}
}
/** Get the top element. */
int top() {
if (!a.empty()) {
while (a.size() != ) {
b.push(a.front());
a.pop();
}
int temp = a.front();
b.push(a.front());
a.pop();
return temp;
}
else {
while (b.size() != ) {
a.push(b.front());
b.pop();
}
int temp = b.front();
a.push(b.front());
b.pop();
return temp;
}
}
/** Returns whether the stack is empty. */
bool empty() {
return a.empty() && b.empty();
}
};
最新文章
- Hadoop HDFS 用户指南
- iOS的一些面试题分析总结（1）
- Android由一个activity 间隔5秒自动跳转到另外一个activity
- Windows下通过bat脚本实现自动上传文件到ftp服务器
- sqlite3加密支持
- js中关于原型的几个方法
- OpenGL 回顾-——矩形的创建、列表
- linux常用命令大全(转)
- 【sql】经典SQL语句大全
- dede 标签
- 采用objdump调试驱动程序
- sk_buff整理笔记（两、操作函数）
- LISTVIEW嵌套GRIDVIEW的一些处理（点击GRIDVIEW的条目，能够显示他在LISTVIEW中的位置）(对这篇文章的优化处理，不每次都new onItemClickListener)
- 在线恶意软件和URL分析集成框架 – MalSub
- 二、 添加控制器Controller（ASP.NET MVC5 系列）
- spring boot +mysql + mybatis + druid的整理（一）——单数据源
- 解析.DBC文件, 读懂CAN通信矩阵，实现车内信号仿真
- c# listview数据预览（转载的放在这里备用）
- 【干货】查看windows文件系统中的数据—利用簇号查看文件与恢复文件
- P1063 能量项链