本文共 8718 字，大约阅读时间需要 29 分钟。
队列（Queue），是一种先进先出的数据结构，First In First Out(FIFO),可以想象一下，就像是在排队买票，后来的人只能排在对尾，先来的人可以先买票（在对头，可以执行出去的操作）。
队列支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。所以，和栈一样，队列也是一种操作受限的线性表，但是队列比栈多出来一个操作端，可以吧队列想象成一个水管，一头进水，一头出水；栈可以想象成一个瓶子，进出都是一个口，这就是它们最直观的区别。
（1）队列分类上可以从实现的底层结构上分，一种使用数组实现，一种是使用链表实现。
- 顺序队列
- 链式队列
（2）循环队列，在容量有了限制时，可以从对尾循环回到对头（队列头为空时），充分利用空间。
（1）阻塞队列
1）在队列的基础上增加阻塞操作，就成了阻塞队列。
2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。
3）从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。
2.并发队列
1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
2）并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。
3）实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
3.线程池
在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
顺序队列通过队列头和对尾来控制队列，即使用 front 和 rear 来控制，保证 front 始终在 rear 的前面。特别注意 front 移动到中间，rear 在对尾时，再添加元素，需要整体移动数据到队列头，时间复杂度较大，O(n)。所以才有后面的循环队列。下面就来看下代码,具体的逻辑就不分析了，好好看下，应该能看懂。仅仅提供一种思路，可以进行优化或者提出其他思路，写在评论区一起讨论（Java实现，C代码文章结尾有地址，可以自己查看）
定义接口
public interface Queue{ boolean enQueque(E e); E deQueue(); E peek(); int size();}
具体实现
public class RArrayQueueimplements Queue { private static final int DEFAULT_SIZE = 10; private Object[] elements; private int head; private int tail; public RArrayQueue() { this(DEFAULT_SIZE); } public RArrayQueue(int size) { if (size < 1) { size = DEFAULT_SIZE; } elements = new Object[size + 1]; } @Override public boolean enQueque(T t) { if (isFull()) { return false; } if (tail == elements.length) { if (isEmpty()) { head = 0; tail = 0; } else { Object[] newElements = new Object[elements.length]; System.arraycopy(elements, head, newElements, 0, size()); elements = newElements; tail = size(); head = 0; } } elements[tail++] = t; return true; } @SuppressWarnings("unchecked") @Override public T deQueue() { if (isEmpty()) { return null; } return (T) elements[head++]; } @SuppressWarnings("unchecked") @Override public T peek() { if (isEmpty()) { return null; } return (T) elements[head]; } @Override public int size() { return tail - head; } public boolean isEmpty() { return head == tail; } public boolean isFull() { return size() == elements.length - 1; }
public class CircleQueueimplements Queue { private static final int DEFAULT_CAPACITY = 10; private Object[] elements; private int front = 0; private int rear = 0; public CircleQueue() { this(DEFAULT_CAPACITY); } public CircleQueue(int capacity) { if (capacity < 1) { capacity = DEFAULT_CAPACITY; } elements = new Object[capacity + 1]; } @Override public boolean enQueque(T t) { checkQueue(); if (isFull()) { return false; } elements[rear] = t; rear = (rear + 1) % elements.length; return true; } @SuppressWarnings("unchecked") @Override public T deQueue() { checkQueue(); if (isEmpty()) { return null; } T t = (T) elements[front]; elements[front] = null; front = (front + 1) % elements.length; return t; } @SuppressWarnings("unchecked") @Override public T peek() { checkQueue(); if (isEmpty()) { return null; } return (T) elements[front]; } @Override public int size() { checkQueue(); return (rear - front + elements.length) % elements.length; } public boolean isEmpty() { return front == rear; } public boolean isFull() { return (rear + 1) % elements.length == front; } private void checkQueue() { if (elements == null || elements.length < 1) { throw new NullPointerException("Queue is null!"); } if (front < 0 || front >= elements.length) { throw new IndexOutOfBoundsException("index id out of bounds!"); } if (rear < 0 || rear >= elements.length) { throw new IndexOutOfBoundsException("index id out of bounds!"); } }}
public class StackWithTwoQueue{ private static final int DEFAULT_SIZE = 10; private CircleQueue queue1; private CircleQueue queue2; private int top = -1; public StackWithTwoQueue() { this(DEFAULT_SIZE); } public StackWithTwoQueue(int capacity) { if (capacity < 1) { capacity = DEFAULT_SIZE; } queue1 = new CircleQueue<>(capacity); queue2 = new CircleQueue<>(capacity); } public boolean push(T t) { if (isFull()) { return false; } if (queue1.isEmpty() && queue2.isEmpty()) { return queue1.enQueque(t); } else if (queue1.isEmpty()) { return queue2.enQueque(t); } else { return queue1.enQueque(t); } } public T pop() { if (isEmpty()) { return null; } if (queue1.isEmpty()) { transQueue(queue1, queue2); return queue2.deQueue(); } else { transQueue(queue2, queue1); return queue1.deQueue(); } } private void transQueue(Queue enQueue, Queue deQueue) { int size = deQueue.size(); for (int i = 0; i < size - 1; i++) { enQueue.enQueque(deQueue.deQueue()); } } /** * 栈顶元素，有点麻烦，低效 * * @return */ public T peek() { if (isEmpty()) { return null; } T result = null; if (queue1.isEmpty()) { transQueue(queue1, queue2); result = queue2.deQueue(); queue1.enQueque(result); } else { transQueue(queue2, queue1); result = queue1.deQueue(); queue2.enQueque(result); } return result; } public boolean isEmpty() { return queue1.isEmpty() && queue2.isEmpty(); } public boolean isFull() { return queue1.isFull() || queue2.isFull(); } public int size() { if (queue1.isEmpty()) { return queue2.size(); } else if (queue2.isEmpty()) { return queue1.size(); } else { throw new RuntimeException("the data struct is error!"); } }}
public class QueueWithTwoStacksimplements Queue { private static final int DEFAULT_CAPACITY = 10; private int MAX_LENGTH; private RStack stack1; private RStack stack2; public QueueWithTwoStacks() { this(DEFAULT_CAPACITY); } public QueueWithTwoStacks(int capacity) { if (capacity < 1) { capacity = DEFAULT_CAPACITY; } MAX_LENGTH = capacity; stack1 = new RStack<>(capacity); stack2 = new RStack<>(capacity); } @Override public boolean enQueque(E e) { if (size() >= MAX_LENGTH || stack1.isFull()) { return false; } stack1.push(e); return true; } @Override public E deQueue() { if (size() < 1) { return null; } transStacks(); return stack2.pop(); } @Override public E peek() { if (size() < 1) { return null; } transStacks(); return stack2.peek(); } public boolean isEmpty() { return size() < 1; } public boolean isFull(){ return size() == MAX_LENGTH; } /** * 转移两个栈的元素 */ private void transStacks() { if (!stack2.isEmpty()) { return; } while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } @Override public int size() { return stack1.size() + stack2.size(); }}
测试的代码就不贴出来了，仅仅参考下，测试代码相对简单，测试的并不严谨，一些边界条件，还需要详细测试。
转载地址：http://pidws.baihongyu.com/