Java中栈的实现，分别用数组和用链表来模拟_java中堆栈使用数组还是连表

栈(stack)
栈是一个先进后出的有序列表
栈的插入和删除只可以在同一段操作，允许删除和插入的一端是栈顶(top),另一端为固定的一端，称为栈底（bottom)

实现栈思路
1.使用数组来模拟栈
2.定义一个top来表示栈顶，初始化为-1.
3.入栈的操作，当有数据入栈的时候，top++,stack[top]=data
4.出栈操作，当有数据出栈时候，int value = stack[top],top–;

使用数组来模拟实现

package com.gsy.stack;

import java.util.Scanner;

/**
 * @program: DataStructures
 * @description: 用数组来实现栈
 * @author: GSY
 * @create: 2020-03-31 21:42
 **/
public class ArrayStackDemo {

    public static void main(String[] args){

        //测试一下是否正确

        ArrayStack stack = new ArrayStack(4);
        int flag;
        boolean loop = true;//控制是否退出菜单
        Scanner scanner = new Scanner(System.in);
        while (loop){

            System.out.println("1:表示显示栈");
            System.out.println("2:退出程序");
            System.out.println("3:添加数据入栈");
            System.out.println("4:表示取出数据");
            System.out.println("输入你的选择");
            flag = scanner.nextInt();
            switch (flag){
                case 1: stack.list();
                     break;
                case 2:   scanner.close();
                   loop = false;
                    break;
                case 3:
                    System.out.println("请输入一个数据");
                    stack.push(scanner.nextInt());
                    break;
                case 4:
                    try {
                        int res = stack.pop();
                        System.out.printf("出栈的数据是%d\n",res);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
    }

}


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()){
            System.out.println("栈空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈的情况，遍历时需要从栈顶开始遍历

    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据");
            return;
        }
        //需要从栈顶开始遍历
        for (int i =0 ;i<=top;i++){
            System.out.printf("%d的数据为%d\n",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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

使用链表来模拟

package com.gsy.stack;

import java.util.Scanner;

/**
 * @program: DataStructures
 * @description: 使用单向链表实现栈
 * @author: GSY
 * @create: 2020-03-31 22:14
 **/
public class SingleLinkedListStackDemo {


    public static void main(String[] args){

        StackManage stackManage = new StackManage();

        int flag;
        boolean loop = true;//控制是否退出菜单
        Scanner scanner = new Scanner(System.in);
        while (loop){

            System.out.println("1:表示显示栈");
            System.out.println("2:退出程序");
            System.out.println("3:添加数据入栈");
            System.out.println("4:表示取出数据");
            System.out.println("输入你的选择");
            flag = scanner.nextInt();
            switch (flag){
                case 1: stackManage.show();
                    break;
                case 2:   scanner.close();
                    loop = false;
                    break;
                case 3:
                    System.out.println("请输入一个数据");
                    stackManage.push(scanner.nextInt());
                    break;
                case 4:
                    stackManage.pop();
                    break;
                default:
                    break;
            }
        }

    }

}



class StackManage{

    private SingleLinkedListStack stackTop = new SingleLinkedListStack(-1);

    //往栈里面加数据
    public void push(int value){

        SingleLinkedListStack res = new SingleLinkedListStack(value);

        SingleLinkedListStack temp = stackTop.next;
        res.next = temp;
        stackTop.next = res;
    }

    //出栈
    public void pop(){

        //判断栈是否为空
        if (stackTop.next == null){
            System.out.println("栈为空");
            return;
        }

        SingleLinkedListStack temp = stackTop.next;
        System.out.printf("出栈的数据为:%d\n",temp.num);
        stackTop.next = temp.next;
    }

    //打印栈
    public void show(){
        //判断栈是否为空
        if (stackTop.next == null){
            System.out.println("栈为空");
            return;
        }

        SingleLinkedListStack temp = stackTop.next;
        while (true){
            if (temp == null){//打印完了，到了栈底
                break;
            }
            System.out.printf("数据是：%d\n",temp.num);
            temp = temp.next;
        }
    }


}



class SingleLinkedListStack{

    public int num;
    public SingleLinkedListStack next;

    public SingleLinkedListStack(int num){
        this.num = num;
    }

}
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