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

目录

用数组实现栈和队列

一、数组实现栈

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.测试