官方彩票投注

隊列的基本操作-隊列的鏈式存儲結構(帶圖詳細)

什么是隊列?        

        隊列是一種特殊的線性表,特殊之處在于它只允許在表的前端(front)進行刪除操作,而在表的后端(rear)進行插入操作,和棧一樣,隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾,進行刪除操作的端稱為隊頭。隊列中沒有元素時,稱為空隊列。

        鏈式隊列是用單鏈表的形式來表示隊列,但是要符合隊列“尾進頭出”的規則

鏈式隊列的構建:

鏈式隊列=單鏈表+隊列

如下代碼是對一個隊列的鏈式存儲的定義:首先定義一個構成單鏈表基本單元的結點,然后定義由指向結點的頭指針、指向結點的尾指針和表示隊列長度的變量組成的隊列

//鏈式隊列    鏈式結構+隊列
//鏈式結構體 =單鏈表的基本單元:結點 
struct Node{
    int data;//數據域 
    struct Node* next;     //指針域 
}; 
//隊列結構體=頭指針+尾指針+隊列大小 
 struct Queue{
    struct Node* front;//指向結點的頭指針 
    struct Node* rear;//指向結點的尾指針 
    int queueSize; //隊列大小/長度 
}; 

創建結點:

官方彩票投注隊列是由一個一個結點通過指針鏈接起來的

//創建結點
struct Node* createNode(int data){
    struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->next=NULL;
    newNode->data=data;
    return newNode;    
}; 

隊列的初始化:

首先使用malloc函數為隊列分配一塊內存,初始狀態隊列的頭指針和尾指針在一起都為空(不帶頭結點),然后設置隊列的大小為0。這樣隊列的初始化操作就完成了。

//隊列初始化
struct Queue* createQueue(){
    struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));//分配內存空間 
    queue->front=queue->rear=NULL;//頭指針和尾指針在一起為空 
    queue->queueSize=0;//隊列大小為0 
    return queue;
} 

入隊操作:

準備工作:首先創建入隊函數push()傳入兩個參數,一個是需要插入那個隊列另一個是需要插入的數據。然后調用createNode()函數創建一個新的結點,保存插入的數據。

準備工作完成后:先判斷隊列是否是空隊列,如果為空隊列直接將front和rear指針指向這個新建結點即可,若不為空,則將尾指針的下一個位置指向新建結點,然后再將尾指針修改為這個新建結點。(這個地方我個人感覺比較難懂,我的理解是 先告訴這個新建結點在哪里,然后在移動rear指針到新建結點把他設為隊尾)。

最后別忘記queueSize自增,表示隊列長度的增加。

 

void push(struct Queue* queue,int data){
    struct Node* newNode=createNode(data);
    if(queue->queueSize==0)
        queue->front=newNode;
        else
        queue->rear->next=newNode;
        queue->rear=newNode;
        queue->queueSize++;
    
} 

 獲取對頭元素:

官方彩票投注首先判斷隊列queueSize是否為0如果為0說明隊列為空,如果不為空直接返回隊列頭指針的data值。

//獲取對頭元素
int queryFront(struct Queue* queue) {
    if(queue->queueSize==0){
        printf("隊列為空無法獲取對頭元素");
        printf("\n"); 
        return -1; 
    }
    return queue->front->data;
}

判斷隊列是否為空:

 代碼很簡單就不一一解釋了。

//判斷隊列是否為空
int empty(struct Queue* queue){
    if(queue->queueSize==0)
    return 0;
    else
    return 1;
} 

出隊操作:

新建頭結點指針指向隊列front指針所指結點的下一個位置(因為出隊操作是在對頭進行的),然后釋放原來的隊頭結點,最后設置這個新的頭結點為隊頭。最后隊列的大小減1.

 

 

//出隊操作
void pop (struct Queue* queue){
    if(queue->queueSize==0){

    printf("隊列為空不能出隊");
    exit(0);
     }else{
         struct Node* newFrontNode=queue->front->next;
         free(queue->front); 
         queue->front=newFrontNode;
         queue->queueSize--;
     }
}

 最后附上完整代碼:

#include <stdio.h>
#include <stdlib.h>
//鏈式隊列    鏈式結構+隊列
//鏈式結構體 =單鏈表的基本單元:結點 
struct Node{
    int data;//數據域 
    struct Node* next;     //指針域 
}; 
//隊列結構體=頭指針+尾指針+隊列大小 
 struct Queue{
    struct Node* front;//指向結點的頭指針 
    struct Node* rear;//指向結點的尾指針 
    int queueSize; //隊列大小/長度 
}; 
//創建結點
struct Node* createNode(int data){
    struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->next=NULL;
    newNode->data=data;
    return newNode;    
}; 
//隊列初始化
struct Queue* createQueue(){
    struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));//分配內存空間 
    queue->front=queue->rear=NULL;//頭指針和尾指針在一起為空 
    queue->queueSize=0;//隊列大小為0 
    return queue;
} 
//入隊
void push(struct Queue* queue,int data){
    struct Node* newNode=createNode(data);
    if(queue->queueSize==0)
        queue->front=newNode;
        else
        queue->rear->next=newNode;
        queue->rear=newNode;
        queue->queueSize++;
    
} 
//獲取對頭元素
int queryFront(struct Queue* queue) {
    if(queue->queueSize==0){
        printf("隊列為空無法獲取對頭元素");
        printf("\n"); 
        return -1; 
    }
    return queue->front->data;
}
//判斷隊列是否為空
int empty(struct Queue* queue){
    if(queue->queueSize==0)
    return 0;
    else
    return 1;
} 
//出隊操作
void pop (struct Queue* queue){
    if(queue->queueSize==0){

    printf("隊列為空不能出隊");
    exit(0);
     }else{
         struct Node* newFrontNode=queue->front->next;
         free(queue->front); 
         queue->front=newFrontNode;
         queue->queueSize--;
     }
}
int main(){
    struct Queue* myQueue=createQueue();
    push(myQueue,1);
    push(myQueue,2);
    push(myQueue,3);
    while(empty(myQueue)){
        printf("%d\t",queryFront(myQueue));
        pop(myQueue);
    }
    printf("\n");
    system("pause");
return 0;
}
 
posted @ 2019-12-20 15:31  陳曉晨不吃香菜  閱讀(...)  評論(...)    收藏