数据结构与算法—栈

素颜马尾好姑娘i 2022-12-02 10:51 147阅读 0赞

## 栈的介绍 ##

1.  **栈**不同于**队列**，栈是一个先进后出(FILO)的有序列表。
2.  **栈**是一种特殊的线性表。它限制了线性表中元素的插入和删除只能在线性表的同一端进行。允许插入和删除的一端，称为 **栈顶**，另一端为固定的一端，称为**栈底**。
3.  最先放入栈中的元素在栈底，最后放入的元素在栈顶。删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

## 应用场景 ##

1.  子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2.  处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3.  表达式的转换\[ 中缀表达式转后缀表达式 \]与求值。
4.  二叉树的遍历。
5.  图形的深度优先(depth 一 first)搜索法。

## 使用数组模拟栈(代码实现) ##

思路分析：

1.  定义一个top来表示栈顶，初始化为 -1；
2.  入栈：当有数据加入到栈中，top++; stack\[top\] = data;
3.  出栈：int value = stack\[top\]; top–; return value;

public class ArrayStack { 
    
        /** * 栈的大小 */
        private int maxSize;
    
        /** * 数组，数组模拟栈 */
        private int[] stack;
    
        /** * 栈顶，初始化为 -1 */
        private int top = -1;
    
        public ArrayStack(int maxSize) { 
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
        }
    
        /** * TODO 判断栈 满 */
        public boolean isFull() { 
            return top == maxSize - 1;
        }
    
        /** * TODO 判断栈 空 */
        public boolean isEmpty() { 
            return top == -1;
        }
    
        /** * TODO 入栈 */
        public void push(int val) { 
            if (isFull()) { 
                System.err.println("入栈失败，栈已满");
                return;
            }
            top++;
            stack[top] = val;
        }
    
        /** * TODO 出栈 */
        public int pop() { 
            if (isEmpty()) { 
                throw new RuntimeException("出栈失败，栈为空");
            }
            int val = stack[top];
            top--;
            return val;
        }
    
        /** * TODO 遍历，从栈顶开始 */
        public void list() { 
            if (isEmpty()) { 
                System.err.println("出栈失败，栈为空");
            }
            for (int i = top; i >= 0; i--) { 
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }
        }
    }

编写测试代码

public static void main(String[] args) { 
    
            ArrayStack stack = new ArrayStack(5);
            String key = "";
            boolean loop = true;
            Scanner sc = new Scanner(System.in);
    
            while (loop) { 
                System.out.println("s 显示栈");
                System.out.println("e 退出程序");
                System.out.println("push 入栈");
                System.out.println("pop 出栈");
                System.out.println("----------------");
                System.out.println("请选择:");
                key = sc.next();
                switch (key) { 
                    case "s":
                        stack.list();
                        break;
                    case "push":
                        System.out.println("请输入一个数");
                        int val = sc.nextInt();
                        stack.push(val);
                        break;
                    case "pop":
                        try { 
                            int res = stack.pop();
                            System.out.println("出栈的数据是:" + res);
                        } catch (Exception e) { 
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "e":
                        sc.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序已退出");
        }

感兴趣的读者可以尝试一下，这只是用数组实现了一个简单的栈，当然还能使用链表来实现栈。最重要是了解栈的特性。

> 参考资料：  
> 作者：韩顺平  
> 课程：《Java数据结构与算法》