数据结构【动态队列】代码实现

#include <iostream>

//链表节点
typedef struct Node
{
    int nData;
    Node *pNext;
}*PNODE;

//队列
//队列有两个指针记录数据，front、rear
typedef struct Queue
{
    PNODE pFront;
    PNODE pRear;
}*PQUEUE;

//初始化队列
void init_queue(PQUEUE pQueue);
void push_queue(PQUEUE pQueue, const int& nValue);
void pop_queue(PQUEUE pQueue);
void show_queue(const PQUEUE pQueue);
bool isEmpty_queue(const PQUEUE pQueue);


int main()
{
    Queue oQueue;
    init_queue(&oQueue);
    push_queue(&oQueue, 1);
    push_queue(&oQueue, 2);
    push_queue(&oQueue, 3);
    push_queue(&oQueue, 4);
    push_queue(&oQueue, 40);
    push_queue(&oQueue, 88);
    push_queue(&oQueue, 99);
    show_queue(&oQueue);

    pop_queue(&oQueue);
    pop_queue(&oQueue);
    pop_queue(&oQueue);
}

//初始化队列
void init_queue(PQUEUE pQueue)
{
    //初始化的时候，申请一个无效节点（不存储任何内容）
    //让队首、队尾都指向这个无效节点
    pQueue->pRear = (PNODE)malloc(sizeof(Node));
    if (nullptr == pQueue->pRear)
    {
        std::cout << "申请内存失败" << std::endl;
        exit(-1);
    }
    pQueue->pRear->pNext = nullptr;

    //队首指向队尾
    pQueue->pFront = pQueue->pRear;
}

//入队
void push_queue(PQUEUE pQueue, const int& nValue)
{
    //插入需要从队尾插入
    PNODE pNewNode = (PNODE)malloc(sizeof(Node));
    if (nullptr == pQueue->pRear)
    {
        std::cout << "申请内存失败" << std::endl;
        exit(-1);
    }
    pNewNode->pNext = nullptr;

    //由于队尾永远指向一个无效的节点，所以这里直接把数据存储到队尾节点即可
    pQueue->pRear->nData = nValue;
    //然后把申请好的无效节点与队尾连接起来，避免丢失节点
    pQueue->pRear->pNext = pNewNode;
    //让队尾指向新加的无效节点，就等于rear + 1
    pQueue->pRear = pNewNode;
}

//出队
void pop_queue(PQUEUE pQueue)
{
    if (isEmpty_queue(pQueue))
    {
        return;
    }

    //出队从队首弹出
    //先记录队首的节点
    PNODE pTempNode = pQueue->pFront;
    //队首指向队首的下一个节点，相当于front + 1
    pQueue->pFront = pQueue->pFront->pNext;

    std::cout << "弹出的元素为：" << pTempNode->nData << std::endl;

    //释放内存
    free(pTempNode);
}

//输出队列内容
void show_queue(const PQUEUE pQueue)
{
    PNODE pNode = pQueue->pFront;
    while (pNode != pQueue->pRear)
    {
        std::cout << pNode->nData << "\t";
        pNode = pNode->pNext;
    }

    //输出完以后换个行
    std::cout << "\n";
}

//队列是否为空
bool isEmpty_queue(const PQUEUE pQueue)
{
    if (pQueue->pFront == pQueue->pRear)
    {
        return true;
    }

    return false;
}