队列
队列同样是一种存储数据的线性表，只允许在队尾插入元素，在队首删除元素，是一种先进先出（FIFO）的线性表。
-
专有名词概念：
- 入队（EnQueue）：在队列中插入一个元素
- 出队（DeQueue）：在队列中删除一个元素
- 下溢（underflow）：对一个空队列执行出队操作
- 溢出（overflow）：对一个满队列执行入队操作
-
应用
- 操作系统对于相同优先级的任务进行的顺序调度任务
- 显示世界中的队列
- 多道程序设计
- 异步数据传输
-
实现
- 基于简单循环数组的实现方法
- 基于动态循环数组的实现方法
- 基于链表的实现方法
采用循环数组可以有效减少空间的浪费。
元素个数=rear-front+n(rear不等于front时)
//循环数组实现队列
public class ArrayQueue {
private int front;
private int rear;
private int capacity;
private int[] array;
private ArrayQueue(int size) {
capacity = size;
front = -1;
rear = -1;
array = new int[size];
}
public static ArrayQueue createQueue(int size) {
return new ArrayQueue[size];
}
public boolean isEmpty() {
return front==-1;
}
public boolean isFull() {
return (rear+1)%capacity == front;
}
public int getQueueSize() {
return (capacity-front+rear+1)%capacity;
}
public void enQueue(int data) {
if(isFull()){
throw new QueueOverflowException("Queue Overflow");
} else {
rear = (rear+1)%capacity;
array[rear] = data;
if(front == -1) {
front = rear;
}
}
}
public int deQueue() {
int data = null;
if(isEmpty()) {
throw new EmptyQueueException("Queue Empty");
} else {
data = array[front];
if(front==rear) {
front =rear - 1;
} else {
front = (front+1)%capacity;
}
}
return data;
}
}
//基于链表实现的队列
public class LLQueue {
private LLNode frontNode;
private LLNode rearNode;
private LLQueue() {
this.frontNode = null;
this.rearNode = null;
}
public static LLQueue createQueue() {
return new LLQueue();
}
public boolean isEmpty() {
return frontNode == null;
}
public void enQueue(int data) {
LLNode newNode = new LLNode(data);
if(rearNode != null) {
rearNode.setNext(newNode);
}
rearNode = newNode;
if(frontNode == null) {
frontNode = rearNode;
}
}
public int deQueue() {
int data = null;
if(isEmpty()) {
throw new EmptyQueueException("Queue Empty");
} else {
data = frontNode.getData();//从队头删除元素
frontNode = frontNode.getNext();
}
return data;
}
}
问题
-
逆置队列元素？
通过一个栈作为缓存
public class QueueReversal { public static Queue reverseQueue(Queue queue) { Stack stack = new LLStack(); while(!queue.isEmpty()) { stack.push(queue.deQueue());//栈中存储队头删除的元素 } while(!stack.isEmpty()) { queue.enQueue(stack.pop()); } return queue; } } -
两个栈实现一个队列？
入队：将一个元素压进第一个栈S1中。
出队：当S2为空时，将S1中元素放进S2中，然后将S2的栈顶元素弹出；当S2不为空时，直接将S2的栈顶元素弹出。
-
两个队列实现一个栈？
入栈：当Q1为空时，对Q2执行入队操作；当Q1不为空，对Q1执行入队操作
出栈：当Q1为非空时，从Q1移n-1个元素到Q2中，对Q1最后一个元素执行出队操作；当Q2为非空时，从Q2移n-1个元素到Q1中，对Q2最后一个元素执行出队操作。
-
给定一个整数栈，检查栈中每队相邻数字是否是连续的，如果栈中元素为奇数，则忽略栈顶元素。
public static boolean checkStackPairwiseOrder(Stack<Integer> s) { Queue<Integer> q = new LinkedList<Integer>(); boolean pairwiseOrdered = true; while(!s.isEmpty()) { q.add(s.pop()); } while(!q.isEmpty()) { s.push(q.remove());//逆置了整个栈中元素 } //判断相邻元素是否连续的 while(!s.isEmpty()) { int n = s.pop(); q.add(n); if(!s.isEmpty()) { int m = s.pop(); q.add(m); if(Math.abs(n-m)!=1) { pairwiseOrdered = false; } } } //恢复栈中数字和顺序 while(!q.isEmpty()) { s.push(q.remove()); } return pairwiseOrdered; } -
给定一个证书队列，把队列中前半部分和后半部分的元素相互交叉，完成队列中元素的重新排列。
可以采用一个栈或队列作为中数据转换
public void interLeavingQueue(Queue<Integer> q) { if(q.size() % 2 != 0) throw new IllegalArgumentException(); Stack<Integer> s = new ArrayStack<Integer>(); int halfSize = q.size() / 2; //倒置队列前半部分的元素 for(int i = 0; i < halfSize; i++) { s.push(q.dequeue()); } while(!s.isEmpty()) { q.enqueue(s.pop());//前半部分倒过来,并放置到后半部分位置 } for(int i = 0; i < halfSize; i++) { q.enqueue(q.dequeue());//恢复位置 } for(int i = 0; i < halfSize; i++) { s.push(q.dequeue());//将倒过来的前半部分一次放入栈中 } //交叉排列数据 while(!s.isEmpty()) { q.enqueue(s.pop()); q.enqueue(q.dequeue()); } }
