疯狂数据结构-栈-Java

àì夳堔傛蜴生んèń 2023-10-13 19:13 25阅读 0赞

## 概念 ##

### 基本概念解读 ###

当谈到 "栈" 时，它是一种遵循后进先出（Last In, First Out，LIFO）原则
    的有序集合。这意味着最后入栈的元素首先被弹出，而最早入栈的元素最后被弹
    出。
    在栈中，只能对最上面的元素进行操作，其他元素都不可见，需要将上面的元素
    先出栈才能访问到其他元素。

![在这里插入图片描述][cee360d2a2414e09a29cb721a782f16b.png]

### 基本操作分析 ###

栈的基本操作包括入栈（push）和出栈（pop）。入栈指的是向栈中添加一个元
    素，使其成为新的栈顶；而出栈指的是移除栈顶的元素，使得下一个元素成为新
    的栈顶。此外，还可以通过栈顶元素的读取（top）来查看当前栈顶的值，以及
    判断栈是否为空（empty）。

### 基本操作总结 ###

入栈（Push）：将一个元素放入栈的顶部。
    出栈（Pop）：从栈的顶部移除一个元素，并将其返回。
    获取栈顶元素（Top）：返回栈的顶部元素，但不对栈进行修改。
    判空（isEmpty）：检查栈是否为空。
    获取栈的大小（getSize）：返回栈中元素的个数。

![在这里插入图片描述][30ad17df8c62443ea32e3627cd87d78d.png]

## 应用分析 ##

### 实际应用分析 ###

栈的应用相当广泛，例如函数的调用栈、浏览器的前进后退功能和计算器的后缀
    表达式求值等等。在算法设计中，栈也常用于解决问题，如深度优先搜索和括号
    匹配等。

![在这里插入图片描述][67c796f8966b46e9b4872b0925df2674.png]

### 实际应用场景 ###

表达式求值：栈可用于将中缀表达式转换为后缀表达式，并对其进行求值。运算
    符和操作数依次入栈，直到遇到更高优先级的运算符。这时，先前的运算符必须
    先出栈。
    递归算法：递归算法通常使用栈来实现，因为递归函数的调用过程本质上也是一
    个栈结构，每次递归调用都会将当前函数的局部变量和返回地址保存在栈上。
    
    浏览器历史记录：浏览器使用栈来跟踪用户访问不同网页的历史记录。每当用户
    访问一个新页面时，该页面被推入栈中。通过后退操作，最近访问的页面会从栈
    中弹出。
    
    函数调用：函数调用通常使用栈来管理函数的调用顺序和返回地址。每当一个函
    数被调用时，其相关信息（参数、局部变量等）会被压入栈，函数执行完成后将
    被弹出。
    
    撤销操作：编辑器、文本处理软件等应用中，栈可以用于实现撤销操作。每次对
    文本进行修改时，相关的操作记录会被压入栈中，在用户需要撤销操作时，可以
    从栈中弹出最近的修改记录，实现撤销功能。
    
    浏览器的浏览历史：浏览器通过使用栈来记录用户的浏览历史。每当用户访问一
    个新的网页时，该网页的 URL 被推入栈中，当用户点击“后退”按钮时，最近访
    问的网页 URL 被弹出栈。
    
    括号匹配：栈可以用于检查表达式中的括号是否匹配。遍历表达式，将左括号压
    入栈中，当遇到右括号时，检查栈顶的左括号是否与之匹配，若匹配则继续。

需要注意的是，在使用栈时要避免两个常见的问题：栈上溢（stack overflow）和栈下溢（stack underflow）。栈上溢发生在尝试向已满的栈中插入元素时，而栈下溢发生在尝试从空栈中弹出元素时。  
![在这里插入图片描述][ce59b6e30276476ba4cf381db17d8606.png]

## 注意事项 ##

### 基本注意事项 ###

栈的初始化：在使用栈之前，需要对栈进行初始化，即为栈分配一定大小的内存
    空间，并将栈的指针指向栈底。如果栈的大小事先不确定，可以动态调整栈的大
    小。
    
    入栈操作：在进行入栈操作时，需要注意判断栈是否已满。如果栈已满，则需要
    进行相应的处理，如扩充栈的空间或者报错。入栈时要确保栈的指针指向栈顶，
    并将要入栈的数据放入栈顶位置，同时栈顶指针要更新。
    
    出栈操作：在进行出栈操作时，需要判断栈是否为空。如果栈为空，则需要进行
    相应的处理，如报错或者返回特定的值。出栈时要确保栈的指针指向栈顶元素，
    取出栈顶元素后，栈顶指针要更新。
    
    栈的访问：栈是一种后进先出的数据结构，因此只能访问栈顶元素，无法直接访
    问栈中的其他元素。如果需要访问栈中的其他元素，需要先将栈顶元素出栈，然
    后再入栈其他元素，或者使用辅助栈进行操作。
    
    栈的容量控制：由于栈的大小是有限的，对于大量数据的处理，需要合理控制栈
    的容量，避免过多的数据存储在栈中，以免造成栈溢出或者浪费内存的问题。可
    以根据具体需求，设定一个合适的栈的容量上限，并在入栈操作时判断栈是否超
    过容量上限。
    
    异常处理：在使用栈的过程中，可能会出现一些异常情况，如栈溢出、空栈出栈
    等。需要进行异常处理，如使用try-catch语句来捕获异常并进行相应的处理。
    避免程序崩溃或者逻辑错误。
    
    内存管理：在使用栈的过程中，需要合理地管理栈的内存。当不再需要使用栈时，
    需要及时释放栈所占用的内存空间，以避免内存泄漏问题。
    
    栈的大小限制：栈的大小是有限的，具体取决于操作系统和计算机硬件的限制。
    在使用栈的过程中，需要确保栈不会溢出。当递归层数过深或者栈中的数据量
    过大时，可能会导致栈溢出的问题。
    
    入栈和出栈的顺序：栈是一种遵循"先入后出"原则的数据结构，因此在进行入栈
    和出栈操作时，需要确保顺序正确，否则可能会导致程序逻辑错误。
    
    栈的线程安全性：多线程环境下，如果多个线程同时使用同一个栈，可能会导致
    线程安全的问题。需要通过合适的同步机制来保证栈的操作的线程安全性，例如
    使用互斥锁或者信号量等。

![在这里插入图片描述][a14ea32a83f2497c8b48d0a0d03d72eb.png]

## 理论总结 ##

总结来说，栈是一种简单而重要的数据结构，具有广泛的应用场景。掌握栈的基
    本操作和实现方式对于理解和应用许多问题都非常有帮助。

## 代码实现 ##

### 思路分析 ###

栈的实现可以使用数组或链表等数据结构。在数组中，栈的底部通常对应数组的
    起始位置，栈的顶部对应最后一个元素；而在链表中，栈的顶部对应链表的首个
    元素。

### 常规操作 ###

import java.util.EmptyStackException;
    
    public class Stack {
        
        private int[] stackArray;
        private int top;
        private int minElement; // 记录栈的最小值
        
        // 构造函数，初始化栈
        public Stack(int capacity) {
        
            stackArray = new int[capacity];
            top = -1; // 栈顶指针初始化为-1，表示栈为空
            minElement = Integer.MAX_VALUE; // 最小值初始化为正无穷大
        }
        
        // 判断栈是否为空
        public boolean isEmpty() {
        
            return top == -1;
        }
        
        // 判断栈是否已满
        public boolean isFull() {
        
            return top == stackArray.length - 1;
        }
        
        // 入栈操作
        public void push(int data) {
        
            if (isFull()) {
        
                throw new StackOverflowError("Stack is full");
            }
            if (data < minElement) {
        
                // 更新最小值
                minElement = data;
            }
            stackArray[++top] = data;
        }
        
        // 出栈操作
        public int pop() {
        
            if (isEmpty()) {
        
                throw new EmptyStackException();
            }
            int data = stackArray[top];
            if (data == minElement) {
        
                // 如果出栈的元素是最小值，更新最小值
                updateMinElement();
            }
            top--;
            return data;
        }
        
        // 获取栈顶元素
        public int top() {
        
            if (isEmpty()) {
        
                throw new EmptyStackException();
            }
            return stackArray[top];
        }
        
        // 获取栈的大小
        public int size() {
        
            return top + 1;
        }
        
        // 清空栈
        public void clear() {
        
            top = -1;
            minElement = Integer.MAX_VALUE;
        }
        
        // 获取栈的最小值
        public int getMin() {
        
            if (isEmpty()) {
        
                throw new EmptyStackException();
            }
            return minElement;
        }
        
        // 判断栈是否存在某个元素
        public boolean contains(int data) {
        
            for (int i = 0; i <= top; i++) {
        
                if (stackArray[i] == data) {
        
                    return true;
                }
            }
            return false;
        }
        
        // 更新最小值
        private void updateMinElement() {
        
            minElement = Integer.MAX_VALUE;
            for (int i = 0; i <= top; i++) {
        
                if (stackArray[i] < minElement) {
        
                    minElement = stackArray[i];
                }
            }
        }
    }

上面代码中
    	获取栈的最小值的操作 getMin() 和判断栈是否存在某个元素的操作 
    	contains()。在 push() 方法中，新增了对栈的最小值的更新操作，
    	以便在出栈时更新最小值。在 pop() 方法中，将出栈的元素与最小值
    	进行比较，如果相等，则更新最小值。 updateMinElement() 方法用
    	于更新最小值，它会遍历栈中的元素以找到最小值。

![在这里插入图片描述][e4f1498d0b3043b3bfa05479688f61be.png]

### 实际应用 ###

public class ArrayStack {
        
        private Object[] arra
       y;
        private int top;
        private int capacity;
    
        public ArrayStack(int capacity) {
        
            this.capacity = capacity;
            this.array = new Object[capacity];
            this.top = -1;
        }
    
        public void push(Object element) {
        
            if (top == capacity - 1) {
        
                throw new StackOverflowError("Stack is full");
            }
            top++;
            array[top] = element;
        }
    
        public Object pop() {
        
            if (isEmpty()) {
        
                throw new EmptyStackException();
            }
            Object element = array[top];
            array[top] = null;
            top--;
            return element;
        }
    
        public Object top() {
        
            if (isEmpty()) {
        
                throw new EmptyStackException();
            }
            return array[top];
        }
    
        public boolean isEmpty() {
        
            return top == -1;
        }
    
        public int getSize() {
        
            return top + 1;
        }
    }

调用上面代码

public static void main(String[] args) {
        
        ArrayStack stack = new ArrayStack(3);
        stack.push("A");
        stack.push("B");
        stack.push("C");
    
        System.out.println("Size: " + stack.getSize()); // 输出：Size: 3
    
        System.out.println(stack.pop()); // 输出：C
        System.out.println(stack.top()); // 输出：B
    
        System.out.println(stack.isEmpty()); // 输出：false
    
        stack.push("D");
        System.out.println(stack.pop()); // 输出：D
        System.out.println(stack.pop()); // 输出：B
        System.out.println(stack.pop()); // 输出：A
    
        System.out.println(stack.isEmpty()); // 输出：true
    }

这个代码演示了使用数组实现的栈的基本操作。你可以根据需要进行进一步扩展和优化，例如，使用链表实现栈，或实现其他更高级的功能。

[cee360d2a2414e09a29cb721a782f16b.png]: https://img-blog.csdnimg.cn/cee360d2a2414e09a29cb721a782f16b.png
[30ad17df8c62443ea32e3627cd87d78d.png]: https://img-blog.csdnimg.cn/30ad17df8c62443ea32e3627cd87d78d.png
[67c796f8966b46e9b4872b0925df2674.png]: https://img-blog.csdnimg.cn/67c796f8966b46e9b4872b0925df2674.png
[ce59b6e30276476ba4cf381db17d8606.png]: https://img-blog.csdnimg.cn/ce59b6e30276476ba4cf381db17d8606.png
[a14ea32a83f2497c8b48d0a0d03d72eb.png]: https://img-blog.csdnimg.cn/a14ea32a83f2497c8b48d0a0d03d72eb.png
[e4f1498d0b3043b3bfa05479688f61be.png]: https://img-blog.csdnimg.cn/e4f1498d0b3043b3bfa05479688f61be.png