美文网首页leetcode刷题
day1剑指offer leetcode

day1剑指offer leetcode

作者: curleyc | 来源:发表于2021-06-22 12:27 被阅读0次

    #栈

    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();

    }

    }

    }

    相关文章

      网友评论

        本文标题:day1剑指offer leetcode

        本文链接:https://www.haomeiwen.com/subject/jegpyltx.html