理论基础
栈与队列的底层实现有多种，可插拔，不归属于容器，而应该叫容器适配器。
232.用栈实现队列
分两个栈分别入、出，入直接进栈就可以，出栈需要分两种情况，如果出栈里有元素，弹一个出来就可以，如果是空的，要把所有入栈的元素都放到出栈里，保证顺序不变。
C++
注意pop是void类型不返回值，要先通过top获取值，再把元素弹出。
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
if (stOut.empty()) {
while (!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
int peek() {
int result = pop();
stOut.push(result);
return result;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
C#
C#里Stack初始化要new，pop是有返回值的。
public class MyQueue {
Stack<int> inStack;
Stack<int> outStack;
public MyQueue() {
inStack = new Stack<int>();
outStack = new Stack<int>();
}
public void Push(int x) {
inStack.Push(x);
}
public int Pop() {
if (outStack.Count == 0) {
while (inStack.Count != 0) {
outStack.Push(inStack.Pop());
}
}
return outStack.Pop();
}
public int Peek() {
int result = Pop();
outStack.Push(result);
return result;
}
public bool Empty() {
return inStack.Count == 0 && outStack.Count == 0;
}
}
225. 用队列实现栈
可以两个队列也可以一个队列实现。
两个队列
需要一个额外队列来对数据进行备份，主队列在弹出的时候，要先把最后一个元素前面的所有元素存到备份队列里，再把最后一个元素弹出才是栈的方式，弹出完再把备份队列放回去。
C++
-
Top不用back也可以，调用一次Top，再把元素放回队列即可（见C#），注意整清楚操作的是队列，别像第一次整混了，画个图最好。
-
back进front出。
class MyStack {
public:
queue<int> que1;
queue<int> que2;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
size--;
while(size--) {
que2.push(que1.front());
que1.pop();
}
int result = que1.front();
que1.pop();
que1 = que2;
while(!que2.empty()) {
que2.pop();
}
return result;
}
int top() {
return que1.back();
}
bool empty() {
return que1.empty();
}
};
C#
注意C#里队列是引用，不能直接=赋值，就一个东西了。
- 在 C++ 中，当两个对象使用“=”进行赋值时，会发生对象拷贝。也就是说，被赋值的对象会被拷贝一份，存储在另一个内存地址中。因此，在一般情况下，使用“=”进行赋值后，左右两边的对象是不同的对象，它们在内存中存储的位置也是不同的。但是，在某些特殊情况下，可以通过一些手段来使得赋值后左右两边的对象是同一个对象。其中一个常见的方法是使用指针或引用来进行赋值。
- 在 C# 中，赋值操作也会发生对象拷贝，不同的是，C# 中的赋值操作有值类型和引用类型之分。对于值类型，当使用“=”进行赋值时，会将右侧的值拷贝一份给左侧的变量，因此左右两边的变量是不同的对象，它们在内存中存储的位置也是不同的。对于引用类型，当使用“=”进行赋值时，会将右侧的引用拷贝一份给左侧的变量，因此左右两边的变量指向的是同一个对象，它们在内存中存储的位置也是同一个对象。
public class MyStack {
Queue<int> queue1;
Queue<int> queue2;
public MyStack() {
queue1 = new Queue<int>();
queue2 = new Queue<int>();
}
public void Push(int x) {
queue1.Enqueue(x);
}
public int Pop() {
int size = queue1.Count - 1;
while (size-- != 0) {
queue2.Enqueue(queue1.Dequeue());
}
int result = queue1.Dequeue();
while (queue2.Count != 0) {
queue1.Enqueue(queue2.Dequeue());
}
//Console.WriteLine(" 10 " + queue1.Peek());
//注意引用类型，queue1和queue2实际就是一个东西了
//Console.WriteLine(queue1.Peek());
return result;
}
public int Top() {
Console.WriteLine(queue1.Peek());
int result = Pop();
//还得放回去
Console.WriteLine(result);
queue1.Enqueue(result);
//Console.WriteLine(queue1.Peek());
return result;
}
public bool Empty() {
return queue1.Count == 0;
}
}
一个队列
C++
把size-1个元素取出再放入，就把最后面的元素放到了队列最前面，再弹出即可。
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
size--;
while (size--) {
int tmp = que.front();
que.pop();
que.push(tmp);
}
int result = que.front();
que.pop();
return result;
}
int top() {
int result = pop();
que.push(result);
return result;
}
bool empty() {
return que.empty();
}
};
C#
public class MyStack {
Queue<int> que = new Queue<int>();
public MyStack() {
}
public void Push(int x) {
que.Enqueue(x);
}
public int Pop() {
int size = que.Count;
size--;
while (size-- > 0) {
que.Enqueue(que.Dequeue());
}
return que.Dequeue();
}
public int Top() {
int result = Pop();
que.Enqueue(result);
return result;
}
public bool Empty() {
return que.Count == 0;
}
}
二刷
用栈实现队列
一个入栈，一个出栈，出栈的时候如果出栈为空，就把入站的全部放进来，否则就按现在弹出，从入栈到出栈的过程顺序就变成队列的顺序了。
#include<iostream>
#include<stack>
using namespace std;
class MyQueue {
public:
stack<int> inStack;
stack<int> outStack;
MyQueue() {
}
void push(int x) {
inStack.push(x);
}
int pop() {
if (outStack.empty()) {
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
int temp = outStack.top();
outStack.pop();
return temp;
}
int peek() {
if (outStack.empty()) {
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
return outStack.top();
}
bool empty() {
return inStack.empty() && outStack.empty();
}
};
用队列实现栈
一个队列就可以，每次push的时候把原来队列中的元素全部取出放到push元素的后面，就完成了顺序转换。
#include<iostream>
#include<queue>
using namespace std;
class MyStack {
public:
queue<int> qe;
MyStack() {
}
void push(int x) {
qe.push(x);
int cnt = qe.size() - 1;
while (cnt--) {
int temp = qe.front();
qe.pop();
qe.push(temp);
}
}
int pop() {
int temp = qe.front();
qe.pop();
return temp;
}
int top() {
return qe.front();
}
bool empty() {
return qe.empty();
}
};
京公网安备 11010502036488号