数据结构——用数组实现栈和队列

目录

用数组实现栈和队列

一、数组实现栈

1.stack类

2.测试

二、数组实现队列

1.Queue类

2.测试

---

查询——数组：数组在内存中是连续空间

增删改——链表：链表的增删改处理更方便一些

满足数据先进后出的特点的就是栈，先进先出就是队列

用数组实现栈和队列

一、数组实现栈

1.stack类

public class StackDemo {private int[] arr;private int i=-1;public StackDemo(int size) {arr=new int[size];}//入栈public void add(int value) {//栈满判断if(i==arr.length-1) {System.out.println("stack full!");return;}i++;arr[i]=value;}//出栈public int get() {//栈空判断if(i==-1) {System.out.println("stack empty");return -1;}int data=arr[i];i--;return data;}
}

main方法调用

package 数据结构;public class test2 {public static void main(String[] args) {StackDemo stack=new StackDemo(5);stack.add(1);stack.add(2);stack.add(6);stack.add(3);stack.add(9);System.out.println(stack.get());System.out.println(stack.get());System.out.println(stack.get());System.out.println(stack.get());System.out.println(stack.get());System.out.println(stack.get());}
}

2.测试

栈满测试

 栈空测试

---

二、数组实现队列

注意观察，入队过程中我们使用到另一个“幽灵指针”，这是通过“r%arr.length”来实现的，本质上r的大小是不变的。

1.Queue类

package 数据结构;public class QueueDemo {private int arr[];private int c=0;private int r=0;public QueueDemo(int size) {arr=new int[size];}public void add(int value) {// 栈满判断if(r-c==arr.length) {System.out.println("Queue full!");return;}arr[r%arr.length]=value;r++;}public int get() {// 栈空判断if(r==c) {System.out.println("Queue empty!");return -1;}int data=arr[c%arr.length];c++;return data;}}

 main方法调用

package 数据结构;public class test3 {public static void main(String[] args) {QueueDemo queue=new QueueDemo(5);queue.add(1);queue.add(2);queue.add(6);queue.add(3);queue.add(9);queue.add(10);System.out.println(queue.get());System.out.println(queue.get());System.out.println(queue.get());System.out.println(queue.get());System.out.println(queue.get());queue.add(4);System.out.println(queue.get());System.out.println(queue.get());}
}

2.测试