【C++面试题】利用两个栈实现1个队列

1、题目 利用两个栈实现一个队列

2、要求

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

3、准备 做这道题之前先分别了解下栈和队列相关知识点。queue 是一种先进先出(first in first out, FIFO)的数据类型,他有两个口,数据元素只能 从一个口进,从另一个口出.队列只允许从队尾加入元素,队头删除元素,必须符合先进先 出的原则,queue 和 stack 一样不具有遍历行为。如下图所示:

stack 是一种先进后出(first in last out,FILO)的数据结构,它只有一个出口,stack 只允许在栈顶新增元素,移除元素,获得顶端元素,但是除了顶端之外,其他地方不允许存取 元素,只有栈顶元素可以被外界使用,也就是说 stack 不具有遍历行为,没有迭代器。

4、思路总结

//
//  利用两个栈实现⼀个队列.cpp
//  c++
//
//  Created by 刘龙玲 on 16/1/29.
//  Copyright © 2016年 liulongling. All rights reserved.
//#include 
#include using namespace std;template 
class MyQueue
{
public:bool empty()const{return head.empty()&&tail.empty();}void push(T t){head.push(t);}//删除对头元素//因为queue是一种先进先出，而stack是先进后出，所以需要把head里的数据拷贝到tail中然后再从tail中pop头元素void pop(){if(this->empty()){//throw exception("队列为NULL");}while(!head.empty()){tail.push(head.top());head.pop();}//删除头元素tail.pop();//再将队尾栈容器元素拷贝到队头栈容器中while(!tail.empty()){head.push(tail.top());tail.pop();}}T& back(){if(this->empty()){// throw exception("head is NULL");}return head.top();}//返回第一个元素T& front(){if(this->empty()){//throw exception("队列为NULL");}while(!head.empty()){tail.push(head.top());head.pop();}int tmp =  tail.top();//再将队尾栈容器元素拷贝到队头栈容器中while(!tail.empty()){head.push(tail.top());tail.pop();}return tmp;}private:stack head;stack tail;
};int main()
{MyQueue q;for(int i=1;i<5;i++){q.push(i);}cout<<"front:"<