队列

路越走越多，可以坚持，但别固执

 

队列 更抽象的数据结构，多作为工具被程序员使用去解决实际需求。数据项先进先出。

类似栈的讲解，我们先给出代码

/*
* 代码是思想的体现，为了突出重点会忽略一些细节
* 为了体现队列是更抽象的数据结构，特意写个接口 哈哈哈
*/
public interface InterfaceQueue {
void remove();
void insert(int value);
int peek();
}

public class IntQueue implements InterfaceQueue {
private int maxSize;
private int queueArray[];
private int front;
private int tail;
private int nElements;

public IntQueue(int size) {
    maxSize = size;
    queueArray = new int[maxSize];
    front = 0;
    tail = -1;
    nElements = 0;
}

@Override
void remove() {
    int temp = queueArray[front++];
    if (front == maxSize) {
        front = 0;
    }
    nElements--;
    return temp;
}

@Override
void insert(int value) {
    if (tail == maxSize -1)
        tail = -1;
    queueArray[++tail] = value;
    nElements++;
}

@Override
int peek() {

}

public void isEmpty() {

}

public void isFull() {

}

}

下面有一个思考性的问题，我们如果不使用nElements字段，如何通过fromt,tail判空和判满

思路是：maxSize = size + 1;

虽然我们创建的数组大了1，但实际我们放到倒数第二个的时候就会设置tail = -1。这样就可以使得数组满时front != tail + 1而是 front = tail + 2。

最后，队列里面还有个不常用的双端队列：两端都可以插入和删除。这里不做介绍了。