数据结构之栈基本实现

绝地灬酷狼 2022-12-28 01:37 213阅读 0赞

### 文章目录 ###

*   *  栈
     *  栈的实现
     *   *  定义结点类
         *  属性及构造方法
         *  getSize()方法
         *  isEmpty()方法
         *  traverse()方法
         *  push(Object data)方法
         *  pop()方法
         *  peek()方法
         *  clear()方法
     *  全部代码
     *  Java中的栈

--------------------

## 栈 ##

栈是一种特殊的线性表，栈中的数据元素以及数据元素间的逻辑关系和线性表相同，两者之间的差别在于：线性表的插入和删除操作可以在表的任意位置进行，而栈的插入和删除操作只允许在表的尾部进行，因此效率都是很高的，插入和删除都是在栈顶进行的，最后插入的最先被删除，所以栈的工作模式是先进后出（LIFO, Last In First Out）。如下为栈的基本结构图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70]  
栈底a1为第一次插入的元素，进栈和出栈都是在栈顶进行操作。

## 栈的实现 ##

栈可以通过数组和和链表来实现，上一章写了[链表的基本实现][Link 1]，那这里就用链表来实现栈了。

### 定义结点类 ###

通过链表来实现栈，看到链表肯定少不了结点，下面定义一个内部类，用于结点类。代码如下

public class Node{
        public Object data; //栈数据
        public Node next;   //栈指针，指向下一个结点
    
        public Node() {
        }
    
        public Node(Object data) {
            this.data = data;
        }
    
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

和链表的结点一样，包含结点数据、指针和构造方法。

### 属性及构造方法 ###

实现栈的方法之前，还需要定义基本的栈属性和构造方法，因为进栈出栈都是在栈顶进行操作，所以需要定义一个栈顶便于操作、在定义一个size属性用于统计栈中元素的数量和一个构造方法。代码如下

//栈顶
        public Node stackTop;
        //栈数量
        public Integer size = 0;
    
        //构造方法
        public ListStack() {
        }

### getSize()方法 ###

getSize()方法返回栈中元素数量，在属性中定义了一个结点数量的属性size，所以这里直接返回size属性即可。

public Integer getSize(){
       	return size;
    }

### isEmpty()方法 ###

isEmpty()方法判断栈是否为空，如果size结点的数量等于0即栈为空。

public Boolean isEmpty(){
        return size == 0;
    }

### traverse()方法 ###

traverse()方法遍历栈中的所有元素。因为这里栈使用的链表来实现的，所以遍历栈和遍历链表一样(栈顶相当于链表的头结点)，直接利用while循环依次遍历，直到栈结点为空结束。

**代码实现**

//遍历栈
    public void traverse(){
        //创建临时结点，赋值为栈顶结点，从栈顶开始遍历
        Node temp = stackTop;
        //遍历栈
        while(temp != null){
            System.out.println("编程小马：" + temp.data);
            //指向下一个栈结点
            temp = temp.next;
        }
    }

### push(Object data)方法 ###

push(Object data)方法进栈操作，即添加栈元素。把新的栈结点指向原栈顶，栈顶更换为新结点。

**代码实现**

/**
     * 进栈，添加栈结点
     * @param data 进栈的数据
     * @return Boolean
     */
    public Boolean push(Object data){
        try{
            //实例一个栈结点
            Node newNode = new Node(data);
            //新栈结点指向栈顶
            newNode.next = stackTop;
            //新结点替换为栈顶
            stackTop = newNode;
            //栈数量自增
            size++;
            return true;
        }catch (Exception e){
            return false;
        }
    }

**push()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 1]

### pop()方法 ###

pop()方法出栈操作，即删除栈顶结点，返回删除的结点。出栈操作之前需要对栈进行一下判断操作，判断栈是否为空；如果栈不为空，则直接获取栈顶结点，把栈顶结点改为栈顶结点指向的结点，返回原栈顶结点即可。

**代码实现**

/**
     * 出栈，删除栈顶部结点
     * @return 删除的结点
     */
    public Node pop(){
        try{
            //判断栈是否为空
            if(!isEmpty()){
                //获取栈顶结点
                Node top = stackTop;
                //改变栈顶元素
                stackTop = top.next;
                return top;
            }
            //栈结点自减
            size--;
            return null;
        }catch (Exception e){
            return null;
        }
    }

**pop()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 2]

### peek()方法 ###

peek()方法取出栈顶结点对象。先判断一下栈是否为空，如果不为空，直接返回定义的栈顶属性即可。

**代码实现**

//取出栈顶结点对象
    public Node peek(){
        try{
            //判断栈是否为空
            if(!isEmpty()){
                return stackTop;
            }
            return null;
        }catch (Exception e){
            return null;
        }
    }

**peek()方法测试**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 3]

### clear()方法 ###

clear()方法清空栈，直接把栈顶属性置为空即可，栈顶为空，栈也就为空了。

**代码实现**

//清空栈
    public Boolean clear(){
        try{
            stackTop = null;
            return true;
        }catch (Exception e){
            return false;
        }
    }

## 全部代码 ##

> 上述基于链表实现了栈的一些常用方法，下面是上述案例中的所有代码。有错误地方欢迎指出。

public class ListStack {
        //定义一个内部类，作为栈的结点
        public class Node{
            public Object data; //栈数据
            public Node next;   //栈指针，指向下一个结点
    
            public Node() {
            }
    
            public Node(Object data) {
                this.data = data;
            }
    
            public Node(Object data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
    
        //栈顶
        public Node stackTop;
        //栈数量
        public Integer size = 0;
    
        //构造方法
        public ListStack() {
        }
    
        //返回栈结点的数量
        public Integer getSize(){
            return size;
        }
    
        //判断栈是否为空
        public Boolean isEmpty(){
            return size == 0;
        }
    
        /**
         * 进栈，添加栈结点
         * @param data 进栈的数据
         * @return Boolean
         */
        public Boolean push(Object data){
            try{
                //实例一个栈结点
                Node newNode = new Node(data);
                //新栈结点指向栈顶
                newNode.next = stackTop;
                //新结点替换为栈顶
                stackTop = newNode;
                //栈数量自增
                size++;
                return true;
            }catch (Exception e){
                return false;
            }
        }
    
        //遍历栈
        public void traverse(){
            //创建临时结点，赋值为栈顶结点，从栈顶开始遍历
            Node temp = stackTop;
            //遍历栈
            while(temp != null){
                System.out.println("编程小马：" + temp.data);
                //指向下一个栈结点
                temp = temp.next;
            }
        }
    
        /**
         * 出栈，删除栈顶部结点
         * @return 删除的结点
         */
        public Node pop(){
            try{
                //判断栈是否为空
                if(!isEmpty()){
                    //获取栈顶结点
                    Node top = stackTop;
                    //改变栈顶元素
                    stackTop = top.next;
                    return top;
                }
                //栈结点自减
                size--;
                return null;
            }catch (Exception e){
                return null;
            }
        }
    
        //取出栈顶结点对象
        public Node peek(){
            try{
                //判断栈是否为空
                if(!isEmpty()){
                    return stackTop;
                }
                return null;
            }catch (Exception e){
                return null;
            }
        }
    
        //清空栈
        public Boolean clear(){
            try{
                stackTop = null;
                return true;
            }catch (Exception e){
                return false;
            }
        }
    
        public static void main(String[] args) {
            //实例一个栈
            ListStack stack = new ListStack();
            //添加栈元素
            stack.push(1);
            stack.push(2);
            stack.push(3);
            //遍历
            stack.traverse();
    
            //取出栈顶元素
            System.out.println("当前栈顶元素为：" + stack.peek().data);
    
            //删除栈顶结点
            System.out.println();
            Node node = stack.pop();
            System.out.println("删除的栈顶结点元素值为：" + node.data);
    
            System.out.println();
            System.out.println("删除后栈中的全部元素");
            stack.traverse();
        }
    }

## Java中的栈 ##

其实Java中也包含的有栈，Java中的Stack栈是继承与Vector类的，是基于动态数组来实现的。包含的方法如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 4]  
**Stack栈的继承关系**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 5]

> 如果平时需要使用栈的操作，可以直接调用Java的Stack类使用。Java中栈是基于数组实现的，想了解基于数组实现栈的小伙伴可以去读一读Stack类的源码。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70]: /images/20221120/01c4739f2c074657a447707525d7ef01.png
[Link 1]: https://blog.csdn.net/qq_40205116/article/details/111036162
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 1]: /images/20221120/2f126bee6c2c4908ab2ac5a08dc8d6c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201214003904995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201214004238911.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020121400523886.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201214005633928.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjA1MTE2,size_16,color_FFFFFF,t_70