算法通关村第四关——如何基于数组（链表）实现栈

清疚 2024-03-23 00:16 8阅读 0赞

## 栈的基础知识 ##

### 栈的特征 ###

#### 特征1 ####

> 栈和队列是比较特殊的线性表，又被称为 访问受限的线性表。栈是很多表达式、符号等运算的基础，也是递归的底层实现（递归就是方法自己调用自己，在JVM的虚拟机栈中，一个线程中的栈帧就是一个要调用的方法，栈帧的实现就是栈结构，其会将正在执行的方法（栈帧）设在栈顶）。理论上递归能够做的题目，栈都可以做，只是有些问题用栈会比较复杂。

#### 特征2 ####

> 栈的底层实现依然是链表或者顺序表。栈与线性表的最大区别就是：数据的存取操作被限制了，其插入和删除操作只允许在线性表的一端进行。
> 
> 一般而言，把2允许操作的一端称为栈顶（top），不可操作的一端称为栈底（bottom）
> 
> 把插入元素的操作称为入栈（Push），把删除元素的操作称为出栈（pop）；若栈中没有任何元素则称为空栈。其结构如下：

![image.png][]

### 栈的操作 ###

栈的常用操作主要有：

>  *  push（E）：增加一个元素E
>  *  pop（）：弹出一个元素E
>  *  peek（）：只显示栈顶元素，不弹出元素
>  *  empty（）：判断栈是否为空

> 在自定义栈时，不管用数组还是链表，都要实现上面的几个方法。
> 
> 检测对栈的理解：
> 
> 入栈顺序为1234，所有可能的出栈序列是什么？

> 4个元素的全排列共有24种，栈要求符合后进先出，按此衡量排除后即得：
> 
> 1234√ 1243√ 1324√ 1342√
> 
> 1432√ 2134√ 2143√ 4321√
> 
> 2314√ 2341√ 2431√3421√
> 
> 3214√ 3241√ 3124x 3142x
> 
> 3412x 4123x 4132x 2413x
> 
> 4213x 4231x 4312x 1423x
> 
> 14种可能，10种不可能，如上所示。

### Java中的栈 ###

> java的util中提供了栈Stack类，使用不复杂，看下面例子

public class MainTest {
    public static void main(string[] args) {
        Stack<Integer> stack = new stack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("栈顶元素为:" + stack.peek());
        while (!stack.empty()){
        //只显示没出栈
        System.out.printIn(stack.peek());//出栈并且显示
        System.out.println(stack.pop());
        }
      }
    }

## 自定义栈 ##

> 如果要自己实现栈，可以有数组、链表和java提供的LinkedList三种基本方式我们都看一下。  
> 采用顺序表实现的的栈，内部以数组为基础，实现对元素的存取操作。在应用中还要注意每次入栈之前先判断栈的容量是否够用，如果不够用，可以进行扩容。
> 
> 入栈过程如下图所示：

![image.png][image.png 1]

> 出栈过程如下图所示：

![image.png][image.png 2]

### 基于数组实现栈 ###

> top先将栈顶元素取出，然后再执行top--。完整的实现代码如下

package org.example.stack;
    
    import java.util.Arrays;
    
    public class MyStackByArray<T>{
        // 实现栈的数组
        private Object[]  stack;
        // 栈顶元素
        private int top;
        //初始化栈容量
    
        public MyStackByArray(int top) {
            stack = new Object[top];
        }
    
        //判断栈是否为空
        public boolean isEmpty(){
            return top == 0;
        }
        //返回栈顶元素
        public T peek(){
            T t = null;
            if (top > 0){
                t = (T) stack[top -1];
            }
            return t;
        }
    
        // 入栈
        public void push(T t){
            extendCapacity(top + 1);
            stack[top] = t;
            top++;
        }
    
        // 出栈
        public T pop(){
            T t = peek();
            if (top > 0){
                stack[top-1] = null;
                top--;
            }
            return t;
        }
    
        //扩大容量
        private void extendCapacity(int size) {
            int len = stack.length;
            if (len < size){
                size = size * 3/2 + 1;
                stack = Arrays.copyOf(stack, size);
            }
        }
    
    
    }

### 基于链表实现栈 ###

> 链表实现栈，只需要把删除和修改的操作都限制在头节点即可，如下图：

![image.png][image.png 3]

> 实现代码如下：

package org.example.stack;
    
    public class MyStackByLinkedList <T>{
        // 构造节点
        class Node<T>{
                public   T t;
                public Node next;
        }
        // 头指针
        public Node<T> head;
        // 初始化
        MyStackByLinkedList(){
            head = null;
        }
    
        // 入栈
        public void push(T t){
            if (t==null){
                throw new NullPointerException("形参不能为空");
            }
            // 如果是空链表，就将入栈的元素设为第一个元素
            if (head == null){
                head = new Node<>();
                head.t = t;
                head.next = null;
            }else {
                Node<T> temp = head;
                head = new Node<>();
                head.t = t;
                head.next = temp;
            }
        }
        // 出栈
        public T pop(){
            T t = null;
            if (head == null){
                return null;
            }else {
                t = head.t;
                head = head.next;
            }
            return t;
        }
    
        // 取栈顶元素
        public T peek(){
            if (head == null){
                return null;
            }
            return head.t;
        }
    
        //栈空
        public boolean isEmpty(){
            return head == null;
        }
    }

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/867aae0eb6ab495fafda50bc055940ac.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/efc6ce45db9c49d5b536efad941e0b66.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cf8c09c6285c4e4dbf3d532867942a1e.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d82997ebcfd34d63814c2722cdcc65f9.png