[数据结构与算法] 从真题中理解循环队列

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 从真题中理解循环队列 -> 正文阅读

[数据结构与算法]从真题中理解循环队列

从真题中理解循环队列

题目概述

如果希望循环队列中的元素都能得到利用，则可设置一个标志域tag，并以tag值为0或1来区分尾指针和头指针相同时的队列状态是“空”还是“满”，其数据结构如下:

typedef struct {
	ElemType *elem;
	int front;
	int rear;
	int tag;
	int maxSize;
}CTagQueue;

1）写出此结构对应的队空判断条件表达式。
2）试编写与此结构对应的入队列算法 Status EnCQueue(CTagQueue &Q，ElemType x)，插入元素为x，其返回值为 ERROR或OK.

题目解答

1）

(Q.tag==0)&&(Q.rear==Q.front)

2）

Status EnCQueue(CTagQueue &Q,QElemType x)
{
    if((Q.tag==1)&&(Q.rear==Q.front))//队满
        return ERROR;
    Q.elem[Q.rear]=x;//新元素插入队尾
    Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针加1
    if(Q.tag==0) Q.tag=1;//标志改1,表示队列非空
    return OK;
}

完整代码

#include<stdlib.h>
#include<stdio.h>
#define MAXQSIZE 100
#define OK 1
#define ERROR -1
#define OVERFLOW -1
typedef int QElemType;
typedef int Status;
typedef struct
{
    QElemType *elem;
    int front;
    int rear;
    int tag;
    int maxSize;
}CTagQueue;

Status InitQueue(CTagQueue &Q)
{
    Q.elem=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
    if(!Q.elem)
        exit(OVERFLOW);//存储分配失败
    Q.front=Q.rear=0;//头尾指针置为0
    Q.tag=0;//标志初始化为0,队列为空
    return OK;
}
int QueuenLength(CTagQueue Q)
{
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;//返回Q的元素个数,即队列长度 
}

//入队
Status EnCQueue(CTagQueue &Q,QElemType x)
{
    if((Q.tag==1)&&(Q.rear==Q.front))//队满
        return ERROR;
    Q.elem[Q.rear]=x;//新元素插入队尾
    Q.rear=(Q.rear+1)%MAXQSIZE;//队尾指针加1
    if(Q.tag==0) Q.tag=1;//标志改1,表示队列非空
    return OK;
}
//出队
Status DeQueue(CTagQueue &Q,QElemType &e)
{
    if((Q.tag==0)&&(Q.rear==Q.front))//队空
        return ERROR;
    e=Q.elem[Q.front];//保存队头元素
    Q.front=(Q.front+1)%MAXQSIZE;//对头指针加1
    if(Q.tag==1) Q.tag=0;//标志改0,表示队列非满
    return OK;
}
//打印队列
void PrintQueue(CTagQueue Q)
{
    while (((Q.rear+1)%MAXQSIZE==Q.front)||Q.front!=Q.rear)
    {
        printf("%d ",Q.elem[Q.front]);
        Q.front++;
    }
    printf("\n");
}


int main()
{
    CTagQueue Q;
    QElemType m_e;
    InitQueue(Q);
    printf("入队顺序:\n");
    for(int i=0;i<10;i++)
        EnCQueue(Q,i);
    for(int i=0;i<10;i++)
        printf("%d ",Q.elem[i]);
    printf("\n");
    printf("出队顺序:\n");
    for(int i=0;i<10;i++)
    {
        DeQueue(Q,m_e);
        printf("%d ",m_e);
    }
    printf("\n");
    system("pause");
    return 0;
}