1. 设计一个循环队列（环形队列）

问题描述： 设计一个支持以下操作的队列：

• enqueue(int x)：将元素 x 添加到队尾。

• dequeue()：移除并返回队头元素。

• peek()：返回队头元素，但不移除它。

• isFull()：判断队列是否已满。

• isEmpty()：判断队列是否为空。

队列的大小为 k，实现一个支持高效操作的循环队列。

思路：

• 使用数组来实现队列，通过两个指针（front 和 rear）来记录队头和队尾位置。

• 循环队列的关键是使用取余操作来避免数组越界。

class CircularQueue {private int front, rear, capacity;private int[] queue;public CircularQueue(int size) {capacity = size;queue = new int[capacity];front = 0;rear = 0;}public void enqueue(int item) {if ((rear + 1) % capacity == front) {System.out.println("Queue is full");return;}queue[rear] = item;rear = (rear + 1) % capacity;}public int dequeue() {if (front == rear) {System.out.println("Queue is empty");return -1;}int item = queue[front];front = (front + 1) % capacity;return item;}public int peek() {if (front == rear) {System.out.println("Queue is empty");return -1;}return queue[front];}public boolean isEmpty() {return front == rear;}public boolean isFull() {return (rear + 1) % capacity == front;}
}

2. 用两个栈实现队列

问题描述： 用两个栈实现一个队列，支持入队和出队操作。要求实现以下接口：

• enqueue(int x)：将元素 x 添加到队列尾部。

• dequeue()：从队列头部移除并返回元素。

思路：

• 使用两个栈：stack1 用于入队，stack2 用于出队。

• 每次出队时，将 stack1 中的所有元素倒入 stack2，然后从 stack2 出队。

import java.util.Stack;class QueueWithTwoStacks {private Stack<Integer> stack1 = new Stack<>();private Stack<Integer> stack2 = new Stack<>();public void enqueue(int x) {stack1.push(x);}public int dequeue() {if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}if (stack2.isEmpty()) {System.out.println("Queue is empty");return -1;}return stack2.pop();}
}

3. 设计一个支持 max 操作的队列

问题描述： 设计一个队列，要求能够在常数时间内支持获取队列中的最大值操作。实现以下接口：

• enqueue(int x)：将元素 x 添加到队列尾部。

• dequeue()：移除并返回队列头部的元素。

• max()：返回队列中的最大值。

思路：

• 使用一个辅助队列 maxQueue 来维护当前队列中的最大值。当新元素加入时，maxQueue 中只保留大于等于该元素的元素，保证队头始终是当前最大值。

import java.util.LinkedList;class MaxQueue {private LinkedList<Integer> queue = new LinkedList<>();private LinkedList<Integer> maxQueue = new LinkedList<>();public void enqueue(int x) {queue.add(x);while (!maxQueue.isEmpty() && maxQueue.getLast() < x) {maxQueue.removeLast();}maxQueue.add(x);}public int dequeue() {if (queue.isEmpty()) {System.out.println("Queue is empty");return -1;}int val = queue.removeFirst();if (val == maxQueue.getFirst()) {maxQueue.removeFirst();}return val;}public int max() {if (maxQueue.isEmpty()) {System.out.println("Queue is empty");return -1;}return maxQueue.getFirst();}
}

4. 设计一个“按大小排序的队列”

问题描述： 设计一个队列，在入队时，保持队列中所有元素按从大到小的顺序排列。实现以下接口：

• enqueue(int x)：将元素 x 添加到队列，并保持队列按大小顺序排列。

• dequeue()：从队列头部移除并返回元素。

思路：

• 可以使用一个 PriorityQueue（优先队列），它能在入队时自动保持元素按指定顺序排列。

import java.util.PriorityQueue;class SortedQueue {private PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a); // 按降序排列public void enqueue(int x) {queue.offer(x);}public int dequeue() {if (queue.isEmpty()) {System.out.println("Queue is empty");return -1;}return queue.poll();}
}

5. 设计一个多线程安全的队列

问题描述： 设计一个线程安全的队列，要求支持以下操作：

• enqueue(int x)：将元素 x 添加到队列尾部。

• dequeue()：从队列头部移除并返回元素。

思路：

• 使用 BlockingQueue 接口及其实现类，如 ArrayBlockingQueue 或 LinkedBlockingQueue，它们提供了线程安全的队列操作。

• 如果是自定义实现，可以使用 synchronized 关键字来确保线程安全，或者使用 ReentrantLock 来实现更细粒度的锁控制。

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;class ThreadSafeQueue {private BlockingQueue<Integer> queue;public ThreadSafeQueue(int capacity) {queue = new ArrayBlockingQueue<>(capacity);}public void enqueue(int x) throws InterruptedException {queue.put(x);}public int dequeue() throws InterruptedException {return queue.take();}
}

6. 队列的逆序打印

问题描述： 给定一个队列，实现一个函数，用队列逆序打印所有元素，但不使用递归或额外的存储空间。

思路：

• 使用两个队列：queue1 用于存储元素，queue2 用于存储倒序元素。每次从 queue1 出队时，将元素加入 queue2，然后再依次出队 queue2 中的元素。

import java.util.LinkedList;
import java.util.Queue;class ReverseQueue {public void reverseQueue(Queue<Integer> queue) {Queue<Integer> tempQueue = new LinkedList<>();while (!queue.isEmpty()) {tempQueue.add(queue.poll());}while (!tempQueue.isEmpty()) {queue.add(tempQueue.poll());}}
}

7. 队列中的最大值

问题描述： 设计一个支持 insert(x) 和 getMax() 操作的队列。

• insert(x)：将元素 x 插入队列。

• getMax()：返回队列中的最大值。

思路：

• 使用双端队列（Deque）来实现，其中维护一个递减的队列来存储最大值。

import java.util.Deque;
import java.util.LinkedList;class MaxQueue {private Deque<Integer> queue = new LinkedList<>();private Deque<Integer> maxDeque = new LinkedList<>();public void insert(int x) {queue.offer(x);while (!maxDeque.isEmpty() && maxDeque.getLast() < x) {maxDeque.pollLast();}maxDeque.offer(x);}public int getMax() {if (maxDeque.isEmpty()) {System.out.println("Queue is empty");return -1;}return maxDeque.peek();}
}