数据结构&算法&队列

拼搏现实的明天。 2024-04-03 10:37 48阅读 0赞

**目录**

一：什么是队列？

二：队列有根据存储结构分为哪两种？

三：队列按照实现机制又分为哪两种？

四：循环队列的代码参考实现

五：队列有哪些参考实现

六：队列中常见的手撕代码

--------------------

## 一：什么是队列？ ##

队列也是一种线性数据结构，特点是与栈的特点刚刚好相反，队列时先进先出，栈式先进后出，队列的出口端式队头，入口端是队尾，所以说队列只能在队尾入队（添加）队头出队（删除）

![8015cfa7d6b7dbe972761722da93b1fe.png][]

## 二：队列有根据存储结构分为哪两种？ ##

**顺序队列：**用**顺序表**实现的叫顺序队列

![6d5385c93ef100a071bc9817d658af16.png][]

**链式队列：** 用**链表**实现的叫链式队列

![295c279b0b542e4085eedb8890dd028f.png][]

## 三：队列按照实现机制又分为哪两种？ ##

**3.1单队列：**

3.1.1单队列常见的操作

3.1.1.1入队：就是将一个新的元素加入到队列中，但是只能在队尾的位置添加元素，添加进来的下一个位置称为新 的队尾。队尾的那个位置总是指向一个空闲的位置。

![d6bd76334bbc33dea7eeb45e3554809d.png][]

3.1.2出队：就是将元素从队列中移出去，但是只能从队头取出，取出元素后，下一个元素变成新的队头。

![ac4e11db381697c3a49bfb823c623dc1.png][]

3.1.3**单队列存在问题**：就是“假溢出”如图所示当12进行进行出栈后，队头就指向了3，这时候在队尾又78又要入队，新的队尾又要指向一个新的队尾，但是没有位置让队尾指了，但是队列 里面明明还是有位置的，这就是一个“假溢出”的想象。

![e10523d7a2fb6f0e8a0b30bed7c93bd4.png][]

**3.循环队列**：循环队列就很好的解决了“假溢出”的问题。

**3.2那么循环队列实现的过程是怎样的？**

*  **步骤一**：一个队列反复的进行出队和入队后，队列只有两个元素，当一个新的元素又要加进来时

![2c22486913b30fcc5b6eeb5d92366eaa.png][]

*  **步骤二**：在列表不进行扩容的情况下，想要在进行入队操作，我们可以利用出队的位置进行扩容，可以将末尾的指针重新指向队首位置。

![a6e7767e50195c8726716832c8cc1f9e.png][]

*  **步骤三**：这样就多列的元素就循环起来了，当然队尾元素也能在队头，再有元素加进来时候就放在了队首的位置，队尾指针就像后移动了。

![1fcc2eaa2c23003a02a05821773e8905.png][]

*  **步骤四**：那么什么是时候循环队列算满呢？当（队尾下标+1）%数据长度=队头下标时说明队列已经满了，注意的是队尾指针永远指的只一个空的位置。

## 四：循环队列的代码参考实现 ##

/**
     * 	循环队列
     */
    public class CircularQueue {
    	private int[] array; // 基于数组实现
    	private int front; // 队头
    	private int rear; // 队尾
    
    	public CircularQueue(int capacity) {
    		this.array = new int[capacity];
    	}
    
    	/**
    	 * 	入队
    	 * 
    	 * @param element 入队的元素
    	 */
    	public void enQueue(int element) throws Exception {
    		if ((rear + 1) % array.length == front) {
    			throw new Exception(" 队列已满！");
    		}
    		array[rear] = element;
    		rear = (rear + 1) % array.length;
    	}
    
    	/**
    	 * 	出队
    	 * 
    	 */
    	public int deQueue() throws Exception {
    		if (rear == front) {
    			throw new Exception(" 队列已空！");
    		}
    		int deQueueElement = array[front];
    		front = (front + 1) % array.length;
    		return deQueueElement;
    	}
    
    	/**
    	 * 	输出队列
    	 */
    	public String toString() {
    		StringBuilder sb = new StringBuilder();
    		for (int i = front; i != rear; i = (i + 1) % array.length) {
    			sb.append(array[i] + "\t");
    		}
    		return sb.toString();
    	}
    
    	public static void main(String[] args) throws Exception {
    		CircularQueue myQueue = new CircularQueue(6);
    		myQueue.enQueue(3);
    		myQueue.enQueue(5);
    		myQueue.enQueue(6);
    		myQueue.enQueue(8);
    		myQueue.enQueue(1);
    		myQueue.deQueue();
    		myQueue.deQueue();
    		myQueue.deQueue();
    		myQueue.enQueue(2);
    		myQueue.enQueue(4);
    		myQueue.enQueue(9);
    		System.out.println(myQueue);
    	}
    }

## 五：队列有哪些参考实现 ##

**5.1 KTV点歌：**在唱歌时候，先点的个歌肯定先出来，后点的歌就会后出来，这也遵循了队列的特点，先进先出。

**5.2 阻塞队列：**阻塞队列其实就是在队列基础上加上阻塞的功能，当队列为空时出队操作就受到阻塞，当阻塞队列满时，在给队列添加元素时就会受到阻塞，这实现了

**5.3 线程池的线程任务队列：**当线程池中没有空闲的线程时，一个线程任务进来时候，就会被分配到线程池的任务队列中，当有空闲线城时就会从任务队列获取一个线程务并执行。当然任务队列有分为 有界队列（基于顺序表实现的）和无界队列（基于链表实现的），当任务队列为无界队列时就可以一直添加任务线程，知道资源被耗尽为止，如果为有界队列添加线城时，任务队列满了，就会执行最大线程数的操作。

## 六：队列中常见的手撕代码 ##

使用栈来实现队列的特点额和功能

实现思路：实现思路为用两个栈来实现队列的特点，一个为出队栈，一个为入队栈，一个是判断是否为空，下面是具体的实现代码。

/*
     * 	Stack栈 LIFO
     * 	Queue队列 FIFO
     * 
     * 	使用两个Stack栈实现Queue队列
     */
    public class Queue {
    	// 入队栈
    	private Stack<Integer> inStack = new Stack<>();
    	
    	// 出队栈
    	private Stack<Integer> outStack = new Stack<>();
    	
    	
    	// 入队
    	public void offer(int item) {
    		while(!outStack.empty()) {
    			inStack.push(outStack.pop());
    		}
    		
    		// 新元素入队
    		inStack.push(item);
    	}
    	
    	// 出队
    	public int poll() {
    		while(!inStack.empty()) {
    			outStack.push(inStack.pop());
    		}
    		return outStack.pop();
    	}
    	
    	// 判断是否为空
    	public boolean empty() {
    		return outStack.size() == 0 && inStack.size() == 0;
    	}
    }

[8015cfa7d6b7dbe972761722da93b1fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/05a4d246120348cb8a3ed2a9e7fd049d.png
[6d5385c93ef100a071bc9817d658af16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/638ff5ceebb443a8993d87e980511209.png
[295c279b0b542e4085eedb8890dd028f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/4e55e9ffe8f1428abbb9c52aa7760aed.png
[d6bd76334bbc33dea7eeb45e3554809d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c3bf7fa5466344cbbf2e9cc0a1f265a0.png
[ac4e11db381697c3a49bfb823c623dc1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/155b837a66c94c84a4580e9f7215fe4b.png
[e10523d7a2fb6f0e8a0b30bed7c93bd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/eecaf0fedb404cc18373e10d0d9cd103.png
[2c22486913b30fcc5b6eeb5d92366eaa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/26a4f5cbb4f54446a35990a914765301.png
[a6e7767e50195c8726716832c8cc1f9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/64bf1cc0793f4392941e5409d753cfd8.png
[1fcc2eaa2c23003a02a05821773e8905.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9b0230f6f13940968aaa48f1ed5143af.png