大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(二）:線性結(jié)構(gòu)
大師兄的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記(四）:樹結(jié)構(gòu)

一鞭铆、什么是隊(duì)列(Queue)

• 隊(duì)列是具有一定操作約束的線性表。
• 只在一端(隊(duì)尾)插入/入隊(duì)列，在另一端(隊(duì)頭)刪除/出隊(duì)列。
• 先入先出：First In First OUT (FIFO)。

二、隊(duì)列的抽象數(shù)據(jù)類型描述

• 數(shù)據(jù)對象集: 一個(gè)有0個(gè)或多個(gè)元素的有窮線性表。
• 操作集: 長度為MaxSize的隊(duì)列,隊(duì)列元素

三蚁滋、隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)

• 隊(duì)列的順序存儲(chǔ)通常由一個(gè)一維數(shù)組宿接、一個(gè)記錄隊(duì)列頭元素位置的變量front、一個(gè)記錄隊(duì)列尾元素位置的變量rear組成辕录。
  

#ifndef QUEUE_H
#define QUEUE_H
typedef int DataType;

const int MaxSize = 100;

class Queue
{
public:
    Queue() {};                             //生成長度為MaxSize的空隊(duì)列
    bool IsFull();      //判斷隊(duì)列Q是否已滿
    void AddQ(DataType item);   //將數(shù)據(jù)元素item插入隊(duì)列Q中
    bool IsEmpty();                 //判斷隊(duì)列Q是否為空
    DataType DeleteQ();             //將隊(duì)頭數(shù)據(jù)元素從隊(duì)列中刪除并返回
private:
    DataType data[MaxSize];
    int front;
    int rear;
};
#endif

#include <iostream>
#include "Queue.h"
using namespace std;

bool Queue::IsFull()
{
    //判斷隊(duì)列Q是否已滿
    if ((rear + 1) % MaxSize == front) {
        return true;
    }
    return false;
}

bool Queue::IsEmpty()
{
    //判斷隊(duì)列Q是否為空
    if (rear == front)
    {
        return true;
    }
    return false;
}

void Queue::AddQ(DataType item)
{
    //將數(shù)據(jù)元素item插入隊(duì)列Q中
    if (IsFull())
    {
        printf("Queue is full!");
        return;
    }
    rear = (rear + 1) % MaxSize;
    data[rear] = item;
}

DataType Queue::DeleteQ()
{
    //將隊(duì)頭數(shù)據(jù)元素從隊(duì)列中刪除并返回
    if (IsEmpty())
    {
        printf("Queue is empty!");
        return 0;
    }
    else {
        front = (front + 1) % MaxSize;
        return data[front];
    }
}

四睦霎、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)

• 用一個(gè)單鏈表實(shí)現(xiàn)，鏈表頭作為front走诞，鏈表末尾作為rear副女。

  
  

#ifndef QUEUE_H
#define QUEUE_H
typedef int DataType;

typedef struct Node {
    //鏈表數(shù)據(jù)結(jié)構(gòu)
    DataType Data;
    struct Node *Next;
}QNode;

class Queue
{
public:
    Queue() {};                 //構(gòu)造函數(shù)
    void AddQ(DataType item);   //將數(shù)據(jù)元素item插入隊(duì)列Q中
    bool IsEmpty();             //判斷隊(duì)列Q是否為空
    DataType DeleteQ();         //將隊(duì)頭數(shù)據(jù)元素從隊(duì)列中刪除并返回
private:
    //鏈表隊(duì)列結(jié)構(gòu)
    QNode *front;
    QNode *rear;
};
#endif

#include <iostream>
#include "Queue.h"
using namespace std;

bool Queue::IsEmpty()
{
    //判斷隊(duì)列Q是否為空
    if (front==nullptr)
    {
        return true;
    }
    return false;
}

void Queue::AddQ(DataType item)
{
    //將數(shù)據(jù)元素item插入鏈表尾部
    QNode* RearCell = new QNode;
    RearCell->Data = item;
    RearCell->Next = nullptr;

    if (IsEmpty())
        rear = front = RearCell;
    else  
        rear->Next = RearCell;
        rear = RearCell;
}   

DataType Queue::DeleteQ()
{
    //將隊(duì)頭數(shù)據(jù)元素從隊(duì)列中刪除并返回
    QNode *FrontCell;
    DataType FrontElem;

    if (IsEmpty())
    {
        printf("Queue is empty!");
        return 0;
    }
    FrontCell = front;
    if (front == rear)
        //如果只有一個(gè)元素,表頭為空
        front = nullptr;
    else
        //如果超過一個(gè)元素，則指向上一個(gè)元素并釋放當(dāng)前元素空間
        front = front->Next;
    FrontElem = FrontCell->Data;
    free(FrontCell);
    return FrontElem;
}