資料結構（三）——隊列及實作、循環隊列實作

一、隊列

    隊列是一種特殊的線性表，它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。在隊列這種資料結構中，最先插入的元素将是最先被删除的元素；反之最後插入的元素将最後被删除的元素，是以隊列又稱為“先進先出”（FIFO—first in first out）的線性表。  

二、操作和實作

1、結構體定義

2、初始化

3、判斷是否為空

4、取得隊列的首節點值

5、入隊列操作

6、出隊列操作

7、列印隊列的内容

1、結構體定義

#define LENGTH 100
typedef char datatype;

typedef struct queue{
    datatype data[LENGTH];
    int front;
    int rear;
}sequence_queue;
           

2、初始化

#include"queue.h"

void init_sequence_queue(sequence_queue *sq){
    sq->front = 0;
    sq->rear = 0;
}
           

3、判斷是否為空

#include"queue.h"

bool is_empty_sequence_queue(sequence_queue *sq){
    return (sq->front == sq->rear ? true:false);
}
           

4、取得隊列的首節點值

#include"queue.h"

datatype get_head(seqence_queue *sq){
    if(sq->front == sq->rear){
        printf("the queue is empty!\n");
        exit(1);
    }
    return sq->data[sq->front]; 
}
           

5、入隊列操作

#include"queue.h"

void insert_sequence_queue(sequence_queue *sq,datatype data){
    if(sq->rear == LENGTH){
        printf("the queue is full\n");
        exit(1);
    }
    sq->data[sq->rear] = data;
    sq->rear++;
}
           

6、出隊列操作

#include"queue.h"

datatype delete_sequence_queue(sequence_queue *sq){
    if(sq->rear == sq->front){
        printf("the queue is empty!\n");
        exit(1);
    }   
    sq->front++;
    return sq->data[sq->front-1];
}
           

7、列印隊列的内容

#include"queue.h"

void display_sequence_queue(sequence_queue *sq){
    if(sq->front == sq->rear){
        printf("the queue is empty!\n");
        exit(1);
    }   
    int i ;
    for(i = sq->front;i<sq->rear;i++){
        priintf("%c ",sq->data[i]);
    }
}
           

三、循環隊列

    由于隊列有元素出列，front就向後移動，是以隊列前面的空間就空了出來。為了更合理的利用空間，人們想了一個辦法：将隊列的首尾相連接配接。這樣當rear移動到LENGTH時，會再從0開始循環。那當什麼時候隊列滿呢？當rear等于front的時候。可是隊列為空的時候也是同樣的條件，那不就沒法判斷了嗎？又有人提出了這樣的想法：犧牲一個存儲空間，front前面不存資料，當rear在front前面的時候就是滿了，如圖：

    當rear在front之前時，隊列中剩餘一個空間，有 LENGTH - 1個元素，是以rear也為LENGTH - 1。這時就算是隊列滿了。于是

    滿的判斷條件應為：(rear+1)%LENGTH == front 。

    空的判斷條件為 rear == front。

是以一些操作有些變化： 

5、入隊列操作

#include"queue.h"

void insert_sequence_queue(sequence_queue *sq,datatype data){
    if((sq->rear+1)%LENGTH == sq->front){
        printf("the queue is full\n");
        exit(1);
    }
    sq->data[sq->rear] = data;
    sq->rear= (sq->rear+1)%LENGTH;
}
           

6、出隊列操作

#include"queue.h"

datatype delete_sequence_queue(sequence_queue *sq){
    if(sq->rear == sq->front){
        printf("the queue is empty!\n");
        exit(1);
    }  
    if(sq->front+1 == LENGTH){
        sq->front = (sq->front+1)%LENGTH;       //其實就是0     
        return sq->data[LENGTH-1];
    }        
    sq->front++;
    return sq->data[sq->front-1];
}
           

7、列印隊列的内容

#include"queue.h"

void display_sequence_queue(sequence_queue *sq){
    if(sq->front == sq->rear){
        printf("the queue is empty!\n");
        exit(1);
    }   
    int i ;
    for(i=sq->front;i!=sq->rear;){
        printf("%c ",sq->data[i]);            
        i=(i+1)%LENGTH;
    }
}