记一道面试题：STL两个栈实现一个队列。

川长思鸟来 2022-05-29 08:42 137阅读 0赞

# 面试题目 #

**STL两个栈实现一个队列。**

要求：只能使用栈的pop(),top()和push()，以及测试栈是否为空 empty()四个操作. 来实现队列的clear(), push(),pop(),back(),front()等操作。

# 思路解析 #

用一个栈用作队列的容器，另一个栈用作临时容器，由于**队列 具有先进先出的特性，而我们的栈 只有一端可以进出，那么我们在做出队，也就是 要将一个栈的栈底元素 出队，所以要用到另一个栈作为辅助容器**。

# 代码展示 #

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <stack>
    using namespace std;
    template<class T>
    class MyQueue
    {
    	//对外接口
    public:
    	//清空队列
    	void clear()
    	{
    		while (!stack1.empty())
    			stack1.pop();
    		while (!stack2.empty())
    			stack2.pop();
    	}
    	//入队
    	void push(T data)	
    	{
    		stack1.push(data);	//stack1用来 入队
    	}
    	//出队
    	T pop()
    	{
    		if (stack2.size() == 0)	//stack2用来 出队，将stack1元素倒腾到stack2
    		{
    			while (stack1.size() > 0)
    			{
    				T top = stack1.top();
    				stack1.pop();
    				stack2.push(top);
    			}
    		}
    		if (stack2.size() == 0)
    			throw std::exception("queue is empty");
    		T top = stack2.top();
    		stack2.pop();
    		return top;
    	}
    	//队尾
    	T back()	//入队的，最后一个元素
    	{
    		if (stack1.size() > 0)	//stack1中有数据，栈顶为最后入队的元素
    			return stack1.top();
    
    		while(stack2.size() > 0) //stack1中没有数据，stack2中有元素，栈底为入队的最后一个元素，将stack2中的数据倒腾到stack1
    		{
    			T top = stack2.top();
    			stack2.pop();
    			stack1.push(top);
    		}
    
    		if (stack1.size() == 0)
    			throw std::exception("queue is empty");
    		return stack1.top();
    	}
    	//队头
    	T front()	//出队的，第一个元素，
    	{
    		if (stack2.size() == 0)	//stack2用来 出队，将stack1元素倒腾到stack2
    		{
    			while (stack1.size() > 0)
    			{
    				T top = stack1.top();
    				stack1.pop();
    				stack2.push(top);
    			}
    		}
    		if (stack2.size() == 0)
    			throw std::exception("queue is empty");
    		return stack2.top();
    	}
    private:
    	stack<T> stack1;	
    	stack<T> stack2;
    };
    /*
    STL两个栈实现一个队列。
    
    要求：只能使用栈的pop(),top()和push()，以及测试栈是否为空
    empty()四个操作. 来实现队列的clear(), push(),pop(),back(),front()等操作。
    */
    int main(int argc, char *argv[])
    {
    	MyQueue<int> que;
    	que.push(1);
    	que.push(2);
    	que.push(3);
    	// 出队<-  1  2  3 <-入队
    	cout << que.front() << endl;//1
    	cout << que.back() << endl;	//3
    	
    	cout << que.pop() << endl;//1
    	cout << que.pop() << endl;//2
    	cout << que.pop() << endl;//3
    	
    	que.clear();
    
    	return EXIT_SUCCESS;
    }

# 运行结果 #

![20180523083521247][]

[20180523083521247]: /images/20220529/9b0a762b95484957b156234a48de4fc1.png