数据结构与算法：栈

叁歲伎倆 2022-09-08 14:50 185阅读 0赞

### 文章目录 ###

*  栈
 *   *  概述
     *  栈的基本操作
     *  顺序栈
     *  链栈
     *  源代码链接
     *  参考文献

# 栈 #

## 概述 ##

栈是限定在表尾进行插入与删除操作的线性表。允许插入与删除的一端称为栈顶（top）,另一端称为栈底（bottom）,不含任何数据的栈称为空栈。

栈的修改是按照后进先出的原则进行的，所以栈又被称为后进先出（LIFO，last in first out）的线性表。

## 栈的基本操作 ##

*  初始化：构造一个空栈
 *  入栈：在栈顶位置插入一个新元素
 *  出栈：删除栈顶位置元素
 *  获取：获取栈顶元素，但并未删除栈顶元素
 *  判空：判断当前栈是否为空
 *  求长度：获取栈中元素个数
 *  销毁：销毁一个已存在的栈

## 顺序栈 ##

顺序栈是利用一组地址连续的存储单元依次存放自栈底到时栈顶的数据元素。

顺序栈程序示例如下：

import java.util.Arrays;
    
    /** * * @param <T> */
    public class SequenceStack<T> { 
    
        final int MAX_SIZE = 5;
    
        private T[] stackArray;
    
        // 指针
        private int top;
    
        public SequenceStack(){ 
            // top的初始值为-1，指向栈底，而这个top==-1也可作为栈空的标志，
            // 每当插入一个新的栈顶元素时，先把指针top增加1，再把入栈的元素放到top指针指向的位置
            this.top = -1;
            this.stackArray = (T[]) new Object[MAX_SIZE];
        }
    
        public SequenceStack(int maxSize){ 
    
            if (maxSize <= 0) { 
                System.out.println("数组长度要大于0,否则退出程序运行");
                System.exit(1);
            }
    
            this.top = -1;
            this.stackArray = (T[]) new Object[maxSize];
        }
    
        /** * 在栈顶位置插入一个新元素 * @param obj */
        public void push(T obj){ 
    
            // 栈满
            if (this.top == this.stackArray.length - 1) { 
                T[] p = (T[]) new Object[this.top * 2 + 2];
                for (int i = 0; i <= top; i++) { 
                    p[i] = this.stackArray[i];
                }
                this.stackArray = p;
            }
    
            this.top++;
            this.stackArray[top] = obj;
        }
    
        /** * 删除栈顶元素 * @return */
        public T pop(){ 
            if (this.top == -1) { 
                System.out.println("当前数据栈已空，无法删除元素");
                return null;
            }
            this.top--;
            return this.stackArray[this.top + 1];
        }
    
        /** * 获取栈顶数据元素 * @return */
        public T getHead(){ 
            if (this.top == -1) { 
                System.out.println("当前数据栈已空，无法删除元素");
                return null;
            }
            this.top--;
            return this.stackArray[this.top + 1];
        }
    
        /** * 判断当前栈是否为空 * @return */
        public boolean isEmpty(){ 
            return this.top == -1;
        }
    
        /** * 获取栈中元素个数 * @return */
        public int size(){ 
            return this.top + 1;
        }
    
        /** * 依次访问栈中元素并输出 */
        public void nextOrder(){ 
    // Arrays.stream(this.stackArray).forEach(t -> System.out.println(t));
            for (int i = this.top; i >= 0; i--) { 
                System.out.println(this.stackArray[i]);
            }
        }
    
        /** * 销毁一个已存在的栈 */
        public void clear(){ 
            this.top = -1;
        }
    
        public static void main(String[] args) { 
            SequenceStack<String> sequenceStack = new SequenceStack<>();
            boolean empty = sequenceStack.isEmpty();
            System.out.println(empty);
        }
    
    }

## 链栈 ##

栈的链接存储结构称为链栈。利用链表实现，链表中的每个数据元素由两部分信息组成，一部分是存储其本身的信息，一部分是存储一个指示其直接后继的信息，即直接后继的存储位置。我们称它有两个域，其中存储数据元素信息的域为数据域，存储直接后继存储位置的域为指针域。

链栈的程序示例，如下：

/** * 链栈 */
    public class LinkedStack<T> { 
    
        // 栈顶指针
        private Node<T> top;
        // 存储栈的长度
        private int length;
    
        public LinkedStack(){ 
            this.length = 0;
            this.top = null;
        }
    
        /** * 入栈 * @param obj */
        public void push(T obj){ 
            this.top = new Node<>(obj, this.top);
            length ++;
        }
    
        /** * 出栈, 返回当前栈顶元素 * @return */
        public T pop(){ 
            if (this.top == null) { 
                System.out.println("当前栈为空");
            }
    
            T temp = this.top.data;
            this.top = top.next;
    
            length --;
            return temp;
    
        }
    
        /** * 获取当前栈顶元素，元素未出栈 * @return */
        public T peek() { 
            return this.top == null ? null : this.top.data;
        }
    
        /** * 获取栈数据元素个数 * @return */
        public int size(){ 
            return length;
        }
    
        /** * 判断当前栈是否为空栈 * @return */
        public boolean isEmpty(){ 
            return this.top == null;
        }
    
        /** * 循环遍历当前栈中元素 */
        public void nextOrder(){ 
            Node<T> p = top;
            while (p != null) { 
                System.out.println(p.data);
                p = p.next;
            }
        }
    
        private class Node<T> { 
    
            /** * 数据域 */
            private T data;
    
            /** * 地址域 */
            private Node<T> next;
    
            public Node(){ 
    
            }
    
            public Node(T data, Node<T> next) { 
                this.data = data;
                this.next = next;
            }
    
        }
    
    }

## 源代码链接 ##

[https://github.com/myNameIssls/java-exampls/tree/master/data-structure-examples/src/main/java/cn/tyrone/java/datastructure/queue][https_github.com_myNameIssls_java-exampls_tree_master_data-structure-examples_src_main_java_cn_tyrone_java_datastructure_queue]

## 参考文献 ##

《数据结构（Java语言描述）》 作者：罗福强，杨剑，刘英

[https_github.com_myNameIssls_java-exampls_tree_master_data-structure-examples_src_main_java_cn_tyrone_java_datastructure_queue]: https://github.com/myNameIssls/java-exampls/tree/master/data-structure-examples/src/main/java/cn/tyrone/java/datastructure/queue