05_队列
2020-10-21 本文已影响0人
伶俐ll
队列初识
- 队列是一种特殊的线性表，只能在头尾两端进行操作
- 队尾（rear）：只能从队尾添加元素，一般叫做enQueue，入队
- 队头（front）：只能从队头移除元素，一般叫做deQueue，出队
-
先进先出的原则，First In First Out，FIFO
Snip20200914_24.png
队列的类型
- 普通队列
只能从队尾添加元素，只能从队头移除元素，先进先出，优先使用双向链表实现 - 双端队列
可以从两端添加或者删除元素，优先使用双向链表实现 - 循环队列
其实队列底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度，这个用数组实现并且优化之后的队列叫做循环队列 - 循环双端队列
可以进行两端添加、删除操作的循环队列
队列的接口设计
1. 普通队列
int size(){} // 元素的数量boolean isEmpty(){} // 是否为空void clear(){} // 清空void enQueue(E element){} // 入队E deQueue(){} // 出队E front(){} // 获取队列的头元素
2. 双端队列
int size(){} // 元素的数量boolean isEmpty(){} // 是否为空void clear(){} // 清空void enQueueRear(E element){} // 从队尾入队E deQueueFront(){} // 从队头出队void enQueueFront(E element){} // 从队头入队E deQueueRear(){} // 从队尾出队E front(){} // 获取队列的头元素E rear(){} // 获取队列的尾元素
代码实现
- 普通队列，使用双向链表实现
package Queue;
import LinkedList.LZLinkedList;
public class LZQueue<E> {
private LZLinkedList<E> list = new LZLinkedList<>();
/**
* 入队
*/
public void enQueue(E element){
list.add(element);
}
/**
* 出队
*/
public void deQueue(){
list.remove(0);
}
/**
* 获取队列的头元素
*/
public E front(){
return list.get(0);
}
/**
* 清空
*/
public void clear(){
list.clear();
}
/**
* 获取队列的长度
*/
public int size(){
return list.size();
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public String toString(){
return list.toString();
}
}
- 双端队列，使用双向链表
package Queue;
import LinkedList.LZLinkedList;
public class LZQueue2<E> {
private LZLinkedList<E> list = new LZLinkedList<>();
/**
* 从队尾入队
*/
public void enQueueRear(E element){
list.add(element);
}
/**
* 从队头出队
*/
public void deQueueFront(){
list.remove(0);
}
/**
* 从队头入队
*/
public void enQueueFront(E element){
list.add(0,element);
}
/**
* 从队尾出队
*/
public void deQueueRear(){
list.remove(list.size()-1);
}
/**
* 获取队列的头元素
*/
public E front(){
return list.get(0);
}
/**
* 获取队列的尾元素
*/
public E rear(){
return list.get(list.size()-1);
}
/**
* 清空
*/
public void clear(){
list.clear();
}
/**
* 获取队列的长度
*/
public int size(){
return list.size();
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public String toString(){
return list.toString();
}
}
- 循环队列
package Queue;
public class LZCircleQueue <E>{
/**
* 元素的数量
*/
private int size;
/**
* 第一个元素的下标
*/
private int front;
/**
* 所有的元素
*/
private E[] elements;
private static final int DEFAULT_CAPACITY = 5;
/**
* 构造函数
*/
public LZCircleQueue(){
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
/**
* 入队
* @param element
*/
public void enQueue(E element){
if (elements.length<(size + 1)){
ensureCapacity();
}
int index = index(size);
elements[index] = element;
size ++;
}
/**
* 出队
* @param
* @return
*/
public void deQueue(){
elements[front] = null;
front = index(1);
size--;
}
/**
* 获取队列的头元素
*/
public E front(){
return elements[front];
}
/**
* 清除所有元素
*/
public void clear(){
for (int i = 0;i<size;i++){
elements[index(i)] = null;
}
front = 0;
size = 0;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 扩容
*/
private void ensureCapacity(){
int oldCapacity = elements.length;
int newCapacity = oldCapacity + (oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0;i<size;i++){
newElements[i] = elements[index(i)];
}
elements = newElements;
//重置front
front = 0;
}
private int index(int index){
index += front;
return index - (index>= elements.length?elements.length:0);
// return (front + index) % elements.length;
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
for (int i = 0;i< elements.length;i++){
if (i != 0){
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
- 循环双端队列
package Queue;
public class LZCircleQueue2 <E>{
/**
* 元素的数量
*/
private int size;
/**
* 第一个元素的下标
*/
private int front;
/**
* 所有的元素
*/
private E[] elements;
private static final int DEFAULT_CAPACITY = 5;
/**
* 构造函数
*/
public LZCircleQueue2(){
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
/**
* 从队尾入队
* @param element
*/
public void enQueueRear(E element){
if (elements.length<(size + 1)){
ensureCapacity();
}
elements[index(size)] = element;
size ++;
}
/**
* 从队头出队
* @param
* @return
*/
public void deQueueFront(){
elements[front] = null;
front = index(1);
size--;
}
/**
* 从队头入队
* @param
* @return
*/
public void enQueueFront(E element){
if (elements.length<(size + 1)){
ensureCapacity();
}
front = index(-1);
elements[front] = element;
size ++;
}
/**
* 从队尾出队
* @param
* @return
*/
public void deQueueRear(){
int index = index(size-1);
elements[index] = null;
size --;
}
/**
* 获取队列的头元素
*/
public E front(){
return elements[front];
}
/**
* 获取队列的尾元素
*/
public E rear(){
return elements[index(size-1)];
}
/**
* 清除所有元素
*/
public void clear(){
for (int i = 0;i<size;i++){
elements[index(i)] = null;
}
front = 0;
size = 0;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 扩容
*/
private void ensureCapacity(){
int oldCapacity = elements.length;
int newCapacity = oldCapacity + (oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0;i<size;i++){
newElements[i] = elements[index(i)];
}
elements = newElements;
//重置front
front = 0;
}
private int index(int index){
index += front;
if (index<0){
return index + elements.length;
}
return index - (index>= elements.length?elements.length:0);
// return (front + index) % elements.length;
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
for (int i = 0;i< elements.length;i++){
if (i != 0){
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
}
复杂度
时间复杂度都是O(1)级别
