如何实现循环队列和循环栈？(语言-c++)

Question

使用循环链表实现队列和栈并实现使用附加头结点记录队列和栈中元素个数的功能。需要完整代码，并包含实验相关结果。
https://data.educoder.net/api/attachments/4748340?filesize=517
https://data.educoder.net/api/attachments/4748343?filesize=271
https://data.educoder.net/api/attachments/4748342?filesize=487
https://data.educoder.net/api/attachments/4748341?filesize=281

Answer 1

人工作答：队列是先进先出，栈是后进先出，他们可以用同样的结构体存储数据，只是在出队或者出栈时不一样。
代码中有详细的注释，运行结果如下：

代码：

#include <iostream>
using namespace std;

//定义数据类型，可根据需要调整
typedef int datatype;

#define MY_OVERFLOW (-1)
#define MY_OK (1)
#define MY_ERROR (0)

//节点结构
typedef struct _node
{
    datatype data;
    struct _node* next;
}Node;

typedef struct _dataStruct
{
    int maxLen;  //链表总长度
    Node* head;  //链表头
    Node* front; //当前数据头节点
    Node* last;  //当前数据尾节点
}CQueue, CStack;

/**   循环链表实现队列  **/
//1.初始化，队列的初始采用尾插法创建链表
void initQueue(CQueue& q,int maxSize = 100)
{
    q.maxLen = maxSize;
    q.head = new Node; //附加头节点
    q.head->data = 0; //当前实际存储的数据个数
    q.head->next = 0;

    Node* p = 0, * t;
    t = q.head;
    //创建maxSize个节点
    for (int i = 0; i < maxSize;i++)
    {
        p = new Node;
        p->next = 0;
        t->next = p;
        t = p;
    }
    
    p->next = q.head;        //尾节点连接头节点
    q.front = q.head->next;  //初始化当前数据节点的头部
    q.last = q.front;
}

//2.入队
int pushQueue(CQueue& q, datatype d)
{
    if (q.head->data == q.maxLen)
        return MY_OVERFLOW;
    else
    {
        q.last->data = d;
        q.last = q.last->next;
        if (q.last == q.head) //跳过附加头节点
            q.last = q.head->next;
            
        q.head->data += 1; //个数+1
        return MY_OK;
    }
}

//3.出队
int popQueue(CQueue& q, datatype& d)
{
    if (q.head->data == 0)
        return MY_ERROR;
    else
    {
        d = q.front->data;
        q.front = q.front->next;
        if (q.front == q.head) //如果下一个节点是附加头节点，跳过
            q.front = q.front->next; 
        q.head->data -= 1; //个数-1
        return MY_OK;
    }
}

//4.获取队列元素个数
int getQueueLength(CQueue& q)
{
    return q.head->data;
}
/**   循环链表实现栈  **/
//1.初始化
void initStack(CStack& s, int maxSize = 100)
{
    s.maxLen = maxSize;
    s.head = new Node; //附加头节点
    s.head->data = 0; //当前实际存储的数据个数
    s.head->next = 0;

    Node* p = 0, * t;
    t = s.head;
    //创建maxSize个节点
    for (int i = 0; i < maxSize; i++)
    {
        p = new Node;
        p->next = 0;
        t->next = p;
        t = p;
    }

    p->next = s.head;        //尾节点连接头节点
    s.front = s.head->next;  //初始化当前数据节点的头部
    s.last = s.front;
}

//2.入栈
int pushStack(CStack& s, datatype d)
{
    if (s.head->data == s.maxLen)
        return MY_OVERFLOW;
    else
    {
        s.last->data = d;
        s.last = s.last->next;
        if (s.last == s.head) //跳过附加头节点
            s.last = s.head->next;
            
        s.head->data += 1; //个数+1
        return MY_OK;
    }
}
//3.出栈
int popStack(CStack& s, datatype& d)
{
    if (s.head->data == 0)
        return MY_ERROR;
    else
    {
        Node* pre,*pp=0;

        pre = s.front; //当前节点
        while (pre->next != s.last)
        {
            if (pre->next == s.head)
                pp = pre; //记录链表的最后一个节点
            pre = pre->next;
        }

        if (pre == s.head) //跳过附加节点
        {
            pre = pp;
        }

        d = pre->data; //后进先出
        s.last = pre; //尾节点前移
        
        s.head->data -= 1; //个数-1
        return MY_OK;
    }
}

//4.获取队列长度
int getStackLength(CStack& s)
{
    return s.head->data;
}

//测试
int main()
{
    CQueue que; //队列
    CStack sta; //栈

    initQueue(que); //初始化队列
    initStack(sta); //初始化栈
    int n, t;
    cout << "请输入入队元素个数：";
    cin >> n;
    cout << "请输入" << n << "个整数入队：" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        pushQueue(que, t); //入队
    }
    cout << "队列当前元素个数：" << getQueueLength(que) << endl;
    cout << "队列元素依次出队：" << endl;
    while (getQueueLength(que) > 0)
    {
        popQueue(que, t);
        cout << t << " ";
    }
    cout << endl;


    cout << "请输入栈元素个数：";
    cin >> n;
    cout << "请输入" << n << "个整数入栈：" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        pushStack(sta, t); //入栈
    }
    cout << "栈当前元素个数：" << getStackLength(sta) << endl;
    cout << "栈元素依次出栈：" << endl;
    while (getStackLength(sta) > 0)
    {
        popStack(sta, t);
        cout << t << " ";
    }
    cout << endl;
    return 0;
}