java中的用数组模拟栈和用链表模拟栈_用数组模拟栈和用链表模拟栈优缺点

栈（stack）
1概述：
①栈是一个后进先出(LIFO, Last In First Out)的有序列表。
②栈的插入和删除只能在线性表的同一端进行。允许插入和删除的一端称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
③根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
④出栈(pop)和入栈(push)的概念(如下图所示)


2. 用数组实现栈

1. 用数组实现栈的思路分析
   ①.定义一个 top 来表示栈顶，初始化为 -1;
   ②. 入栈的操作，当有数据加入到栈时， top++; stack[top] = data;
   ④. 出栈的操作， int value = stack[top]; top–, return value;
   

2.代码实现

public class ArrayStackDemo {
    public static void main(String[] args) {
        //创建一个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) {
                        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;//栈顶

            //构造器
            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() {
                if (isEmpty()) {
                    System.out.println("栈空");
                    return;
                }
                for (int i = top; i >= 0; i--) {
                    System.out.printf("stack[%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

3 用链表实现栈
1）用链表实现栈的思路分析
入栈：相当于新new一个头结点，然后让新节点指向单链表的头结点
出栈：只要将链表的头指针后移到它的next，将next作为新的头结点
2）代码实现

public class LinkedListStackDemo {
    public static void main(String[] args) {
        Node node1 = new Node(1, "貂蝉");
        Node node2 = new Node(2, "西施");
        Node node3 = new Node(3, "王昭君");
        Node node4 = new Node(4, "杨玉环");
        Stack stack = new Stack();
        stack.push(node1);
        stack.push(node2);
        stack.push(node3);
        stack.push(node4);
        for(int i=0;i<4;i++){
            Node popNode = stack.pop();
            System.out.println(popNode);
        }
    }
}

//栈
class Stack{
    private Node head = new Node(0,"");
        //入栈
    public void push(Node newNode){
          //创建辅助指针
         Node temp = head;
         //栈为空时
        if(temp.next == null){
            temp.next = newNode;
        }else{
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    //出栈
    public Node pop(){
       //栈空
        if(head.next == null){
       //抛出异常结束方法
            throw new RuntimeException("栈空，不能取数据");
        }
         //创建辅助指针
        Node temp = head;
        if(temp.next.next != null){
            Node popNode = temp.next;
            temp.next = temp.next.next;
            return popNode;
        }else{
            return temp.next;
        }
    }
}



        //节点类
class Node{
    public int no;
    public String name;
    public Node next;
    public Node(int no,String name){
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node [no=" + no + ", name=" + name + "]";
     }
    }

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