【数据结构】(队列的Java实现与经典应用)

队列的出现迎合了很多Java复杂结构的应用,如二叉树的层序遍历,本篇用两种方法(数组\链表)实现了队列的定义,与此同时还有一些经典的方法进行了定义,涵盖了简单队列的内容,欢迎阅览喔( ͡° ͜ʖ ͡°)✧

前言

与栈的结构相反，队列是一种先进先出的特殊表结构，普通队列的假溢出现象十分糟糕，所有目前对于队列的实现一般都使用循环队列，需要注意的是为了区分空队列和满队列的条件不同，故需要牺牲一个存储位置来满足循环队列的判断，具体可见数组形式的队列实现代码。

队列的数组实现

package SquenceList;

public class ArrayQueue<T> {

		private T[] datas;
		private int rear;
		private int front;
		private int maxsize;
		private int realmaxsize; //真正储存的只有最大值-1个元素
		//队列的初始化
		public ArrayQueue(int maxsize) {
			if(maxsize<1) {
				maxsize=1;
			}
			this.maxsize = maxsize;
			realmaxsize = maxsize-1;
			rear = 0;
			front = 0;
			datas = (T[])new Object[maxsize];
		}
		//判断队列是否为空
		public boolean isEmpty() { 
			return (front==rear);
		}
		//判断队列是否已满
		public boolean isFull() {
			//注意循环队列判断是否已满的条件，为了和队空的条件区别
			if((rear+1)%maxsize==front) {
				rear--;
				return true;
			}
			return false;
		}                                      //所以这里牺牲了一个存储空间从而找到了判断队满的条件
		//进队
		public void push(T t) {
			if(isFull()) {
				System.out.println("队满啦，不能再进啦～");
				return;
			}
			datas[rear]=t;
			rear++;
			rear = rear%maxsize;  //循环队列的特点，若要知其值则%maxsize
			return;
		}
		//出队
		public T pop() {
			if(isEmpty()) {
				System.out.println("我队什么都没有，不可以再出去了～");
				return null;
			}
			T data = datas[front++];
			front = front%maxsize;
			return data;
		}
		//获取队列的队头位置
		public int getFront() {
			return front;
		}
		//获取队列的队尾位置
		public int getRear() {
			int end = rear-1;
			return end;  //倒数第二个位置放着队列的队尾元素
		}
		//获取队列的对头位置元素
		public T getFrontData() {
			return datas[front];
		}
		//获取队列的队尾位置元素
		public T getRearData() {
			int end = rear-1;
			return datas[end]; //队尾指针始终为空，故队尾元素在倒数第二个
		}
		//获取队列的元素
		public T[] getDatas() {
			return datas;
		}
		//获取队列的最大长度
		public int getLength() {
			return realmaxsize;  //这里因为我们创建的是循环形式的队列，所以在判断队列是否满的时候需要牺牲一个位置
		}                      //所以真实的存储空间应为空间数-1
	public static void main(String[] args) {
		ArrayQueue myqueue = new ArrayQueue(5);
		System.out.println("我的队列现在是空的吗:"+myqueue.isEmpty());
		System.out.println("我的队列现在是满的吗:"+myqueue.isFull());
		myqueue.push(1);
		System.out.println("现在队头是第几个呢:"+myqueue.getFront());
		myqueue.push(3);
		myqueue.push(5);
		//myqueue.push(7);
		//myqueue.push(9); //空间只能存放最大数量-1个数量的元素
		System.out.println("在我入队了一些元素后，现在我的队列现在是空的吗:"+myqueue.isEmpty());
		System.out.println("在我入队了一些元素后，现在我的队列现在是满的吗:"+myqueue.isFull());
		System.out.println("出队:"+myqueue.pop());
		//System.out.println("出队:"+myqueue.pop());
		System.out.println("现在我的队伍都有谁呢:"+myqueue.getDatas());
		System.out.println("现在队头是第几个呢:"+myqueue.getFront());
		System.out.println("现在队尾是第几个呢:"+myqueue.getRear());
		System.out.println("现在队头是谁呢:"+myqueue.getFrontData());
		System.out.println("现在队尾是谁呢:"+myqueue.getRearData());
		System.out.println("我的队列能放多少个元素呢:"+myqueue.getLength());
		}
	}

队列的链表实现

package Queue;

public class LinkedQueue<T> {

	private Node<T> front;
	private Node<T> rear;
	private int maxsize;
	class Node<T>{  //同样用内部类来作为节点的定义
		private T data;
		public Node<T> next;
		public Node (){
			this.data=null;
			this.next=null;
		}
		public Node(T data) {
			this.data = data;
			this.next = null;
		}
		public T getData() {
			return data;
		}
		public void setData(T data) {
			this.data = data;
		}
		public Node getNext() {
			return this.next;
		}
	}
	//构造链队的初始化方法
	public LinkedQueue() {
		this.front = new Node();
		this.rear = new Node();
		maxsize = 0;
	}
	//初始化链队
	public void initQueue() {
		this.front = null;
		this.rear = null;
		maxsize = 0;
	}
	//入队
	//判断链队是否为空
	public boolean isEmpty() {
		if(front.next==null||rear.next==null) {
			return true;
		}else {
			return false;
		}
	}
	//入队
	public void push(T data) {
		Node<T> node = new Node<T>(data);
		if(isEmpty()) {
			front.next = node;
			rear.next = node;
			maxsize++;
		}else {
			node.next = front.next;
			front.next = node;
			maxsize++;
		}
	}
	//出队
	public Node pop() {
		if(isEmpty()) {
			System.out.println("这里是空的无法出队哦");
			return null;
		}else if(maxsize ==1) {
			Node node = front.next;
			initQueue();
			return node;
		}else {
			Node end = front;
			for(int i=1;i<maxsize-1;i++) {
				end = end.next;
			}
			Node node = rear.next;
			rear.next = end.next;
			maxsize--;
			return node;
			
		}
	}
	public static void main(String[] args) {
		LinkedQueue<Integer> lq = new LinkedQueue<Integer>();
		System.out.println("我现在还没有入队，队是空的吗？"+lq.isEmpty());
		lq.push(1);
		lq.push(2);
		lq.push(3);
		lq.push(4);
		System.out.println("我入队了一些元素，现在队还是空的吗？"+lq.isEmpty());
		System.out.println("出队所有元素元素：");
		System.out.println(lq.pop().data);
		System.out.println(lq.pop().data);
		System.out.println(lq.pop().data);
		System.out.println(lq.pop().data);
	}
}