栈-Java实现栈数据结构

红太狼 2023-07-16 12:55 31阅读 0赞

### 1、栈的基本概念 ###

栈（英语：stack）又称为堆栈或堆叠，栈作为一种数据结构，是一种只能在一端进行插入和删除  
操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，  
需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插  
入与删除操作中，不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶  
(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为  
进栈（PUSH），删除则称为退栈（POP）。

由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运  
作。栈也称为后进先出表。

这里以羽毛球筒为例，羽毛球筒就是一个栈，刚开始羽毛球筒是空的，也就是空栈，然后我们一个  
一个放入羽毛球，也就是一个一个push进栈，当我们需要使用羽毛球的时候，从筒里面拿，也就是pop  
出栈，但是第一个拿到的羽毛球是我们最后放进去的。

### 2、Java模拟简单的顺序栈实现 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]

package person.shw.structure;
    
    /**
     * @author Administrator
     * @create 2020/3/18
     * @since 1.0.0
     */
    public class MyStack {
        
    
        private Object[] array;
        private int maxSize;
        private int top;
    
        // 初始化栈
        public MyStack(int size) {
        
            this.maxSize = size;
            array = new Object[size];
            top = -1;
        }
    
        // 元素入栈
        public void push(Object value){
        
            if (top < maxSize-1){
        
                array[++top] = value;
            }
        }
    
        // 元素出栈
        public Object pop() {
        
            return array[top--];
        }
    
        // 访问栈顶元素
        public Object peek() {
        
            return array[top];
        }
    
        // 判断栈是否为空
        public boolean isEmpty() {
        
            return top ==-1;
        }
    
        // 判断栈是否已满
        public boolean isFull() {
        
            return top == maxSize-1;
        }
    }

使用栈倒序输出字符串：

public static void main(String[] args) {
        
            MyStack myStack = new MyStack(15);
            String str = "how are you";
            for (char c : str.toCharArray()) {
        
                myStack.push(c);
            }
    
            while (!myStack.isEmpty()){
        
                System.out.print(myStack.pop());
            }
        }

结果：  
![在这里插入图片描述][20200318173233432.png]  
这个栈是用数组实现的，内部定义了一个数组，一个表示最大容量的值以及一个指向栈顶元素的  
top变量。构造方法根据参数规定的容量创建一个新栈，push()方法是向栈中压入元素，指向栈顶的变量  
top加一，使它指向原顶端数据项上面的一个位置，并在这个位置上存储一个数据。pop()方法返回top变  
量指向的元素，然后将top变量减一，便移除了数据项。要知道 top 变量指向的始终是栈顶的元素。  
产生的问题：  
①、上面栈的实现初始化容量之后，后面是不能进行扩容的（虽然栈不是用来存储大量数据的），  
如果说后期数据量超过初始容量之后怎么办？（自动扩容）  
②、我们是用数组实现栈，在定义数组类型的时候，也就规定了存储在栈中的数据类型，那么同一  
个栈能不能存储不同类型的数据呢？（声明为Object）  
③、栈需要初始化容量，而且数组实现的栈元素都是连续存储的，那么能不能不初始化容量呢？  
（改为由链表实现）

### 3、增强功能版栈 ###

对于上面出现的问题，第一个能自动扩容，第二个能存储各种不同类型的数据，解决办法如下：  
（第三个在讲链表的时候在介绍）  
这个模拟的栈在JDK源码中，大家可以参考 Stack 类的实现  
![在这里插入图片描述][20200318173505410.png]

package person.shw.structure;
    import	java.util.EmptyStackException;
    import	java.util.Arrays;
    
    /**
     * @author Administrator
     * @create 2020/3/18
     * @since 1.0.0
     */
    public class MyStackPlus {
        
    
        private int initialCapacity;
        private Object[] elelementData;
        private int top;
    
        // 默认初始化容量
        public MyStackPlus() {
        
            elelementData = new Object[10];
            top = -1;
        }
    
        // 自定义初始化容量
        public MyStackPlus(int initialCapacity) {
        
    
            if (initialCapacity<0){
        
                throw new IllegalArgumentException("初始化容量不小于0=>"+initialCapacity);
            }
            this.initialCapacity = initialCapacity;
            top = -1;
            elelementData = new Object[initialCapacity];
        }
    
        // 元素入栈
        public Object push(Object value){
        
    
                isGrow(top+1);
                elelementData[++top] = value;
                return value;
        }
    
        // 元素出栈
        public Object pop() {
        
            
            if (top ==-1){
        
                throw new EmptyStackException();
            }
            Object obj = elelementData[top--];
            elelementData[top] = null;
            return obj;
        }
    
        // 访问栈顶元素
        public Object peek() {
        
            if (top ==-1){
        
                throw new EmptyStackException();
            }
            return elelementData[top];
        }
    
        // 判断栈是否为空
        public boolean isEmpty() {
        
            return top ==-1;
        }
    
        // 判断栈是否已满
        public boolean isFull() {
        
            return top == initialCapacity-1;
        }
    
        // 是否需要扩容，如果需要，则扩大一倍并返回true，不需要则返回false
        public boolean isGrow(int minCapacity){
        
            int oldCapacity = this.initialCapacity;
            // 如果当前元素压入栈之后总容量大于前面定义的容量，则需要扩容
            if (oldCapacity<minCapacity){
        
                 int newCapacity = 0;
                 // 判断栈容量扩大两倍是否大于int的范围
                if (oldCapacity<<1-Integer.MAX_VALUE>0){
        
                    newCapacity = Integer.MAX_VALUE;
                }else {
        
                    newCapacity = oldCapacity<<1;
                }
                this.initialCapacity = newCapacity;
                elelementData = Arrays.copyOf(elelementData,initialCapacity);
                return true;
            }else {
        
                return false;
            }
    
        }
    }

### 4、利用栈判断分隔符是否匹配 ###

写过xml标签或者html标签的，我们都知道<必须和最近的>进行匹配，\[ 也必须和最近的 \] 进行匹  
配。  
比如：<abc\[123\]abc>这是符号相匹配的，如果是 <abc\[123>abc\] 那就是不匹配的。  
对于 12<a\[b\{c\}\]>，我们分析在栈中的数据：遇到匹配正确的就消除  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]

//分隔符匹配
    //遇到左边分隔符了就push进栈，遇到右边分隔符了就pop出栈，看出栈的分隔符是否和这个有分隔符匹配
    @Test
    public void testMatch(){
        
      MyStackPlus stack = new MyStackPlus(3);
      String str = "12<a[b{c}]>";
      char[] cha = str.toCharArray();
      for(char c : cha){
        
        switch (c) {
        
        case '{':
        case '[':
        case '<':
          stack.push(c);
          break;
        case '}':
        case ']':
        case '>':
          if(!stack.isEmpty()){
        
            char ch = stack.pop().toString().toCharArray()[0];
            if(c=='}' && ch != '{'
              || c==']' && ch != '['
              || c==')' && ch != '('){
        
              System.out.println("Error:"+ch+"-"+c);
           }
         }
          break;
        default:
          break;
       }
     }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]: /images/20230528/8deddc39340a45f198edf650932472dc.png
[20200318173233432.png]: /images/20230528/349a6717ce0944b88ab1b739e5b4e605.png
[20200318173505410.png]: /images/20230528/c0a665d5c52944fcb317998f961daf73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]: /images/20230528/28c23261fb594cf6a2440caaa1a94d95.png