剑指offer 09.用两个栈实现队列——30.包含min函数的栈

2021年11月25日 阅读数:4
这篇文章主要向大家介绍剑指offer 09.用两个栈实现队列——30.包含min函数的栈,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。


题目描述:(栈和队列)数据结构

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

 

解题思路:ide

 

1.栈没法去实现队列功能:栈底元素没法直接删除,须要将上方的全部元素出栈函数

2.使用双栈便可实现列表倒序及列表元素删除功能spa

 

 

对于这题咱们能够直接使用两个函数,利用栈A用于加入队尾操做,栈B用于删除操做(将A元素倒序)code

 

 1 class CQueue{
 2 
 3 LinkedList<Integer> A.B;
 4    public CQuere(){
 5       
 6     A = new LinkedList<Integer>();
 7     B = new LinkedList<Integer>();
 8       }
 9 //加入操做
10    public void appendTail(int value){
11            
12            A.addLast(value);
13 
14       }
15 
16    public int deleteHead(){
17 
18        if(!B.isEmpty())  return B.removeLast();
19        if(A.isEmpty())  return -1;
20        while(!A.isEmpty()){
21                     B.addLast(A.removeLast());
22                 }
23      return B.removeLast();
24       }
25 
26 }

 

 

 

30——定义栈的数据结构,请在该类型中实现一个可以获得栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。队列

 

 

解题思路:rem

因为普通栈的push()和pop()函数的复杂度为O(1) ;而获取栈的最小值min() 函数须要遍历整个栈,复杂度为O(N)it

咱们若是要下降复杂度的话,能够创建经过辅助栈实现ast

数据栈A:栈A用于储存全部元素,保证入栈的push函数,出栈的pop函数,及获取栈顶的top函数的正常逻辑

辅助栈B:栈B用来储存A中全部“非严格降序”的元素,栈A中的最小元素始终对应栈B的栈顶元素,因此min函数只要返回B的栈顶元素便可

 1 class MinStack{
 2 
 3 Stack<Integer> A,B;
 4 public MinStack(){
 5 
 6 A = new Stack<Integer>();
 7 B = new Stack<Integer>();
 8       }
 9 
10 public void push(int x){
11 A.add(x);
12 if(B.isEmpty() || B.peek() >= x){
13           B.add(x);
14              }
15        }
16 public void pop(){
17 
18    if(A.pop().equals(B.peek()){
19            B.pop();
20 }
21        }
22 public int top(){
23         return A.peek();
24       }
25 
26 public int min(){
27        return B.peek();
28       }
29 }