隊列

定義

隊列簡稱隊，是一種只允許在表的一端進行插入操作，而在表的另一端進行刪除操作的線性表。允許插入的一端稱為隊尾，隊尾元素的位置由rear指出；允許刪除的一端稱為隊頭, 隊頭元素的位置由front指出。如下圖

隊列的基本操作

1、隊列的插入（進隊、入隊）
2、隊列的刪除（出隊、退隊）
3、測試隊列是否為空
4、檢索當前隊頭元素
5、創(chuàng)建一個空隊

隊列的順序存儲結構和操作

1、構造原理
在實際程序設計過程中，通常借助一個一維數(shù)組QUEUE[0: M–1]來描述隊列的順序存儲結構，同時,設置兩個變量front與rear分別指出當前隊頭元素與隊尾元素的位置。如下圖

C語言實現(xiàn)如下：

#define M 1000
QElemType QUEUE[M];
int front, rear;

2、初始化隊列

void INITIALQ( int front, int rear ) {
    front= –1;
    rear= –1;
}

3、測試隊列是否為空

int EMPTYQ( int front,int rear ){
    return front==rear;
}

4、插入（進隊）算法

int ADDQ( QElemType QUEUE[], int rear, int item ){
    if (rear==M-1)      /* 隊列滿，插入失敗*/
        return 0;
    else {
        QUEUE[++rear]=item;
        return 1;           /* 隊列未滿，插入成功*/
    }
}

5、刪除（出隊）算法

int DELQ( QElemType QUEUE[], int front, int rear, QElemType item ){
    if ( EMPTYQ(front,rear) )
        return 0;           /* 隊列為空，刪除失敗*/
    else {
         item=QUEUE[++front];
         return 1;          /* 隊列非空，刪除成功*/
     }
 }

隊列的鏈式存儲結構和操作

1、構造原理
隊列的鏈式存儲結構是用一個線性鏈表表示一個隊列，指針front 與rear分別指向?qū)嶋H隊頭元素與實際隊尾元素所在的鏈結點。如下圖

C語言實現(xiàn)如下

typedef struct node { 
     QElmeType data;
     struct node *link;
} QNode, *QLink;

2、初始化隊列

void INITIALQ( QLink front, QLink rear ){
    front=NULL;
    rear=NULL；
}

3、測試隊列是否為空

int EMPTYQ( QLink front ){
     return front==NULL;
}

4、插入（進隊）算法

#define LEN sizeof(QNode)
int ADDLINKQ( QLink front, QLink rear, QElemType item ){ 
     QLink p;
     if(!(p=(Qlink)malloc(LEN))        /* 申請鏈結點*/
          return 0;
      p->data=item;
      p->link=NULL;
      if (front ==NULL) 
           front=p;                /* 插入空隊的情況*/
       else
           rear->link=p;         /* 插入非空隊的情況*/
       rear=p;
       return 1; 
}

5、刪除（出隊）算法

int DELLINKQ( QLink front, QLink rear, QElemType item ){ 
    Qlink p;
    if ( EMPTYQ(front) ) 
        return 0;              /* 隊列為空，刪除失敗*/
    else {
        p=front;
        front=front->link;
        item=p->data;
        free(p); 
        return 1;             /* 隊列非空，刪除成功*/
    }
}

6、銷毀一個隊列

void DESLINKQ(QLink front, QLink rear){
    while(front){            /* 隊列非空時*/
         rear=front->link; 
         free(front);         /* 釋放一個結點空間*/
         front=rear;
     }
}