一、队列的基本操作

  • 初始化队列:InitQueue(Q)
    操作前提:Q为未初始化的队列。
    操作结果:将Q初始化为一个空队列。
  • 判断队列是否为空:IsEmpty(Q)
    操作前提:队列Q已经存在。
    操作结果:若队列为空则返回1,否则返回0。
  • 判断队列是否已满:IsFull(Q)
    操作前提:队列Q已经存在。
    操作结果:若队列为满则返回1,否则返回0。
  • 入队操作:EnterQueue(Q,data)
    操作前提:队列Q已经存在。
    操作结果:在队列Q的队尾插入data。
  • 出队操作:DeleteQueue(Q,&data)
    操作前提:队列Q已经存在且非空。
    操作结果:将队列Q的队头元素出队,并使用data带回出队元素的值。
  • 取队首元素:GetHead(Q,&data)
    操作前提:队列Q已经存在且非空。
    操作结果:若队列为空则返回1,否则返回0。
  • 清空队列:ClearQueue(&Q)
    操作前提:队列Q已经存在。
    操作结果:将Q置为空队列。

二、队列的顺序结构

设立一个队首指针front ,一个队尾指针rear ,分别指向队首和队尾元素。
◆ 初始化:front=rear=0。
◆ 队列为空:front=rear。
◆ 队满:rear=MaxSize。
◆ 入队:将新元素插入rear所指的位置,然后rear加1。
◆ 出队:删去front所指的元素,然后加1并返回被删元素。
◆ 取队首元素:返回fornt指向的元素值

//当不需要修改队列中的元素时,建议不要直接用指针形参操作 
#include <stdio.h>
#include <assert.h> //使用断言:assert(Q)

#define MaxSize 10  //队列的最大容量

typedef int elemtype;  //队列中元素类型

typedef struct QueueType
{
    elemtype data[MaxSize];
    int fornt;   //队头指针
    int rear;    //队尾指针
}Queue;

//队列初始化,将队列初始化为空队列
void InitQueue(Queue *Q)
{
    Q->fornt = Q->rear = 0;  //把对头和队尾指针同时置0
 }
 
//另一种队列初始化。须在main()中使用:CirQueue *SCQ=InitCirQueue();但感觉多余 
/* 
CirQueue *InitCirQueue()
{
    CirQueue *Q = (CirQueue *)malloc(sizeof(CirQueue));
    Q->fornt = Q->rear = 0;
    return Q;
}
*/

//判断队列为空
int IsEmpty(Queue Q)
{
    if (Q.fornt == Q.rear)
    {
        return 1;
    }
    return 0;
}

//判断队列是否为满
int IsFull(Queue Q)
{
    if (Q.rear == MaxSize) 
    {
        return 1;
    }
    return 0;
}

//入队,将x插入到队列Q中
int EnterQueue(Queue* Q,elemtype x)
{
    if (IsFull(*Q))
    {
        printf("队列已满\n");
        return 0;
    }
    Q->data[Q->rear] = x;  //在队尾插入x
    Q->rear = Q->rear + 1;     //队尾指针后移一位
    return 1;
}

//出队,将队列中队头的元素出队,出队后队头指针front后移一位
int DeleteQueue(Queue* Q,elemtype* e)
{
    if (IsEmpty(*Q))
    {
        printf("队列为空!\n");
        return 0;
    }
    *e = Q->data[Q->fornt];   //出队元素值
    Q->fornt = (Q->fornt)+1;  //队尾指针后移一位
    return 1;
}

//获取队首元素
int GetHead(Queue Q, elemtype* e)
{
    if (IsEmpty(Q))
    {
        printf("队列为空!\n");
        return 0;
    }
    *e = Q.data[Q.fornt];
    return 1;  
}

//清空队列
void ClearQueue(Queue* Q)
{
    Q->fornt = Q->rear = 0;
}


//打印队列中的与元素
void PrintQueue(Queue Q)
{
    assert(&Q);  //断言队不空  
    int i = Q.fornt;
    while(i<Q.rear)
    {
        printf("%-3d", Q.data[i]);
        i++;
    }
    printf("\n");
}

int main()
{
    Queue Q;
    elemtype e;
//初始化队列。如果没有初始化,则需要在定义Q时(即第一条语句)使用关键字“static ”。但不推荐 
    InitQueue(&Q);

    EnterQueue(&Q, 1);
    EnterQueue(&Q, 2);
    EnterQueue(&Q, 3);
    EnterQueue(&Q, 4);
    EnterQueue(&Q, 5);
    EnterQueue(&Q, 6);
    EnterQueue(&Q, 8);
    EnterQueue(&Q, 10);
    EnterQueue(&Q, 12);
    EnterQueue(&Q, 15);
    EnterQueue(&Q, 16);//对满,16无法入队 

    printf("队列中的元素为:");
    PrintQueue(Q);
    
    printf("\n");

    DeleteQueue(&Q, &e);
    printf("出队元素为:%d\n", e);
    DeleteQueue(&Q, &e);
    printf("出队元素为:%d\n", e);
    printf("\n");
    
    printf("队列中的元素为:");
    PrintQueue(Q);
    printf("\n");

    e = GetHead(Q, &e);
    printf("队首元素为:%d\n", e);
    
    printf("#元素16入队#\n");
    EnterQueue(&Q, 16);
    
    printf("队列中的元素为:");
    PrintQueue(Q);
    printf("\n");
    
    return 1;
}

输出结果:
Data-Struct-Queue-circular-link


三、队列的循环结构

设立一个队首指针front ,一个队尾指针rear ,分别指向队首和队尾元素。
◆ 初始化:front=rear=0。
◆ 队列为空:front=rear。
◆ 队满:(rear + 1) % MaxSize == fornt
◆ 入队:将新元素插入rear所指的位置,然后rear加1。
◆ 出队:删去front所指的元素,然后加1并返回被删元素。
◆ 取队首元素:返回fornt指向的元素值

//当不需要修改队列中的元素时,建议不要直接用指针形参操作
#include<stdio.h>
#include<assert.h> //使用断言:assert(SCQ)

#define MaxSize 10

typedef int elemtype;

typedef struct QueueType 
{
    elemtype data[MaxSize];
    int fornt;
    int rear;
}CirQueue;

//队列初始化,
void InitCirQueue(CirQueue* SCQ)
{
    SCQ->fornt = SCQ->rear = 0;
}

//另一种队列初始化。须在main()中使用:CirQueue *SCQ=InitCirQueue();但感觉多余 
/* 
CirQueue *InitCirQueue()
{
    CirQueue *SCQ = (CirQueue *)malloc(sizeof(CirQueue));
    SCQ->fornt = SCQ->rear = 0;
    return SCQ;
}
*/

//判断队列是否为空
int IsEmpty(CirQueue SCQ)
{
    if (SCQ.fornt == SCQ.rear)
    {
        return 1;
    }
    return 0;
}

//判断队列是否为满
int IsFull(CirQueue SCQ)
{
    //尾指针+1追上队头指针,标志队列已经满了
    if ((SCQ.rear + 1) % MaxSize == SCQ.fornt)
    {
        return 1;
    }
    return 0;
}

//入队操作
int EnterCirQueue(CirQueue* SCQ, elemtype data)
{
    if (IsFull(*SCQ))
    {
        printf("队列已满,不能入队!\n");
        return 0;
    }
    SCQ->data[SCQ->rear] = data;
    SCQ->rear = (SCQ->rear+1) % MaxSize;   //重新设置队尾指针
    return 1;
}

//出队操作
int DeleteCirQueue(CirQueue* SCQ,elemtype* data)
{
    if (IsEmpty(*SCQ))
    {
        printf("队列为空!\n");
        return 0;
    }
    *data = SCQ->data[SCQ->fornt];
    SCQ->fornt = (SCQ->fornt + 1) % MaxSize;  //重新设置队头指针
    return 1;
}

//取队首元素
int GetHead(CirQueue SCQ,elemtype* data)
{
    if (IsEmpty(SCQ))
    {
        printf("队列为空!\n");
        return 0;
    }
    *data = SCQ.data[SCQ.fornt];
    return 1;
}

//清空队列
void ClearCirQueue(CirQueue* SCQ)
{
    SCQ->fornt = SCQ->rear = 0;
}

//打印队列元素
void PrintCirQueue(CirQueue SCQ)
{
    assert(&SCQ);   //断言SCQ不为空
    int i = SCQ.fornt;
    if (SCQ.fornt < SCQ.rear)
    {
        for (; i < SCQ.rear; i++)
        {
            printf("%-3d", SCQ.data[i]);
        }
    }
    else{
        for(; i< SCQ.rear+MaxSize; i++)
        {
            printf("%-3d",SCQ.data[i]);
        }
    }

    printf("\n");
}

int main()
{
    CirQueue SCQ;
    elemtype data;
    
//初始化队列。如果没有初始化,则需要在定义&SCQ时(即第一条语句)使用关键字“static ”。但不推荐 
    InitCirQueue(&SCQ);
    
    EnterCirQueue(&SCQ, 1);
    EnterCirQueue(&SCQ, 2);
    EnterCirQueue(&SCQ, 4);
    EnterCirQueue(&SCQ, 6);
    EnterCirQueue(&SCQ, 8);
    EnterCirQueue(&SCQ, 9);
    EnterCirQueue(&SCQ, 10);
    EnterCirQueue(&SCQ, 12);
    EnterCirQueue(&SCQ, 13);    
//为何此处的15无法进队?因为循环队列判断队列已满是以少存入一个数据来判断的!    
    EnterCirQueue(&SCQ, 15); 
   
    printf("队列中元素为:\n");
    PrintCirQueue(SCQ);

    DeleteCirQueue(&SCQ, &data);
    printf("出队元素为:%d\n", data);
    printf("\n");
    printf("队列中元素为:\n");
    PrintCirQueue(SCQ);
    printf("15入队:\n");
    EnterCirQueue(&SCQ, 15);
    printf("队列中元素为:\n");
    PrintCirQueue(SCQ);

    return 1;
}

输出结果
Data-Struct-Queue-circular-link


四、队列的链式结构

设立一个队首指针front ,一个队尾指针rear ,分别指向队首和队尾元素。
◆ 初始化:front=rear=pHead。
◆ 队列为空:front=NULL。
◆ 队满:无。
◆ 入队:新建节点,将新节点插入rear所指的下一个位置,修改rear指针。
◆ 出队:删去front所指的下一个节点,然后指向下下一个节点,最后释放。
◆ 取队首元素:返回fornt指向的元素值

//当不需要修改队列中的元素时,建议不要直接用指针形参操作
#include <stdio.h>
#include <stdlib.h> //使用malloc()的库 
#include <assert.h> //使用断言:assert(LQ)

typedef int elemtype;

typedef struct NodeType 
{
    elemtype data;
    struct NodeType* next;
}Node;

typedef struct LinkQueueType
{
    Node* front;
    Node* rear;
}LinkQueue;


//初始化队列
void InitLinkQueue(LinkQueue* LQ)
{
    //创建一个头结点
    Node* pHead = (Node*)malloc(sizeof(Node));
    assert(pHead);
    LQ->front = LQ->rear = pHead; //队头和队尾指向头结点
    LQ->front->next = NULL;
}

//判断队列是否为空
int IsEmpty(LinkQueue LQ)
{
    if (LQ.front->next == NULL)
    {
        return 1;
    }
    return 0;
}

//入队操作
void EnterLinkQueue(LinkQueue* LQ, elemtype data)
{
    //创建一个新结点
    Node* pNewNode = (Node*)malloc(sizeof(Node));
    assert(pNewNode);
    pNewNode->data = data;  //将数据元素赋值给结点的数据域
    pNewNode->next = NULL;  //将结点的指针域置空
    LQ->rear->next = pNewNode;   //将原来队列的队尾指针指向新结点
    LQ->rear = pNewNode;      //将队尾指针指向新结点
}

//出队操作
int DeleteLinkQueue(LinkQueue* LQ,elemtype* data)
{
    if (IsEmpty(*LQ))
    {
        printf("队列为空!\n");
        return 0;
    }
//pDel指向队头元素,由于队头指针front指向头结点,所以pDel指向头结点的下一个结点
    Node* pDel = LQ->front->next;  
    *data = pDel->data;   //将要出队的元素赋给data
    LQ->front->next = pDel->next;  //使指向头结点的指针指向pDel的下一个结点

//如果队列中只有一个元素,将队列置空
    if (pDel->next == NULL)   
    {
        LQ->rear = LQ->front;
    }
    free(pDel);   //释放pDel指向的空间
    return 1;
}

//取队头元素
int GetHead(LinkQueue LQ, elemtype* data)
{
    if (IsEmpty(LQ))
    {
        printf("队列为空!\n");
        return 0;
    }
    *data =  LQ.front->next->data;   //将队头元素值赋给data
    return 1; 
}

//清空队列
void ClearQueue(LinkQueue* LQ)
{
    while (LQ->front != NULL)
    {
        LQ->rear = LQ->front->next;  //队尾指针指向队头指针的下一个结点
        free(LQ->front);              //释放队头指针指向的结点
        LQ->front = LQ->rear;         //队头指针指向队尾指针
    }
}

//打印队列中的元素
void PrintLinkQueue(LinkQueue LQ)
{ 
    Node *pCur= LQ.front->next;;
    assert(&LQ);
    while (pCur)
    {
        printf("%-3d", pCur->data);
        pCur = pCur->next;
    }
    printf("\n");
}
int main()
{
    LinkQueue LQ; 
    elemtype data;
//初始化队列。如果没有初始化,则需要在定义LQ时(即第一条语句)使用关键字“static ”
    InitLinkQueue(&LQ);

    EnterLinkQueue(&LQ, 1); 
    EnterLinkQueue(&LQ, 2);
    EnterLinkQueue(&LQ, 3);
    EnterLinkQueue(&LQ, 4);
    EnterLinkQueue(&LQ, 5);
    EnterLinkQueue(&LQ, 6);
    EnterLinkQueue(&LQ, 7);
    EnterLinkQueue(&LQ, 8);
    
    printf("队列中的元素为:");
    PrintLinkQueue(LQ);
    printf("\n");

    data = GetHead(LQ, &data);
    printf("队头元素为:%d\n", data);
    printf("\n");

    DeleteLinkQueue(&LQ, &data);
    printf("出队的元素为:%d\n", data);
    printf("\n");
    
    printf("队列中的元素为:");
    PrintLinkQueue(LQ);
    printf("\n");
    
    GetHead(LQ, &data);
    printf("队头元素为:%d\n", data);
    printf("\n");
    
    ClearQueue(&LQ);

    return 1;
}

运行结果
Data-Struct-Queue-circular-link


五、运行环境

  1. windows7 X64
  2. Dev-C++ v5.11

六、参考文件


最后更新:2020 年 06 月 09 日 09 : 06 AM
本文链接:https://eonegh.com/Pythagorean-Fourier/Data-Struct-Queue-circular-link.html
版权声明:本文内容收集整理自互联网,著作权归原作者所有。

相关文章:

  • 考研数学—柯西不等式