题目描述

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

样例

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

提示

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

题目链接
https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

解题思路

这题的话,The main thing is to consider how to use two stacks to achieve the effect of a queue,Can think of a solution for this,这题就迎刃而解了.

我的思路是,一个栈用来入队,Then another stack is used to dequeue.

Whenever you need to go out,First check whether there are elements in the dequeued queue（Certainly not at first）：

• 如果没有的话,Put all the elements in the enqueue queue into the dequeue queue,这里是关键.Every time we dequeue an element, we put that element into another queue,This just reverses the order of the elements in the stack,And since the queue is first in first out,Therefore, the elements inserted later have no effect on the previous elements.
• 如果有的话,Then just pop the stack,Return the element that is popped from the stack.

代码

中规中矩,Java代码：

class CQueue {
    

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public CQueue() {
    

    }
    
    public void appendTail(int value) {
    
        stack1.push(value);
    }
    
    public int deleteHead() {
    
        if ( !stack2.empty() ) {
    
            return stack2.pop();
        }
        
        while( !stack1.isEmpty() ) {
    
            stack2.push(stack1.pop());
        }
        if (!stack2.empty()) 
            return stack2.pop();
        else 
            return -1;
    }
}