栈和队列的相互实现

栈（stack）：先进后出，后进先出。限定在表尾进行插入删除的线性表。

队列（queue）：先进先出，后进后出。限定在表头删除，在表尾插入的线性表。

那么如何用栈来实现队列和如何用队列来实现栈的数据结构呢？

一、用栈实现队列

单个栈肯定无法实现队列，所以至少应该用两个栈来实现队列。

入队：

• 数据栈：每次有新元素来时，先把存放的元素弹入辅助栈，再把新元素压入数据栈底；
• 辅助栈：等待新元素进入数据栈以后依次弹出元素压入数据栈中；

根据这两个栈的功能，不管是数据栈中是否有元素存在，新元素都会被沉到栈底中，实现入队的功能。

出队：

由于在入队时，通过数据栈与辅助栈的交换，实现了后加入的元素沉在栈底，先进入的元素保留在栈顶，直接通过出栈弹出即可

Java代码实现：

public class StackImplQueue {// 数据栈private Stack<Integer> stack;// 辅助栈private Stack<Integer> aux;StackImplQueue() {stack = new Stack<>();aux = new Stack<>();}// 入队--通过数据栈与辅助栈相互交换，保证新加入的元素沉在数据栈底public void enqueue(Integer e) {while (!stack.isEmpty()) {aux.push(stack.pop());}stack.push(e);while(!aux.isEmpty()){stack.push(aux.pop());}}// 出队--弹出数据栈元素public Integer dequeue(){return stack.pop();}// 查看队头元素public Integer peek(){return stack.peek();}// 是否为空public boolean isEmpty(){return stack.isEmpty();}public static void main(String[] args) {StackImplQueue queue = new StackImplQueue();queue.enqueue(1);System.out.println(queue.peek());queue.enqueue(2);System.out.println(queue.peek());queue.enqueue(3);System.out.println(queue.peek());System.out.println("=============");System.out.println(queue.dequeue());System.out.println(queue.dequeue());System.out.println(queue.dequeue());}
}

二、用队列实现栈

入栈：

入栈的元素要在队头，而队列入队的元素在队尾，只需让队头至队尾前的其它所有元素依次出队再入队，直至在队尾新加入的元素被移到队头，也即实现了让新压入的元素保留在栈顶。

出栈：

由于在入栈时保证队列中新加入队尾的元素被移到了队头，出栈只需弹出队头元素即可

Java代码实现：

public class QueueImplStack {// 定义队列private Queue<Integer> queue;public QueueImplStack() {queue = new LinkedList();}// 入栈--在队尾加入元素后,让其他元素按顺序出队再入队，保持新加入的元素永远在队头public void push(Integer e) {queue.offer(e);int size = queue.size();int i = 0;while (i < size - 1) {queue.offer(queue.poll());i++;}}// 出栈--将队尾前的其它所有元素出队再入队，直至队尾元素移到队头public Integer pop() {return queue.poll();}// 查看栈顶元素--即队头元素public Integer peek() {return queue.peek();}// 是否为空public boolean isEmpty() {return queue.isEmpty();}public static void main(String[] args) {QueueImplStack stack = new QueueImplStack();stack.push(1);System.out.println(stack.peek());stack.push(2);System.out.println(stack.peek());stack.push(3);System.out.println(stack.peek());System.out.println("=============");System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.isEmpty());}
}

附：C++版代码

1、用栈实现队列

#include<stack>
#include<iostream>using namespace std;class queue{
public:stack<int> dataStack;//数据栈 stack<int> auxStack;//辅助栈//入队，通过辅助栈让新元素沉于栈底
void push(int x) {while(!dataStack.empty()){auxStack.push(dataStack.top());dataStack.pop();}dataStack.push(x);while(!auxStack.empty()){dataStack.push(auxStack.top());auxStack.pop();}
}// 出队--弹出数据栈元素int outqueue(){int temp = dataStack.top();dataStack.pop();return temp;}// 查看队头元素int top(){return dataStack.top();}// 是否为空bool empty(){return dataStack.empty();}};int main(){queue iq;iq.push(1);cout<<iq.top()<<endl;iq.push(2);cout<<iq.top()<<endl;iq.push(3);cout<<iq.top()<<endl;cout<<"-------------"<<endl;cout<<iq.outqueue()<<endl;cout<<iq.outqueue()<<endl;cout<<iq.outqueue()<<endl;	return 0;
}

2、用队列实现栈

#include<deque>
#include<iostream>using namespace std;class stack{
public:deque<int> de;// 入栈--在队尾加入元素后,让其他元素按顺序出队再入队，保持新加入的元素永远在队头void push(int x) {de.push_front(x);int size = de.size();int i = 0;while (i < size - 1) {de.push_front(de.back());de.pop_back();i++;}}// 出栈--将队尾前的其它所有元素出队再入队，直至队尾元素移到队头int pop() {int temp = de.front();de.pop_front();return temp;}// 查看栈顶元素--即队头元素int top() {return de.front();}// 是否为空bool isEmpty() {return de.empty();}			
};int main(){stack iq;iq.push(1);cout<<iq.top()<<endl;iq.push(2);cout<<iq.top()<<endl;iq.push(3);cout<<iq.top()<<endl;cout<<"-------------"<<endl;cout<<iq.pop()<<endl;cout<<iq.pop()<<endl;cout<<iq.pop()<<endl;	return 0;
}

本文参考来源：

• 用队列实现栈，用栈实现队列，听起来有点绕，都搞懂了就掌握了精髓！ - 云+社区 - 腾讯云 (tencent.com)
• 《小灰的算法之旅》