> 文档中心 > 后端秋招上岸字节刷题第一天(堆栈)多种语言实现

后端秋招上岸字节刷题第一天(堆栈)多种语言实现


提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 1.用两个栈实现队列
    • 题目描述:
    • 思路分析:
    • 代码实现:
  • 2.包含min的栈
    • 题目描述:
    • 思路分析:
    • 代码实现:
        • Java版本
  • 加入学习交流

前言:努力刷题,上岸上岸

1.用两个栈实现队列

题目描述:

后端秋招上岸字节刷题第一天(堆栈)多种语言实现

思路分析:

使用两个栈,分别为添加A栈和删除R栈

💪添加元素直接向A栈中添加元素即可

💪删除元素时

  1. 先判断R栈中是否有元素:
  2. 如果没有元素则将A栈中的元素,依次添加到R栈中,完成一次元素的反转。将R栈的栈顶元素删除即可,
  3. 如果有元素则直接将R栈的栈顶元素删除即可,
  4. 若A栈和R栈都为空,返回-1;

以上为题目的思路:

代码实现:

java版本

class CQueue {    LinkedList<Integer> stacka,stackd;    public CQueue() { stacka = new LinkedList<Integer>(); stackd = new LinkedList<Integer>();    } public void appendTail(int value) { stacka.addLast(value);    } public int deleteHead() { if(!stackd.isEmpty()) return stackd.removeLast(); if(stackd.isEmpty()&stacka.isEmpty()) return -1; while(!stacka.isEmpty()){     stackd.addLast(stacka.removeLast()); } return stackd.removeLast();    }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

python3版本

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

2.包含min的栈

题目描述:

后端秋招上岸字节刷题第一天(堆栈)多种语言实现

思路分析:

首先创建两个栈
添加元素:

  1. 首先A栈中不用判断,直接插入
  2. B栈在插入时,先判断插入的元素与B栈栈顶的元素哪个值比较小
  3. 若插入的值小,则插入到B栈中

删除元素:

  1. A栈直接删除元素即可
  2. 若A栈删除的元素和B栈的栈顶的元素一样,则B栈也要删除

top():
直接查看A栈栈顶元素即可
min():
直接查看B栈栈顶元素即可

代码实现:

Java版本

//使用stack实现class MinStack {    Stack<Integer> A, B;    public MinStack() { A = new Stack<>(); B = new Stack<>();    }    public void push(int x) { A.add(x); if(B.empty() || B.peek() >= x)     B.add(x);    }    public void pop() { if(A.pop().equals(B.peek()))     B.pop();    }    public int top() { return A.peek();    }    public int min() { return B.peek();    }}//使用LinkedList实现class MinStack {    LinkedList<Integer> Astack,Bstack;    /** initialize your data structure here. */    public MinStack() { Astack = new LinkedList<>(); Bstack = new LinkedList<>();    } public void push(int x) { Astack.addLast(x); if(Bstack.isEmpty()||Bstack.getLast()>=x)Bstack.addLast(x);    } public void pop() { int val = Astack.removeLast(); if(val==Bstack.peekLast()) Bstack.removeLast();    } public int top() { return Astack.peekLast();    } public int min() { return Bstack.peekLast();    }}/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.min(); */

加入学习交流

在这里插入图片描述