【数据结构】数据结构中的栈——Java_栈的存取时间复杂度

数据结构中的栈 Java

1.栈的概念

栈是一种特殊的线性表，只能在一段进行插入和删除操作，遵循先进后出原则。

1. 栈是先进后出的，那么入栈和出栈的时间复杂度是多少？
   由于入栈和出栈都是在栈顶进行操作，所以入栈和出栈的时间复杂度统一都为O（1）
2. 栈有顺序存储，也有链式存储，栈的链式存储是什么样的？
   假如栈是对单向链表存储，那么插入数据有头插和尾插
   （1） 入栈是尾插法，时间复杂度为O（N）
   出栈，删除尾结点时间复杂度为O（N）
   （2）入栈是头插法，时间复杂度为O（1）
   出栈，删除头节点时间复杂度O（1）

所以当栈的存储方式为链式并且是单链表时， 入栈选头插法是最好的选择。

3. 如果是双向链表，那么我们该从哪里入栈出栈？
   （1）从头入栈，从头出栈
   （2）从尾入栈，从尾出栈
   两种时间复杂度都是O（1），所以那种方式都可以对于双向链表。

2.栈的模拟实现

栈继承了Vector，Vector和ArrayList类似，属于动态顺序表，Vector属于线程安全。

//创建一个栈
public class Stack {
    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_CAPATI  = 5;
    public Stack(){
        elem = new int[DEFAULT_CAPATI];
    }
}
1
2
3
4
5
6
7
8
9

//入栈push()
    //判满
    public boolean isFull(){
        if (usedSize == elem.length){
            return true;
        }
        return false;
    }
    public void push(int val){
        if (isFull()){
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//出栈pop()
    //判空
    public boolean isEmpty(){
        return usedSize == 0;
    }
    //如果栈是空 抛出一个异常  EmptyStackException
    public class EmptyStackException  extends RuntimeException{
        public EmptyStackException(){
            
        }
        public EmptyStackException(String msg){
            super(msg);
        }
    }
    public int  pop(){
        if (isEmpty()){
            throw new EmptyStackException("栈是空栈");
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        return oldVal;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//获取栈顶元素 peek()
    public int peek(){
        if (isEmpty()){
            throw new EmptyStackException("栈是空栈");
        }
        return elem[usedSize-1];
    }
   
1
2
3
4
5
6
7
8

 
    //获取有效元素个数
    
    public int getUsedSize(){
        return usedSize;
    }
1
2
3
4
5
6

3.栈的使用

public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.pop();
        System.out.println(stack.getUsedSize());
        System.out.println(stack.peek());
    }
1
2
3
4
5
6
7
8
9
10

4.关于栈的面试题（LeetCode）

括号匹配

括号匹配

思路：我们考虑使用栈，当遇到匹配的最小括号对时，我们将这对括号从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是。

代码展示：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='{'  || ch=='('||ch=='['){
                stack.push(ch);
            }else{
                //说明是右括号
                if(stack.empty()){
                    //右括号多
                    return false;
                }
                char top =stack.peek();
                if(ch==')' && top=='('  || ch==']' && top=='['  || ch=='}' && top=='{' ){
                    //只能说明当前字符匹配
                    stack.pop();
                }else{
                    //左右括号不匹配
                    return false;
                }
                
            }
        }
        if(stack.empty()){
                    return true;
                    }else{
                    return false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

逆波兰表达式

逆波兰表达式

逆波兰表达式，也叫做后缀表达式。
下图中左边是中缀表达式，中间是其对应的语法树，右边是语法树转成的后缀表达式。

对逆波兰表达式求值的过程是：

如果遇到数字就进栈；
如果遇到操作符，就从栈顶弹出两个数字分别为 num2（栈顶）、num1（栈中的第二个元素）；计算num1 运算 num2

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String x : tokens) {
            //不是加减乘法
            if(!isOperation(x)) {
                stack.push(Integer.parseInt(x));
            }else{
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(x) {
                    case "+" :
                        stack.push(num1+num2);
                        break;
                    case "-" :
                        stack.push(num1-num2);
                        break;
                    case "*" :
                        stack.push(num1*num2);
                        break;
                    case "/" :
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String opera) {
        if(opera.equals("+") || opera.equals("-") || opera.equals("*") ||  opera.equals("/") ) {
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

栈的压入、弹出序列

栈的压入、弹出序列

思路：

代码展示：

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        //入栈过程中可以出栈
        if(pushA.length==0 || popA.length ==0){
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;
      for(int i = 0;i < pushA.length;i++){
          stack.push(pushA[i]);
          
          while(j<popA.length && !stack.empty() && stack.peek().equals( popA[j]){
              stack.pop();
              j++;
          }
      }  
        return stack.empty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22