java实现栈（数组模拟和单链表模拟）_java实现单链表模拟栈

一，基本概念简介：
栈是一种后进先出的数据结构。一个元素如果最后进栈，那么最先出栈，一般都是用数组来模拟栈的特点。可以想象一个数组，现在设置两个指针top指针和base指针，一般来说base指针指向栈底并且这个指针是不移动的，起到一个标识作用。而top指针指向随着栈内元素的个数而移动，一般来说top指针指向栈顶元素的位置。元素进栈时把元素存储在top所指的数组下标位置，然后top指针+1。元素出栈时，先将top位置的元素保存，再将top指针减1。用数组模拟栈时，数组的容量是有限的，所以入栈之前要考虑一下栈是否已经满了，如果满了那么就无法继续入栈。在出栈之前要考虑一下栈是否为空，空就没办法进行出栈操作了。而用链表似乎更加方便，模拟队列入栈时动态添加节点不用考虑队列为满的情况，出队时判断一下队列是否为空即可。入栈和出栈操作相当于在链表的表头处进行添加节点和删除节点。

二、代码实现：
数组基本操作；
栈满：top==MaxSize-1
栈空：top==bottom
入栈：top++; stack[top]=number;
出栈：int value=stack[top]; top--;
取栈顶元素：stack[top]
遍历栈元素：

public void list()
    {
        int temp=top;
        while (temp!=bottom)
        {
            System.out.printf("%5d",stack[temp]);
            temp--;
        }
        System.out.print("\n");
    }
1
2
3
4
5
6
7
8
9
10

链表实现基本操作：
栈满：无
栈空：head.next==null
入栈：newNode.next=head.next; head.next=newNode;
出栈：linklistnode temp= head.next; head.next=head.next.next; return temp;

整体代码实现：

package com.linear.test;

import java.util.Scanner;

/**
 * @author ymm
 * @create 2020-10-06 13:56
 */
public class StackByArrayDemo {
    //测试数组模拟代码
    public static void main(String []args)
    {
        //StackByArray arraystack= new StackByArray(3);
        StackByLinkList linklisttack=new StackByLinkList();
        String option="";
        boolean flag=true;
        Scanner sc=new Scanner(System.in);
        while(flag)
        {
            System.out.print("show: 显示栈\n");
            System.out.print("exit: 退出\n");
            System.out.print("push: 数据压栈\n");
            System.out.print("pop: 数据退栈\n");
            System.out.print("head: 显示栈的头元素\n");
            System.out.print("输入你的选择\n");
            option=sc.next();
            switch (option)
            {
                case "show":
                    //arraystack.list();
                    linklisttack.list();
                    break;
                case "exit":
                    sc.close();
                    flag=false;
                    break;
                case "push":
                    System.out.print("输入要入栈的元素\n");
                    int num=sc.nextInt();
                    linklistnode newNode =new linklistnode(num);
                    linklisttack.push(newNode);
                    //arraystack.push(num);
                    break;
                case "pop":
                    System.out.println("出栈元素为:");
                    System.out.println(linklisttack.pop());
                    break;
                case "head":
                    if(linklisttack.IsEmpty())
                        System.out.print("栈空，没有栈顶元素\n");
                    else
                        //System.out.print("首元素为"+arraystack.gethead()+"\n");
                          System.out.println("栈的首元素为");
                          System.out.println(linklisttack.gethead());
                    break;
            }
        }

    }
}

//数组模拟实现栈
class StackByArray
{
    int MaxSize;    //栈的容量
    int []stack;  //数组存储栈的数据
    int top;    //栈顶指针
    int bottom; //栈底指针
    //初始化栈空间
    public StackByArray(int MaxSize)
    {
        this.MaxSize=MaxSize;
        stack= new int[MaxSize];
        top=-1;
        bottom=-1;
    }
    //判断栈空
    public boolean IsEmpty()
    {
        if(top==bottom)
            return true;
        else
            return false;
    }
    //判断栈满
    public boolean IsFull()
    {
        if(top==MaxSize-1)
            return true;
        else
            return false;
    }
    //出栈
    public void pop()
    {
        if(IsEmpty()){
            System.out.print("栈空，没有元素可以出栈\n");
            return ;
        }
        int value=stack[top];
        top--;
        System.out.print("出栈成功"+"出栈元素为"+value+"\n");
        return ;
    }
    //入栈
    public void push(int number)
    {
        if(IsFull())
        {
            System.out.print("栈已满，无法入栈\n");
            return;
        }
        else
        {
            top++;
            stack[top]=number;
            return;
        }

    }
    //取头元素
    public int gethead()
    {
        if(IsEmpty())
        {
            System.out.print("栈空，没有栈顶元素,返回0\n");
            return 0;
        }
        return stack[top];
    }
    //遍历栈
    public void list()
    {
        int temp=top;
        while (temp!=bottom)
        {
            System.out.printf("%5d",stack[temp]);
            temp--;
        }
        System.out.print("\n");
    }
}

//链表模拟栈,不存在队列满的情况了
class StackByLinkList{
    linklistnode head =new linklistnode(0);
    //入栈，头插法模拟
    public void push(linklistnode newNode)
    {
        newNode.next=head.next;
        head.next=newNode;
    }
    //出队
    public linklistnode pop()
    {
        if(IsEmpty())
        {
            System.out.print("队列为空，没有元素出队");
            return head;
        }
        linklistnode temp= head.next;
        head.next=head.next.next;
        return temp;
    }
    //遍历栈
    public void list()
    {
        if(head.next==null)
            System.out.print("链表为空\n");
        else {
            linklistnode temp= head.next;
            while (temp!=null){
                System.out.println(temp);
                temp=temp.next;
            }
        }

    }
    public boolean IsEmpty()
    {
        if(head.next==null)
            return true;
        else
            return false;
    }
    public  linklistnode gethead()
    {
        return head.next;
    }


}
//定义链表结构,默认头结点不存储数据
class linklistnode{
    int value;
    linklistnode next;
    public linklistnode(int value)
    {
        this.value=value;
    }

    @Override
    public String toString() {
        return "linklistnode{" +
                "value=" + value +
                '}';
    }
}

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

B站java数据结构学习