栈和队列的相互实现

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

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

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

用栈实现队列

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

入队：

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

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

出队：

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

代码：

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());

    }
}

用队列实现栈

入栈：

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

出栈：

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

代码：

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++版代码

//用栈实现队列
#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;
}

//用队列实现栈
#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;
}