前言

通过我之前的作品已经初步理解了栈和队列的数据结构，这期我们来学习如何实现这两个数据结构的互相转换。在计算机科学中，栈（Stack）和队列（Queue）是两种常见的数据结构，它们具有不同的操作特性和应用场景。栈遵循后进先出（LIFO, Last In First Out）的原则，而队列遵循先进先出（FIFO, First In First Out）的原则。尽管它们有不同的特性，但我们可以利用其中一种数据结构来实现另一种数据结构。

一、用栈实现队列

操作：

要使用栈来实现队列，我们需要两个栈：一个用于处理入队操作（stack_in），另一个用于处理出队操作（stack_out）。

入队（Enqueue）：
直接将元素压入 stack_in。

出队（Dequeue）：
如果 stack_out 为空，则将 stack_in 中的所有元素逐个弹出并压入 stack_out（这样原来 stack_in 中的栈底元素就移动到了 stack_out 的栈顶）。然后从 stack_out 弹出栈顶元素。

检查队列是否为空（IsEmpty）：
当 stack_in 和 stack_out 都为空时，队列为空。

查看队列的头部元素（Peek）：
类似于出队操作，但如果 stack_out 为空，则将 stack_in 中的所有元素移动到 stack_out，然后返回 stack_out 的栈顶元素（但不弹出）。

c++代码模版

#include<iostream>
#include<exception>
using namespace std;template<typename T>//定制栈里面的元素，就像vector一样
class Stack {
private:int size;//既为栈元素个数又为栈顶位置int capacity;T* data;void resize();
public:Stack() :data(new T[capacity]), size(0), capacity(10) {}//构造函数，申请类型为T容量为capacity的内存空间，相当于数组~Stack();void push(T x);T top() const;T pop();int getSize() const;bool empty() const;
};template<typename T>
void Stack<T>::resize() {//顺序栈扩容int newCapacity = 2 * capacity;T* newData = new T[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}delete[]data;data = newData;capacity = newCapacity;
}template<typename T>
Stack<T>::~Stack() {delete[]data;
}template<typename T>
void Stack<T>::push(T x) {if (size == capacity) {resize();}data[size++] = x;
}template<typename T>
T Stack<T>::top() const {if (!size) {throw std::underflow_error("Stack is empty");//如果栈为空即为非法状态，抛出异常}return data[size - 1];//注意栈元素序号从零开始
}template<typename T>
T Stack<T>::pop() {if (!size) {throw std::underflow_error("Stack is empty");}return data[--size];
}template<typename T>
int Stack<T>::getSize() const {return size;
}template<typename T>
bool Stack<T>::empty() const {return size == 0;
}class MyQueue {
private:Stack<int> s1;//s1作为辅助栈Stack<int> s2;
public:MyQueue(){}void push(int x) {s1.push(x);//队列插入元素，就是把元素插入s1中}int pop() {if (s2.empty()) {//队列出队操作，就是将s1中谈栈入栈到s2中，队首就是s2的栈顶while (!s1.empty()) {s2.push(s1.pop());}}return s2.pop();}int peek() {//去队首函数if (s2.empty()) {while (!s1.empty()) {s2.push(s1.pop());}}return s2.top();}bool empty() {//队列判空函数return s1.empty() && s2.empty();}
};int main() {MyQueue m;for (int i = 0; i < 5; i++) {m.push(i);}cout << m.peek() << endl;return 0;
}

经典例题

面试题 03.04. 化栈为队
（蓝色字体可以点进去看原题）

代码题解

template<typename T>//定制栈里面的元素，就像vector一样
class Stack {
private:int size;//既为栈元素个数又为栈顶位置int capacity;T* data;void resize();
public:Stack() :data(new T[capacity]), size(0), capacity(10) {}//构造函数，申请类型为T容量为capacity的内存空间，相当于数组~Stack();void push(T x);T top() const;T pop();int getSize() const;bool empty() const;
};template<typename T>
void Stack<T>::resize() {//顺序栈扩容int newCapacity = 2 * capacity;T* newData = new T[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}delete[]data;data = newData;capacity = newCapacity;
}template<typename T>
Stack<T>::~Stack() {delete[]data;
}template<typename T>
void Stack<T>::push(T x) {if (size == capacity) {resize();}data[size++] = x;
}template<typename T>
T Stack<T>::top() const {if (!size) {throw std::underflow_error("Stack is empty");//如果栈为空即为非法状态，抛出异常}return data[size - 1];//注意栈元素序号从零开始
}template<typename T>
T Stack<T>::pop() {if (!size) {throw std::underflow_error("Stack is empty");}return data[--size];
}template<typename T>
int Stack<T>::getSize() const {return size;
}template<typename T>
bool Stack<T>::empty() const {return size == 0;
}class MyQueue {
private:Stack<int> s1;//s1作为辅助栈Stack<int> s2;
public:MyQueue(){}void push(int x) {s1.push(x);//队列插入元素，就是把元素插入s1中}int pop() {if (s2.empty()) {//队列出队操作，就是将s1中谈栈入栈到s2中，队首就是s2的栈顶while (!s1.empty()) {s2.push(s1.pop());}}return s2.pop();}int peek() {//去队首函数if (s2.empty()) {while (!s1.empty()) {s2.push(s1.pop());}}return s2.top();}bool empty() {//队列判空函数return s1.empty() && s2.empty();}
};

二、用队列实现栈

要使用队列来实现栈，我们可以使用一个队列（queue）和两个辅助变量：size 用于跟踪队列中的元素数量，main_queue 和 temp_queue 用于操作。

操作：

入栈（Push）：
将新元素添加到 temp_queue。
将 main_queue 中的所有元素依次出队并重新入队到 temp_queue（这样原来 main_queue 中的最后元素就到了 temp_queue 的前面）。交换 main_queue 和 temp_queue 的引用。

出栈（Pop）：
从 main_queue 出队元素（因为 main_queue 的第一个元素就是栈顶元素）。

检查栈是否为空（IsEmpty）：
当 main_queue 为空时，栈为空。

查看栈顶元素（Peek）：
返回 main_queue 的第一个元素（但不出队）。

c++代码模版

#include<iostream>
#include<exception>
using namespace std;template<typename T>
class Queue {
private:int front;int rear;int capacity;T* data;void resize();
public:Queue() :data(new T[capacity]), front(0), rear(0), capacity(10) {}~Queue();void Enqueue(T x);T Dequeue();T getFront();int size();bool empty();
};template<typename T>
void Queue<T>::resize() {int newCapacity = capacity * 2;T* newData = new T[newCapacity];for (int i = front; i < rear; i++) {newData[i] = data[i];}delete[] data;data = newData;capacity = newCapacity;
}template<typename T>
Queue<T>::~Queue() {delete[]data;
}template<typename T>
void Queue<T>::Enqueue(T x) {if (rear == capacity) resize();data[rear++] = x;
}template<typename T>
T Queue<T>::Dequeue() {if (front == rear) {throw std::underflow_error("Queue is empty!");}return data[front++];
}template<typename T>
T Queue<T>::getFront() {if (front == rear) {throw std::underflow_error("Queue is empty!");}return data[front];
}template<typename T>
int Queue<T>::size() {return rear - front;
}template<typename T>
bool Queue<T>::empty() {return size() == 0;
}class MyStack {
private:Queue<int>q1;//辅助队列Queue<int>q2;
public:void push(int x) {q1.Enqueue(x);}int pop() {while (q1.size() > 1) {q2.Enqueue(q1.Dequeue());}int ret = q1.Dequeue();while (!q2.empty()) {q1.Enqueue(q2.Dequeue());}return ret;}int top() {while (q1.size() > 1) {//把q1除队尾以为元素存入q2,剩下的元素就是栈顶q2.Enqueue(q1.Dequeue());}int ret = q1.Dequeue();//去除栈顶以后记得将该值放进q2q2.Enqueue(ret);while (!q2.empty()) {q1.Enqueue(q2.Dequeue());}return ret;}bool empty() {return q1.empty();}
};int main() {MyStack s;for (int i = 0; i < 5; i++) {s.push(i);}cout << s.top() << endl;int x = s.pop();cout << x << endl;cout << s.empty() << endl;return 0;
}

经典例题

225. 用队列实现栈

代码题解

template<typename T>
class Queue {
private:int front;int rear;int capacity;T* data;void resize();
public:Queue() :data(new T[capacity]), front(0), rear(0), capacity(10) {}~Queue();void Enqueue(T x);T Dequeue();T getFront();int size();bool empty();
};template<typename T>
void Queue<T>::resize() {int newCapacity = capacity * 2;T* newData = new T[newCapacity];for (int i = front; i < rear; i++) {newData[i] = data[i];}delete[] data;data = newData;capacity = newCapacity;
}template<typename T>
Queue<T>::~Queue() {delete[]data;
}template<typename T>
void Queue<T>::Enqueue(T x) {if (rear == capacity) resize();data[rear++] = x;
}template<typename T>
T Queue<T>::Dequeue() {if (front == rear) {throw std::underflow_error("Queue is empty!");}return data[front++];
}template<typename T>
T Queue<T>::getFront() {if (front == rear) {throw std::underflow_error("Queue is empty!");}return data[front];
}template<typename T>
int Queue<T>::size() {return rear - front;
}template<typename T>
bool Queue<T>::empty() {return size() == 0;
}class MyStack {
private:Queue<int>q1;//辅助队列Queue<int>q2;
public:void push(int x) {q1.Enqueue(x);}int pop() {while (q1.size() > 1) {q2.Enqueue(q1.Dequeue());}int ret = q1.Dequeue();while (!q2.empty()) {q1.Enqueue(q2.Dequeue());}return ret;}int top() {while (q1.size() > 1) {//把q1除队尾以为元素存入q2,剩下的元素就是栈顶q2.Enqueue(q1.Dequeue());}int ret = q1.Dequeue();//去除栈顶以后记得将该值放进q2q2.Enqueue(ret);while (!q2.empty()) {q1.Enqueue(q2.Dequeue());}return ret;}bool empty() {return q1.empty();}
};

三、总结

通过以上方法，我们可以使用栈来实现队列，或使用队列来实现栈。这些实现虽然效率不如直接使用相应的数据结构（因为涉及额外的操作），但它们展示了数据结构之间的转换和灵活性。

四、结语

通过本次学习相信大家对栈和队列这两个数据结构有更深刻理解了，希望大家多刷题巩固知识点，那么下期我们一起学习初级数据结构——串。

想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家