資料結構之隊列 C++實作

隊列很重要的一點就是入隊在隊尾進行，出隊在隊首進行，是以又把隊列稱為先進先出表。

功能實作

1.入隊功能

使用連結清單實作

#include"iostream"

using namespace std;

typedef struct student{
    int data;
    student* next;
}Node;

typedef struct linkQueue{
    Node *first, *rear;
    linkQueue() :first(NULL), rear(NULL){}
}Queue;

/*
入隊,入隊是在隊尾操作，出隊是在隊首操作
*/
Queue* insert(Queue *Q, int x){
    Node *temp;
    temp = (Node*)malloc(sizeof(Node));
    temp->data = x;
    temp->next = NULL;
    if (Q->rear == NULL){
        Q->first = temp;
        Q->rear = temp;
    }
    else{
        Q->rear->next = temp;
        Q->rear = temp;
    }
    return Q;
}

int main(){
    Queue *q = new Queue;
    insert(q, );
    insert(q, );
    insert(q, );
    cout << "隊首："<<q->first->data << endl;
    cout << "隊尾：" << q->rear->data << endl;

    system("pause");
    return ;
}
           

現象如下圖所示：

2.出隊功能

出隊在隊首操作，分三種情況：

1.隊首為空，直接傳回空；

2.隊首與隊尾相同，出隊後，隊首和隊尾為空；

3.其他，删除原隊首，将隊首指向原隊首的下一個節點。

/*
出隊
*/
Queue* dequeue(Queue* Q){
    Node *temp;
    if (Q->first == NULL){
        cout << "NULL Queue" << endl;
        return NULL;
    }
    else{
        temp = Q->first;
        if (Q->first == Q->rear){
            Q->first = NULL;
            Q->rear = NULL;
        }
        else{
            Q->first = Q->first->next;
            free(temp);
        }
        return Q;
    }
}

int main(){
    Queue *q = new Queue;
    //入隊
    cout << "入隊：" << endl; 
    enqueue(q, );
    enqueue(q, );
    enqueue(q, );
    cout << "隊首："<<q->first->data << endl;
    cout << "隊尾：" << q->rear->data << endl;

    //出隊
    cout << "出隊" << endl;
    dequeue(q);
    cout << "隊首：" << q->first->data << endl;
    cout << "隊尾：" << q->rear->data << endl;

    system("pause");
    return ;
}
           

現象如下圖所示：