数组和单链表模拟实现栈的出入栈（java实现）_用单链表实现栈,问入栈的语句

栈（一）

一、栈的介绍
1.栈的英文名为：stack
2.栈是一个先入后出的有序列表。
3.栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。
4.根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
5.出栈（pop）和入栈（push）如下图所示


二、数组模拟实现栈

代码实现：

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(4);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        while (loop){
            System.out.println("=================菜单==============");
            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" :
                    arrayStack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数：");
                    int value = scanner.nextInt();
                    arrayStack.push(value);
                    break;
                case "pop":
                    try {
                        int res = arrayStack.pop();
                        System.out.println("出栈的数据是：" + res);
                    } catch (Exception e) {
                        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;//top表示栈顶，初始化为-1

    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[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;
        }
       stack[++top] = value;
    }
    //出栈
    public int pop(){
        if (isEmpty()){
           throw new RuntimeException("栈空，没有数据可以出栈");
        }
        return stack[top--];
    }

    //遍历栈
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据");
            return;
        }
        for (int i=top;i>=0;i--){
            System.out.println("stack[" + i + "]:" + stack[i]);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

结果如下：

三、单链表模拟实现栈（自己写的有问题可以私信一起沟通）
代码如下

public class LinkedStackDemo {
    public static void main(String[] args) {
        LinkedStack linkedStack = new LinkedStack(4);
        String key = "";
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        while (loop){
            System.out.println("=================菜单==============");
            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" :
                    linkedStack.list();
                    break;
                case "push":
                    System.out.println("请输入一个数：");
                    int value = scanner.nextInt();
                    linkedStack.push(value);
                    break;
                case "pop":
                    try {
                        Node res = linkedStack.pop();
                        System.out.println("出栈的数据是：" + res.getData());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("您已经退出菜单程序");
    }
    }


class LinkedStack{
    Node head = new Node(0);
    public int maxSize;
    public LinkedStack(int maxSize){
        this.maxSize = maxSize;
    }
    //栈满
    public boolean isFull(){
        int count = 0;
        Node temp = head.getNext();
        while(temp!=null){
            count++;
            temp = temp.getNext();
            if (count == maxSize){
                return true;
            }
        }
        return false;
    }

    //栈空
    public boolean isEmpty(){
        return head.getNext() == null;
    }

    //入栈
    public void push(int value){
        if (isFull()){
            System.out.println("栈满，数据不能入栈");
            return;
        }
        Node newNode = new Node(value);
        Node temp = head;
        newNode.setNext(temp.getNext());
        temp.setNext(newNode);
    }

    //出栈
    public Node pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，没有数据可以出栈");
        }
        Node temp = head;
        Node res = temp.getNext();
        temp.setNext(temp.getNext().getNext());
        return res;
    }

    //显示栈元素
    public void list(){
        if (isEmpty()){
            System.out.println("栈中无元素");
            return;
        }
        Node temp = head.getNext();
        while (temp!=null){
            System.out.println(temp.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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

运行结果如下：

本篇文章是根据尚硅谷数据结构视频进行总结和代码实现，谢谢尚硅谷大学教会我java知识