Introduction of Queue

队列作为一种抽象数据结构，遵循First-In-First-Out(FIFO)原则。

它的定义如下：

A list or collection with the restriction that insertion can be performed at one end (rear) and deletion can be performed at other end (front).

队列的操作有以下几种：

  1. Enqueue(x) 入队列
  2. Dequeue( ) 出队列（并返回删除队列的值）
  3. front( ) and rear( )
  4. IsEmpty( )

以上操作的时间复杂度均为O(1).

队列的实现

用数组实现

我们分别定义两个变量front和rear来储存队首和队尾，队列为空时令front = -1 rear = -1。

但是我们发现随着不断地Enqueue和Dequeue，队列逐渐后移，前面数组空间无法重复利用。于是我们采用循环数组，循环数组可以想象成是数组首尾相连，因此我们这样表示它的位置：

current position: i

next position: (i+1)%N

previous position: (i+N-1)%N (N表示开辟数组的长度)

代码实现

  1. IsEmpty( )
bool IsEmpty(){
    if(front == -1 && rear == -1)
        return true;
    else
        return false;
}
  1. Enqueue( x )
void Enqueue(int x){
    if((rear+1)%N == front)//rear向后一格与front重合，说明循环数组已满
        return;
    else if(IsEmpty()){
        front = 0;
        rear = 0;
        A[rear] = x;
    }
    else{
        rear = (rear + 1) % N;
        A[rear] = x;
    }
}
  1. Dequeue( )
void Dequeue(){
    if(IsEmpty())
        return;
    else if(front == rear){
        front = -1;
        rear = -1;
    }
    else{
        front = (front + 1) % N;
    }
}
  1. front( )和rear( )
int front(){
    return A[front];
}
int rear(){
    return A[rear];
}

用链表实现

Enqueue和Dequeue操作必然一个在链表头一个在链表尾，为了保证两个操作的时间复杂度都是O(1)，要设置两个指针front和rear。

代码实现

struct Node{
    int data;
    struct Node* next;
}
struct Node* front = NULL;
struct Node* front = NULL;
void Enqueue(int x){
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = NULL;
    if(front == NULL && rear == NULL){
        front = temp; rear = temp;
        return;
    }
    rear->next = temp;
    rear = temp;
}
void Dequeue(){
    struct Node* temp = front;
    if(front = NULL) return;
    if(front == rear){
        front = NULL; rear = NULL;
    }
    else{
        front = front->next;
    }
    free(temp);
}