标题

剑指offer 两个栈实现队列


一、题目描述:

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例:

["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]

二、过程

想法就是用两个栈来实现队列,队列是先进先出,栈是先进后出,入队时候直接进in栈,出队时候把in栈放入out栈,然后出栈顶;

1.引入库

stack<int> Stack;//c++函数库直接引用栈

2.代码

初始化栈,清空栈

 CQueue() {
        while(!in.empty()){
            in.pop();
        }
        while(!out.empty()){
            out.pop();
        }
    }

入队

void appendTail(int value) {
        in.push(value);
    }

出队

  int deleteHead() {
        if(out.empty()){
            while(!in.empty()){
                out.push(in.top());
                in.pop();
            }
        }
        if(out.empty()){
            return -1;
        }
        int x=out.top();
        out.pop();
        return x;
    }