剑指 Offer 09. 用两个栈实现队列----20211228

剑指 Offer 09. 用两个栈实现队列----2021/12/28 栈与队列 剑指 Offer 09. 用两个栈实现队列-2021/12/28

    用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在
    队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead  *** 作返回 -1 )
    
#   示例 1：
    输入：
    ["CQueue","appendTail","deleteHead","deleteHead"]
    [[],[3],[],[]]
    输出：[null,null,3,-1]
    
#   提示：
    1 <= values <= 10000
    最多会对 appendTail、deleteHead 进行 10000 次调用

题目解读:

	[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”] ：这里表示的是按顺序执行每一步函数 *** 作。
	然后[[],[3],[],[]]代表每一个函数所需要的参数。
# 举例：
    CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此 *** 作不需要参数。appendTail 表示
    执行一个appendTail() *** 作，函数对应要所需要的参数为3。deleteHead 表示执行一个deleteHead *** 作，
    对应的所需参数为[]，即此 *** 作不需要参数。

解题思路:

• 栈 stack1 添加数据、栈stack2 删除数据

• 判断stack2是否为空

  1. 否------返回值

  2. 是------进行下一步

• 判断stack1是否为空

  1. 是-----返回-1
  2. 否-----当stack1不为空是，一直d出数据，并推入stack2中，然后stack2d出

Java代码:

import java.util.Stack;
public class CQueue{
    Stack stack1,stack2;

    public CQueue(){
        stack1 = new Stack();
        stack2 = new Stack();
    }

    public void appendTail(int value){
        stack1.push(value);
    }

    public int deleteHead(){
        // stack2不为空，将stack2的值d出
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        // stack1为空，返回-1
        // 注意：此处必须要放在下面，这是因为Stack *** 作会删除元素，此时stack1已经是空的了
        if(stack1.isEmpty()){
            return -1;
        }
        // 运行到这说明，stack2为空，需要将stack1的值赋给stack2，形成了一次倒叙
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        };
        return stack2.pop();
    }

    public static void main(String [] args){
        CQueue obj = new CQueue();
        System.out.println(obj.deleteHead());
        obj.appendTail(5);
        obj.appendTail(2);
        System.out.println(obj.deleteHead());
        System.out.println(obj.deleteHead());
    }

}