7、栈-数组模拟一个栈

来源：https://www.bilibili.com/video/BV1B4411H76f?p=28

一、栈

1、是一个先入后出的有序列表；

2、插入删除数据时，栈顶的指针会发生变化，栈底是固定的；

3、先插入的数据放在栈底，后插入的数据更接近栈顶，删除是从栈顶开始删除，最后才到栈底。

二、数组模拟栈的思路

1、定义一个指向栈顶的指针top，初始化为-1，定义代表栈的数组stack；

2、当向栈中压入数据时，【top++】，【stack[top]=data】；

3、当从栈中弹出数据时，弹出来的数据【value=stack[top]】，同时【top--】。

三、实现

1、创建一个数组模拟栈的类ArrayStack，其中包含的属性有：栈的大小maxSize，指向栈顶的指针top，初始值为-1，用来存放数据的数组arr。类中目前包含一个入栈的方法，由于入栈时必须保证栈是不满的，因此额外增加了一个判断栈满的方法；为了检测方法的有效性，加入了一个展示方法，通过遍历展示栈中的内容；想要得到栈中的内容必须保证栈是非空的，所以又添加了一个判断栈为空的方法。

 1 public class ArrayStack {
 2     private int maxSize;//栈的大小
 3     private int top = -1;//栈顶指针
 4     private int[] arr;//模拟栈的数组
 5 
 6     public ArrayStack(int maxSize) {
 7         this.maxSize = maxSize;
 8         arr = new int[maxSize];
 9     }
10 
11     //判断当前栈是否已经满了
12     public boolean isFull(){
13         return top == maxSize - 1;
14     }
15     //判断栈是否为空
16     public boolean isEmpty(){
17         return top == -1;
18     }
19 
20     //入栈
21     public void push(int val){
22         if(isFull()){
23             System.out.println("栈满，无法添加数据");
24             return;
25         }
26         top++;
27         arr[top] = val;
28     }
29     //出栈
30 
31 
32     //展示
33     public void show(){
34         if(isEmpty()){
35             System.out.println("栈空，无法展示");
36             return;
37         }
38         for (int i = 0; i <= top; i++) {
39             System.out.printf("arr[%d]=%d",i,arr[i]);
40             System.out.println();
41         }
42     }
43 }

测试

 1     public static void main(String[] args) {
 2         ArrayStack arrayStack = new ArrayStack(5);
 3 
 4         arrayStack.show();
 5         System.out.println();
 6 
 7         arrayStack.push(1);
 8         arrayStack.show();
 9         System.out.println();
10 
11         arrayStack.push(2);
12         arrayStack.show();
13         System.out.println();
14 
15         arrayStack.push(3);
16         arrayStack.show();
17         System.out.println();
18 
19         arrayStack.push(4);
20         arrayStack.show();
21         System.out.println();
22 
23         arrayStack.push(5);
24         arrayStack.show();
25         System.out.println();
26 
27         arrayStack.push(6);
28         arrayStack.show();
29         System.out.println();
30     }

结果

栈空，无法展示

arr[0]=1

arr[0]=1
arr[1]=2

arr[0]=1
arr[1]=2
arr[2]=3

arr[0]=1
arr[1]=2
arr[2]=3
arr[3]=4

arr[0]=1
arr[1]=2
arr[2]=3
arr[3]=4
arr[4]=5

栈满，无法添加数据
arr[0]=1
arr[1]=2
arr[2]=3
arr[3]=4
arr[4]=5

2、在类中补充出栈的操作

 1     //出栈
 2     public int pop(){
 3         if(isEmpty()){
 4             System.out.println("栈空，无法操作");
 5             return -1;
 6         }
 7         int val = arr[top];
 8         top--;
 9         return val;
10     }

测试

 1         int pop = arrayStack.pop();
 2         System.out.println("出栈的数据为："+pop);
 3 
 4         pop = arrayStack.pop();
 5         System.out.println("出栈的数据为："+pop);
 6 
 7         pop = arrayStack.pop();
 8         System.out.println("出栈的数据为："+pop);
 9 
10         pop = arrayStack.pop();
11         System.out.println("出栈的数据为："+pop);
12 
13         pop = arrayStack.pop();
14         System.out.println("出栈的数据为："+pop);
15 
16         pop = arrayStack.pop();
17         System.out.println("出栈的数据为："+pop);

结果

出栈的数据为：5
出栈的数据为：4
出栈的数据为：3
出栈的数据为：2
出栈的数据为：1
栈空，无法操作
出栈的数据为：-1