day1剑指offer leetcode

#栈

1.题目描述

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

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

2.解题思路

栈无法实现队列功能： 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。

双栈可实现列表倒序： 设有含三个元素的栈 A = [1,2,3]A=[1,2,3] 和空栈 B = []B=[]。若循环执行 AA 元素出栈并添加入栈 BB ，直到栈 AA 为空，则 A = []A=[] , B = [3,2,1]B=[3,2,1] ，即 栈 BB 元素实现栈 AA 元素倒序 。

利用栈 BB 删除队首元素： 倒序后，BB 执行出栈则相当于删除了 AA 的栈底元素，即对应队首元素。

#Python

class CQueue:

    def __init__(self):

        self.A, self.B = [], []

    def appendTail(self, value: int) -> None:

        self.A.append(value)

    def deleteHead(self) -> int:

        if self.B: return self.B.pop()

        if not self.A: return -1

        while self.A:

            self.B.append(self.A.pop())

        return self.B.pop()

#java

class CQueue {

LinkedList<Integer>A,B;

public CQueue(){

A = new LinkedList<Integer>();

B = new LinkedList<Integer>();

}

public void appendTail(int value){

A.addLast(value)

}

public int deleteHead(){

if(!B.isEmpty()) return B.removeLast();

if(A.isEmpty()) return -1;

while(!A.isEmpty()){

B.addLast(A.removeLast());

return B.removeLast();

}

}

}