/**
 * @author: @Akari
 * @date: 2024-01-08 12:22:10
 **/
#include <stdio.h>
#include <stdlib.h>
/**定义模块**/
#define MaxSize 100
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize]; // 用静态数组存放队列元素
    int front, rear;    // 队头指针和队尾指针
}SqQueue;

// 函数声明
void initQueue(SqQueue &Q); // 初始化
bool isEmpty(SqQueue Q);    // 判空
bool isFull(SqQueue Q);     // 判满
bool enQueue(SqQueue &Q, ElemType e);   // 入队
bool outQueue(SqQueue &Q, ElemType &e); // 出队，用 e 返回
bool getHead(SqQueue &Q, ElemType &e);  // 获取队头元素，用 e 返回
/**定义模块**/

/**测试模块**/
void printQueue(SqQueue Q);
void testQueue();
/**测试模块**/

int main(void)
{
    testQueue();
    return 0;
}

/**实现模块**/
// 初始化队列
void initQueue(SqQueue &Q){
    Q.rear = Q.front = 0;   // 初始化时，队头队尾都指向 0
}

// 判断队列是否为空
bool isEmpty(SqQueue Q){
    if ( Q.rear == Q.front ){
        return true;
    } else {
        return false;
    }
}

// 判断队列是否为满
bool isFull(SqQueue Q){
    if ( (Q.rear + 1) % MaxSize == Q.front ){   // 牺牲一个单元区分队空和队满
        return true;
    } else {
        return false;
    }
}

// 入队
bool enQueue(SqQueue &Q, ElemType e){
    // 如果队列已满直接返回
    if ( isFull(Q) ){
        return false;
    }
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MaxSize;    // 通过取余操作让整个队列循环起来
    return true;
}

// 出队
bool outQueue(SqQueue &Q, ElemType &e){
    // 如果队列为空直接返回
    if ( isEmpty(Q) ){
        return false;
    }
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

bool getHead(SqQueue &Q, ElemType &e){
    if ( isEmpty(Q) ){
        return false;
    }
    e = Q.data[Q.front];
    return true;
}
/**实现模块**/

/**测试模块**/
// 打印整个队列
void printQueue(SqQueue Q){
    printf("开始打印队列\n");
    while ( Q.front != Q.rear ){
        printf("%d ", Q.data[Q.front]);
        Q.front = (Q.front + 1) % MaxSize;  // 输出后更新下标
    }
    printf("结束打印\n");
}

// 测试
void testQueue(){
    printf("开始测试\n");
    SqQueue Q;
    initQueue(Q);
    
    if ( enQueue(Q, 1) ){
        printf("入队成功！\n");
    } else {
        printf("入队失败！\n");
    }
    if ( enQueue(Q, 2) ){
        printf("入队成功！\n");
    } else {
        printf("入队失败！\n");
    }
    if ( enQueue(Q, 3) ){
        printf("入队成功！\n");
    } else {
        printf("入队失败！\n");
    }
    printQueue(Q);
    
    int e;
    if ( outQueue(Q, e) ){
        printf("出队成功，弹出的元素是：%d\n", e);
    } else {
        printf("出队失败！");
    }
    if ( getHead(Q, e) ){
        printf("获取队头成功！队头元素是：%d\n", e);
    } else {
        printf("获取队头失败！\n");
    }
    if ( isEmpty(Q) ){
        printf("队空\n");
    } else {
        printf("队非空\n");
    }
    
    printf("结束测试\n");
}
/**测试模块**/

void Clear(){
while( !this->isEmpty() )
    {
        int val;
        this->outQueue(val);
    }
}

void Clear(){
    int val;
    Out_Queue(val);
}

~Queue(){
    this->Clear();
    delete this->pHead;
}

~Queue(){
    Clear();
    delete pHead;
}

/**
 * @author: @Akari
 * @date: 2024-01-08 20:05:37
 **/

// 带头结点版本。

#include <iostream>
using namespace std;

typedef struct Node{
    int data;
    struct Node *pNext;
}NODE, *PNODE;

class Queue{
private:
    PNODE pHead, pTail; // pHead指向无用的头结点 pHead->pNext才是指向队首元素, pTail指向队尾元素
public:
    // 构造函数
    Queue() : pHead(new NODE), pTail(pHead){    // 在构造函数中使用初始化列表
        this->pHead->pNext = nullptr;
    }
    
    // 析构函数：在对象被销毁时自动调用
    ~Queue(){
        Clear();
        delete pHead;
    }
    
    // 遍历队列元素
    void Traverse() const{
        if ( isEmpty() ){
            cout << "队列为空，无法遍历！" << endl;
            return;
        }
        
        PNODE pTemp = this->pHead->pNext;
        while ( pTemp != nullptr ){
            cout << pTemp->data << " ";
            pTemp = pTemp->pNext;
        }
        cout << endl;
    }
    
    // 判空
    bool isEmpty() const{
        // 简化返回语句
        return (this->pHead == this->pTail);
    }
    
    // 入队
    void enQueue(int val){
        PNODE pNew = new NODE;
        pNew->data = val;
        pNew->pNext = nullptr;
        
        this->pTail->pNext = pNew;  // 将pNew挂到队列尾部
        this->pTail = pNew; // 注意是尾指针上移
    }
    
    // 出队
    bool outQueue(int &val){
        if ( isEmpty() ){
            cout << "队列为空，无法出队！" << endl;
            return false;
        }
        PNODE pTemp = this->pHead->pNext;   //pHead不是要删除的队首元素，pHead->pNext所指向的元素才是要删除的元素
        val = pTemp->data;  // 保存出队元素
        this->pHead->pNext = pTemp->pNext;  // 更新首节点
        
        delete pTemp;
        pTemp = nullptr;
        
        if (nullptr == this->pHead->pNext){  // 如果队列为空
            this->pTail = this->pHead;       // 尾指针要指向无用的头结点，则将 pTail 移回 pHead
        }
        return true;
    }
    
    // 清空队列
    void Clear(){
        int val;
        outQueue(val);
    }
};

int main(void)
{
    Queue Q;
    
    for ( int i = 0; i < 5; i++ ){
        Q.enQueue(i + 1);
    }
    Q.Traverse();
    
    int val;
    if ( Q.outQueue(val) ){ // 用引用代替&val
        cout << "出队成功，出队的元素是: " << val << endl;
    } else
        cout << "出队失败！" << endl;
    Q.Traverse();
    
    Q.Clear();
    return 0;
}

/**
 * @author: @Akari
 * @date: 2024-01-08 21:55:58
 **/

// 链式队列（带头结点版本）

#include <stdio.h>
#include <stdlib.h>

/**定义模块**/
// 链表节点
typedef struct LinkNode{
    int data;
    struct LinkNode *Next;
}LinkNode;

// 队列结构
typedef struct{
    LinkNode *front, *rear; // 头指针和尾指针
}LinkQueue;

// 函数声明
void initQueue(LinkQueue &Q);   // 初始化
bool enQueue(LinkQueue &Q, int x);  // 入队
bool deQueue(LinkQueue &Q, int &x); // 出队
bool getHead(LinkQueue Q, int &x);  // 获取头元素
bool isEmpty(LinkQueue Q);      // 判空
void clearQueue(LinkQueue &Q);  // 清空
/**定义模块**/

/**实现模块**/
void initQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    if ( Q.front == nullptr ){
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    Q.front->Next = nullptr;    // 初始化时，front、rear 都指向头结点
}

bool enQueue(LinkQueue &Q, int x){
    // 判满？链式存储一般不需要判满，除非内存不足
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    if ( s == nullptr ){
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    
    s->data = x;
    s->Next = nullptr;
    Q.rear->Next = s;   // 新节点插入到 rear 之后
    Q.rear = s;     // 更新尾指针
    return true;
}

bool deQueue(LinkQueue &Q, int &x){
    if ( isEmpty(Q) ){
        return false;
    }
    
    LinkNode *p = Q.front->Next;    // 指针p 记录队头元素
    x = p->data;    // x 返回队头元素
    Q.front->Next = p->Next;    // 修改头节点的Next指针
    
    // 最后一个节点出队时
    if ( Q.rear == p ){
        Q.rear = Q.front;   // 修改rear指针
    }
    free(p);
    return true;
}

bool getHead(LinkQueue Q, int &x){
    if ( isEmpty(Q) ){
        return false;
    }
    x = Q.front->Next->data;
    return true;
}

bool isEmpty(LinkQueue Q){
    return (Q.front == Q.rear);
}

void clearQueue(LinkQueue &Q){
    int x;
    while ( deQueue(Q, x) ){
        // 依次出队，释放所有节点内存
    }
    free(Q.front);  // 释放头结点内存
}
/**实现模块**/

/**测试模块**/
// 打印函数
void printQueue(LinkQueue Q){
    printf("开始打印\n");
    
    LinkNode *temp = Q.front->Next; // 使用临时指针 temp，避免改变原视队列的状态
    
    while ( temp != Q.rear ){
        printf("%d ", temp->data);
        temp = temp->Next;
    }
    printf("\n打印完成\n");
}

// 测试函数
void testLinkQueue(){
    printf("开始测试！\n");
    LinkQueue Q;
    initQueue(Q);
    
    if ( enQueue(Q, 1) ){
        printf("入队成功 1\n");
    } else {
        printf("入队失败\n");
    }
    if ( enQueue(Q, 2) ){
        printf("入队成功 2\n");
    } else {
        printf("入队失败\n");
    }
    if ( enQueue(Q, 3) ){
        printf("入队成功 3\n");
    } else {
        printf("入队失败\n");
    }
    printQueue(Q);
    
    int x;
    if ( deQueue(Q, x) ){
        printf("出队成功，弹出的元素是 %d\n", x);
    } else {
        printf("出队失败\n");
    }
    if ( getHead(Q, x) ){
        printf("获取队头成功，队头元素是 %d\n", x);
    } else {
        printf("获取队头元素失败\n");
    }
    if ( isEmpty(Q) ){
        printf("队空\n");
    } else {
        printf("队非空\n");
    }
    
    clearQueue(Q);  // 清理队列
    printf("测试结束！\n");
}
/**测试模块**/

int main(void)
{
    testLinkQueue();
    return 0;
}