数组和链表模拟栈（Java）

ゞ浴缸里的玫瑰 2024-04-08 11:26 71阅读 0赞

数组模拟栈

这是代码运行界面，

![9c06e71439374e2e9c56bf86a4ab7792.png][]

package com.ldm.stack;
    
    import java.util.Scanner;
    
    /**
     * @author 梁东明
     * 2022/8/23
     * 86139
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class ArrayStackDemo {
        public static void main(String[] args) {
            ArrayStack stack = new ArrayStack(6);
            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 "exit":
                        scanner.close();
                        loop =false;
                        break;
                    case "push":
                        System.out.println("请输入一个数");
                        int value = scanner.nextInt();
                        stack.push(value);
                        break;
                    case "pop":
                        try {
                            int res = stack.pop();
                            System.out.println("取出的数据是："+ res);
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序已退出。。。");
    
        }
    }
    class ArrayStack{
        private int maxSize;     //栈的大小
        private int[] stack;      //存放栈的数据
        private int top = -1;     //初始化top = -1
    
        public ArrayStack(int maxSize) {
            this.maxSize = maxSize;
            stack = new int[this.maxSize]; //初始化数组栈的容量
        }
    
        //判断栈满
        public boolean isFull(){
    
            return top == maxSize - 1;
        }
        //判断栈空
        public boolean isEmpty(){
            return top == -1;
        }
        //入栈
        public void push(int value){
            //判断栈满
            if (isFull()){
                System.out.println("栈满，无法插入元素");
                return;
            }
            top ++;
            stack[top] = value;
        }
        //出栈
        public int pop(){
            //判断是否空栈
            if (isEmpty()){
                throw new RuntimeException("栈空，无法出栈");
            }
            int value = stack[top];
            top--;
            return value;
        }
        //显示栈元素遍历栈，从栈顶开始
        public void list(){
            //判断栈是否为null
            if (isEmpty()){
                System.out.println("没有元素");
                return;
            }
            //从栈顶显示元素
            for (int i = top; i > 0; i--) {
                System.out.println("第" + i +"个元素是："+stack[i]);
            }
        }
    }

链表模拟栈是韩老师教程的课后习题，我觉得有必要加深对栈和链表的学习 ，所以又花了一个小时把代码敲出来了，供大家参考。

![88e5b1774b2242f383d36527bf4e3ea1.png][]

package com.ldm.stack;
    
    import java.util.Scanner;
    
    /**
     * @author 梁东明
     * 2022/8/23
     * 86139
     * 点击setting在Editor 的File and Code Templates 修改
     */
    public class LinkedListStackDemo {
        public static void main(String[] args) {
    
            LinkedListStack stack = new LinkedListStack();
    
            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.show();
                        break;
                    case "exit":
                        scanner.close();
                        loop =false;
                        break;
                    case "push":
                        System.out.println("请输入一个数");
                        int value = scanner.nextInt();
                        Node node = new Node(value);
                        stack.push(node);
                        break;
                    case "pop":
                        try {
                            stack.pop();
                            System.out.println("取出的数据是：");
                        } catch (Exception e) {
                            System.out.println(e.getMessage());
                        }
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序已退出。。。");
    
        }
    }
    
    //注意，链栈和数组栈的区别是，数组栈有最大容量限制，而链栈则没有，想插入多少数据就插入多少数据
    class LinkedListStack{
        private Node top = new Node(-1);
    
    
        //判断栈空
        public boolean isEmpty(){
            return top.getNext() == null;
        }
        //入栈
        public void push(Node node){
            //如果栈中没有元素就插入第一个元素
            if (isEmpty()){
                top.setNext(node);
                return;
            }
            //如果栈中有元素了，就使用头插法的方式入栈
            //定义一个辅助变量指向头节点的下一个节点
            Node temp = top.getNext();
    
            top.setNext(node);
            node.setNext(temp);
    
        }
    
        //出栈
        public void pop(){
            //判断栈是否为null
            if (top == null) {
                System.out.println("栈为null，无法出栈。。。");
                return;
            }
            System.out.println("出栈节点为：" + top.getNext().getData());
            top = top.getNext();
        }
        //遍历链表栈
        public void show(){
            //判断栈是否为null
            if (isEmpty()) {
                System.out.println("栈为null，没有元素。。。");
                return;
            }
            Node temp = top;
            while (true) {
                // 将temp后移， 一定小心空指针异常，我就是没有这个if语句，害我找bug花了两个小时
                if (temp.getNext() != null){
                    // 输出节点的信息
                    System.out.println(temp.getNext().getData());
                    temp = temp.getNext();
                }
            }
        }
    
    
    }
    
    class Node{
        private int data;
        private  Node next;
    
    
        public Node(int data) {
            this.data = data;
        }
    
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    }

不知道大家的代码编辑器是不是idea，如果不是的话，建议花点时间学习使用idea。如果还是用eclipse的话，给大家分享一下韩老师用eclipse写的代码。供大家参考。

这是代码运行界面

![8695df78d44149438c6e5805a189172f.png][]

这是韩老师的代码

package com.ldm.Stack;
    
    import java.util.Scanner;
    
    public class ArrayStackDemo {
    
    	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("程序退出~~~");
    	}
    
    }
    
    //定义一个 ArrayStack 表示栈
    class ArrayStack {
    	private int maxSize; // 栈的大小
    	private int[] stack; // 数组，数组模拟栈，数据就放在该数组
    	private int top = -1;// top表示栈顶，初始化为-1
    	
    	//构造器
    	public ArrayStack(int maxSize) {
    		this.maxSize = maxSize;
    		stack = new int[this.maxSize];
    	}
    	
    	//栈满
    	public boolean isFull() {
    		return top == maxSize - 1;
    	}
    	//栈空
    	public boolean isEmpty() {
    		return top == -1;
    	}
    	//入栈-push
    	public void push(int value) {
    		//先判断栈是否满
    		if(isFull()) {
    			System.out.println("栈满");
    			return;
    		}
    		top++;
    		stack[top] = value;
    	}
    	//出栈-pop, 将栈顶的数据返回
    	public int pop() {
    		//先判断栈是否空
    		if(isEmpty()) {
    			//抛出异常
    			throw new RuntimeException("栈空，没有数据~");
    		}
    		int value = stack[top];
    		top--;
    		return value;
    	}
    	//显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
    	public void list() {
    		if(isEmpty()) {
    			System.out.println("栈空，没有数据~~");
    			return;
    		}
    		//需要从栈顶开始显示数据
    		for(int i = top; i >= 0 ; i--) {
    			System.out.printf("stack[%d]=%d\n", i, stack[i]);
    		}
    	}
    	
    }

如果大家以后打算学习 韩老师的 [数据结构与基本算法的教程][Link 1]，可以关注我，我以后会一边学习，一边分享教程中的代码供大家参考。当然啦，会有我自己写的更详细的注解以及课后习题。大家一起促进学习。

如果只是应付作业的话可以看一下我的主页，以后我会源源不断的更新用 java写的 算法和数据结构内容。总有一样可以应付作业的。

最后的最后，介绍一下，我是小白，很高兴认识你。期待与你的下次相遇。

[9c06e71439374e2e9c56bf86a4ab7792.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d9bd7048b00849068e9b3581c7743aba.png
[88e5b1774b2242f383d36527bf4e3ea1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/64c82704e1e744a4a169cd84f05216fb.png
[8695df78d44149438c6e5805a189172f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2611664db3464012b53b7f015a300493.png
[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=33&spm_id_from=pageDriver&vd_source=027fde985896626031abccc06ce8b031