Sword finger offer09 Implementing queues with two stacks

The finger of the sword Offer09. Queues are implemented with two stacks

Title Description

Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions appendTail and deleteHead , The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .( If there are no elements in the queue ,deleteHead Operation return -1 )

Example 1：

 Input ：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
 Output ：[null,null,3,-1]

Example 2：

 Input ：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
 Output ：[null,-1,null,null,5,2]

Tips ：

1 <= values <= 10000 At most appendTail、deleteHead Conduct 10000 Secondary call

JAVA Code

Algorithm design idea

Stack features last in first out , The queue is characterized by first in, first out .
therefore , When using two stacks stackA,stackB When simulating a queue ,stackA As input stack , Stack elements one by one , Simulate queue entry .
stackB As output stack , Simulate the team .
When the simulation is out of the team , If stackB If there is data, it will be directly out of the stack , Otherwise it would be stackA Withdraw from the stack and press in one by one stackB in ,stackA The first element on the stack is stackB At the top of the stack . When this is done ,stackB Backstack , It is equivalent to the first in, first out of the queue .
Team space ： When stackA and stackB It's all empty time .

Classical method

class CQueue {
    

    Stack<Integer> stackA;
    Stack<Integer> stackB;

    public CQueue() {
    
        // Create two new stacks ,stackA As the tail of the queue , To join the team ,stackB As the head of the queue , Used to get out of the team .
        stackA= new Stack<Integer>();
        stackB = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
    
        // hypothesis stack Is infinite , You don't have to judge stackA The stack is full .
        stackA.push(value);
    }
    
    public int deleteHead() {
    
        if(stackB.isEmpty()){
    
            // No data 
            if(stackA.isEmpty()){
    
                return -1;
            }else{
    
            //stackB It's empty ,stackA Isn't empty , take stackA Array stack of , Then enter the stack to stackB in , Then simulate the team operation .
                while(!stackA.isEmpty()){
    
                    stackB.push(stackA.pop());
                }
            }
        }
        // Out of the team 
        return stackB.pop();
    }
}

/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

Official methods

According to the official method , Revised as follows ：
because Stack Low performance , The official has not recommended it , So we can modify the creation method of stack
Now the official recommendation is java.util.Deque. Similar to the following usage ：

Deque<Integer> stackA = new ArrayDeque<Integer>();

Reference resources ： There are dynamic graphic demonstrations

https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/tu-jie-guan-fang-tui-jian-ti-jie-yong-li-yjbf/

expand ：Deque Methods