编程实现循环队列的入队、出队操作。
【问题描述】
编程实现循环队列的入队、出队操作。（需要详细过程）
循环链表实现队列和堆栈的代码（堆栈不需要的话可以删掉），代码中有详细注释。运行结果：
代码：
#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;
}
#include <iostream>
using namespace std;
#define ERROR -1
#define OK 1
typedef int QElemType;
typedef int Status;
//循环队列的存储结构
#define MAXQSIZE 100 //最大队列长度
typedef struct
{
QElemType *base; //用于动态分配存储空间
int front; //队头索引
int rear; //队尾索引
} SqQueue;
//初始化
void InitQueue (SqQueue &Q)
{
//构造一个空队列
Q.base =new QElemType[MAXQSIZE];
Q.front=Q.rear=0;
}
//销毁队列
void DestroyQueue(SqQueue &Q)
{
if(Q.base)
free(Q.base);
Q.base = NULL;
Q.front = Q.rear = 0;
}
//清空队列
void ClearQueue(SqQueue &Q)
{
Q.front=Q.rear=0;
}
//求长度
int QueueLength (SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
//判空
bool QueueEmpty (SqQueue Q)
{
return (Q.front==Q.rear);
}
//求队头元素
Status GetHead (SqQueue Q, QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
return OK;
}
//循环队列入队
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear = (Q.rear+1) % MAXQSIZE;
return OK;
}
//循环队列出队
Status DeQueue (SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1) % MAXQSIZE;
return OK;
}
//遍历使队列显示
void DisplayQueue(SqQueue Q)
{
int i=Q.front;
while(Q.front!=Q.rear && (i+MAXQSIZE) % MAXQSIZE != Q.rear)
{
cout<<Q.base[i]<<endl;
i++;
}
}
void show_help()
{
cout<<"******* Data Structure ******"<<endl;
cout<<"1----清空循环队列"<<endl;
cout<<"2----判断循环队列是否为空"<<endl;
cout<<"3----求循环队列长度"<<endl;
cout<<"4----取队头元素"<<endl;
cout<<"5----入队"<<endl;
cout<<"6----出队"<<endl;
cout<<"7----显示队列"<<endl;
cout<<" 退出，输入0"<<endl;
}
int main()
{
char operate_code;
show_help();
SqQueue Q;
InitQueue(Q);
QElemType e;
int i;
while(1)
{
cout<<"请输入操作代码:";
cin>>operate_code;
if(operate_code=='1')
{
cout<<"The queue has been cleared."<<endl;
ClearQueue(Q);
}
else if (operate_code=='2')
{
if(QueueEmpty(Q))
cout<<"The queue is empty."<<endl;
else
cout<<"The queue is not empty."<<endl;
}
else if (operate_code=='3')
{
cout<<"The length of queue is:"<<QueueLength(Q)<<endl;
}
else if (operate_code=='4')
{
cout<<"队头元素为："<<endl;
if(GetHead(Q,e) == 1) cout<<e<<endl;
else cout <<"error"<<endl;
}
else if (operate_code=='5')
{
cout<<"请输入你想要入队的数："<<endl;
cin>>e;
EnQueue(Q,e);
}
else if (operate_code=='6')
{
cout<<"出队元素为："<<endl;
if(DeQueue(Q,e)) cout<<e<<endl;
}
else if (operate_code=='7')
{
cout<<"The contents of the queue are:"<<endl;
DisplayQueue(Q);
}
else if (operate_code=='0')
{
break;
}
else
{
cout<<"\n操作码错误！！！"<<endl;
show_help();
}
}
//调用销毁栈函数
DestroyQueue(Q);
return 0;
}
#ifndef __QUEUE_H__
#define __QUEUE_H__
#define MAX 8
typedef int datatype;
typedef struct
{
datatype data[MAX];
int front; //队头
int tail; //队尾
}seQueue;
//创建
seQueue *create();
//判空
int empty(seQueue *S);
//判满
int full(seQueue *S);
//入队
int push(seQueue *S,datatype e);
//遍历
void show(seQueue *S);
//出队
int pop(seQueue *S);
//销毁
void destroy(seQueue *S);
#endif
#include<stdio.h>
#include<stdlib.h>
#include"queue.h"
//创建
seQueue *create()
{
seQueue *S = (seQueue *)malloc(sizeof(seQueue));
if(S == NULL)
{
printf("创建失败\n");
return NULL;
}
//初始化
S->front = 0;
S->tail = 0;
printf("创建成功\n");
return S;
}
//判空
int empty(seQueue *S)
{
return S->front==S->tail? 1:0; //1表示空，0表示非空
}
//判满
int full(seQueue *S)
{
return (S->tail+1)%MAX==S->front?1:0;
}
//入队
int push(seQueue *S,datatype e)
{
//判断逻辑
if(S == NULL || full(S))
{
printf("入队失败\n");
return -1;
}
S->data[S->tail] = e;
//队尾后移
S->tail = (S->tail+1)%MAX;
printf("入队成功\n");
return 0;
}
//遍历
void show(seQueue *S)
{
//判断逻辑
if(S == NULL || empty(S))
{
printf("遍历失败\n");
return;
}
int len;
printf("队头到队尾元素分别是：");
for(int i=S->front;i != S->tail;i=(i+1)%MAX)
{
printf("%d\t",S->data[i]);
}
putchar(10);
len=(S->tail+MAX-S->front)%MAX;
printf("队伍长度为：%d\n",len);
}
//出队
int pop(seQueue *S)
{
if(S == NULL || empty(S))
{
printf("出队失败\n");
return -1;
}
printf("%d出队成功\n",S->data[S->front]);
S->front = (S->front+1)%MAX;
return 0;
}
//销毁
void destroy(seQueue *S)
{
if(S != NULL)
{
free(S);
S=NULL;
}
printf("销毁成功\n");
}
#include<stdio.h>
#include<stdlib.h>
#include"queue.h"
int main(int argc, const char *argv[])
{
//创建
seQueue *S = create();
if(S == NULL)
{
return -1;
}
//调用入队
push(S,9);
push(S,6);
push(S,8);
push(S,7);
push(S,4);
push(S,5);
//遍历
show(S);
//出队
pop(S);
pop(S);
show(S);
//销毁
destroy(S);
S = NULL;
return 0;
}
https://blog.csdn.net/qq_60071225/article/details/125929446
- 你看下这篇博客吧, 应该有用👉 ：链式队列，队列篇（链式队列的出队入队操作）
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632