栈的快速入门--数组模拟栈

喜欢ヅ旅行 2023-05-22 12:28 37阅读 0赞

**1 栈的介绍**

1.  栈的英文为(stack)
2.  栈是一个 先入后出(FILO-First In Last Out) 的有序列表。
3.  栈(stack) 是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。 。 允许插入和删除的  
    一端，为 变化的一端，称为栈顶(Top) ，另一端为 固定的一端，称为栈底(Bottom) 。
4.  根据栈的定义可知 ， 最先放入栈中元素在栈底 ， 最后放入的元素在栈顶 ， 而删除元素刚好相反 ， 最后放入的元  
    素最先删除，最先放入的元素最后删除
5.  图解方式说明出栈(pop) 和入栈(push) 的概念  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU5OTM3Nw_size_16_color_FFFFFF_t_70]  
    **2 栈的应用场景**

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

1.  图形的深度优先(depth 一 first)搜索法。  
    **3 数组模拟栈**  
    实现思路：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU5OTM3Nw_size_16_color_FFFFFF_t_70 1]  
    代码实现

//数组模拟栈的取和存
    public class ArrayStackDamo {
    	public static void main(String[] args) {
    		// 测试一下ArrayStack 是否正确
    		// 先创建一个ArrayStack对象->表示栈
    		ArrayStack stack = new ArrayStack(4);
    		String key = "";
    		boolean loop = true; // 控制是否退出菜单
    		Scanner scanner = new Scanner(System.in);
    
    		while (loop) {
    			System.out.println("show: 表示显示栈");
    			System.out.println("exit: 退出程序");
    			System.out.println("push: 表示添加数据到栈(入栈)");
    			System.out.println("pop: 表示从栈取出数据(出栈)");
    			System.out.println("请输入你的选择");
    			key = scanner.next();
    			switch (key) {
    			case "show":
    				stack.list();
    				break;
    			case "push":
    				System.out.println("请输入一个数");
    				int value = scanner.nextInt();
    				stack.push(value);
    				break;
    			case "pop":
    				try {
    					int res = stack.pop();
    					System.out.printf("出栈的数据是 %d\n", res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				break;
    			case "exit":
    				scanner.close();
    				loop = false;
    				break;
    			default:
    				break;
    			}
    		}
    
    		System.out.println("程序退出~~~");
    	}
    
    }
    
    //定义一个数组表示栈
    class ArrayStack {
    	private int maxSize;// 栈的大小
    	private int[] stack;// 数组，模拟栈
    	private int top;// 表示栈顶，初始化为-1
    	// 构造器
    
    	public ArrayStack(int maxSize) {
    		this.maxSize = maxSize;
    		stack = new int[maxSize];
    	}
    
    	// 栈满
    	public boolean isFull() {
    		return top == maxSize - 1;
    	}
    
    	// 栈空
    	public boolean ifEmpty() {
    		return top == -1;
    	}
    
    	// 入栈--push
    	public void push(int value) {
    		// 先判断是否栈满
    		if (isFull()) {
    			// 抛出异常
    			// throw new RuntimeException("栈满");
    			return;
    		}
    		top++;// 可以理解为数组扩容。通过top参数来扩容
    		stack[top] = value;
    	}
    
    	// 出栈--pop，将栈顶的数据返回
    	public int pop() {
    		// 先判断是否栈空
    		if (ifEmpty()) {
    			throw new RuntimeException("栈空，么有数据");
    		}
    		int value = stack[top];// top是数组中的最后一个数据
    		top--;
    		return value;
    	}
    
    	// 显示栈的情况，也就是遍历。需要从栈顶开始显示数据
    	public void list() {
    		if (ifEmpty()) {
    			System.out.println("没有数据");
    			return;
    		}
    		// 需要从栈顶开始显示数据
    		for (int i = top; i >= 0; i--) {
    			System.out.println(System.out.printf("stack[%d]=%d\n", i, stack[i]));
    		}
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU5OTM3Nw_size_16_color_FFFFFF_t_70]: /images/20230521/cfd48b2136434aeaaab79ccca25bcda1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU5OTM3Nw_size_16_color_FFFFFF_t_70 1]: /images/20230521/affc9838a74f4cc0a833309a62f4ddb9.png