05、数据结构与算法 - 实战：队列

队列 - 先进先出 - 线性结构

可使用 数组、链表进行实现

1.1 简单数组队列 - 只能存满一次

特点：

1、 队首出队(front改变)、队尾入队(rear改变)；
2、 front==rear→队列为空；
3、 rear==数组最大下标→队列为满；
4、 ***rear：**记录上次入队的位置；**front：*记录上次出队的位置；

代码实现 - 只能存满一次

class SimpleArrayQueue {
   
     
	
	int capacity;   // 队列能存储的最大容量
	int front;     // 存储上一次 从数组中 移出的 元素位置  -- 出队时改变
	int rear;  	   // 存储 上一次  元素被增添在数组内的位置  -- 入队时改变
	int[] array;   // 数组队列的容器
	
	SimpleArrayQueue(int capacity) {
   
     
		this.capacity = capacity;
	}
	
	// 如果  上一次出队的位置 跟  上一次入队的位置 相同  -- 说明无元素在队内
	public boolean isEmpty() {
   
     
		if(rear == front) {
   
     
			return true;
		}
		return false;
	}
	
	// 如果 rear指示上次入队的数组位置，数组最大下标为( 容量-1 )，如果两者相等，说明队已经满，不可在入队
	public boolean isFull() {
   
     
		if( rear == capacity - 1) {
   
     
			return true;
		}
		return false;
	}
	
	// 入队，先验证上次入队的位置是否等于最大数组小标，在rear进行指针下移动，入队新元素
	public void enQueue(int element) {
   
     
		
		if(isFull()) {
   
     
			System.out.println("队列已经满");
			return;
		}
		array[++rear] = element;
	}
	
	// 出队，先验证是否上次入队、出队位置重合，不重合，在进行front指针下移，出队指针下移位置的元素
	public int deQueue() {
   
     
		if(isEmpty()) {
   
     
			throw new RuntimeException("队列中没有元素");
		}
		return array[++front];
	}
	
}

1.2 环形数组队列

1.2.1 代码实现#

隐喻：好比如front就是你要追的女孩子，rear就是你，front不喜欢你，你在怎么追，永远都会跟她有一步之遥，除非女孩子一步步的靠近你

代码实现 – rear不能追上front，导致永远会预留一个位置

class CircularQueue {
   
     
	int capacity;
	int front = 0;
	int rear = 0;
	int[] array;
	
	CircularQueue(int capacity) {
   
     
		this.capacity = capacity;
		array = new int[capacity];
	}
	
	// 查看 如果元素增加，rear指针是否与front重合，如果重合则不能添加
	// 为了保证 isEmpty() 具有空队的 判断
	boolean isFull() {
   
     
		return (rear + 1) % capacity == front;
	}
	
	// 一旦front追上rear， 则说明是空队
	boolean isEmpty() {
   
     
		return rear == front;
	}

	void add(int a) {
   
     
		if (isFull()) {
   
     
			System.out.println("已满");
			return;
		}
		array[rear] = a;  // 元素入队成功
		rear = (rear + 1) % capacity;  //计算出下一个元素的入队位置
	}

	int get() {
   
     

		if (isEmpty()) {
   
     
			System.out.println("无元素可取");
			throw new RuntimeException();
		}
		int result = array[front];  // 元素出队成功
		array[front] = 0;   // 元素值为0，表明那个位置是空的位置;
		front = (front + 1) % capacity; //  计算下一个元素的出队位置
		return result;  
	}

	void show() {
   
     

		System.out.println(Arrays.toString(array));
	}

}

1.2.2 测试代码#

public static void main(String[] args) {
   
     
    CircularQueue cq = new CircularQueue(3);
    cq.add(1);
    cq.add(2);     // 队满
    cq.show();     

    cq.add(3);     // 不可添加
    cq.show();    // 数组依然只有 1、2两元素

    System.out.println("--------------------");

    System.out.println(cq.get());	// 出队
    cq.show();		// 只剩元素1
    cq.add(3);     // 添加成功
    cq.show();     // 展示入队后的情况
    cq.add(4);     // 数组满 - 不可入队
}

运行结果