编程实现循环队列的入队、出队操作。

Question

【问题描述】
编程实现循环队列的入队、出队操作。（需要详细过程）

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;
}