队列的基本操作及实现

技术 > 数据结构 Data Structure

发布时间 : 2020-04-21 22:00

字数:925 阅读 :

评论:

1、队列的定义
2、队列的基本操作（创建、入队、出队、遍历）
THE END!

本文目录

1、队列的定义
2、队列的基本操作（创建、入队、出队、遍历）
THE END!

1、队列的定义

队列是一种特殊的线性表，特殊在于队列限定在一端进行插入，在另一端进行删除。
队列有两种物理存储结构：
1、顺序队列：循环队列是为了解决队列的“假溢出”现象。
2、链队列：队列的链式存储

2、队列的基本操作（创建、入队、出队、遍历）

#include <stdio.h>
#include <stdlib.h>

#define MAX_DATA_SIZE (20)
typedef int QElemType;

// 1、循环队列的顺序存储结构
typedef struct SqQueue
{
    QElemType data[MAX_DATA_SIZE];
    int front;  // 头指针
    int rear;   // 尾指针，若队列不空，则指向队列尾元素的下一个位置
} SqQueue;

// 1.1、初始化一个空队列Q
int InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return 0;
}

// 1.2、返回队列Q中的元素个数
int GetLengthQueue(SqQueue *Q)
{
    return ((Q->rear - Q->front +  MAX_DATA_SIZE) % MAX_DATA_SIZE);
}

// 1.3、入队列:若队列未满，则插入元素e为Q新的队尾元素
int EnterQueue(SqQueue *Q, QElemType e)
{
    if ((Q->rear + 1) % MAX_DATA_SIZE == Q->front)
    {
        printf("队列满了，无法插入新元素!\n");
        return -1;
    }

    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_DATA_SIZE;

    return 0;
}

// 1.4、出队列:若队列不空，则删除队头元素，并用e返回其值
int DeQueue(SqQueue *Q, int *e)
{
    if (Q->rear == Q->front)
    {
        printf("空栈!\n");
        return -1;
    }
    *e = Q->data[Q->front];
    Q->front =  (Q->front+1) % MAX_DATA_SIZE;

    return 0;
}


// 2、队列链式存储结构
typedef struct Node
{
    QElemType data;
    struct Node *next;
} Node, *LinkListPtr;

typedef struct LinkQueue
{
    LinkListPtr front, rear;
} LinkQueue;

// 2.1 队列初始化为空队列
int InitLinkQueue(LinkQueue *LQ)
{
    LinkListPtr QueueHead;
    QueueHead = (LinkListPtr) malloc(sizeof(Node));
    if (NULL == QueueHead)
    {
        printf("QueueHead malloc error!\n");
        return -1;
    }
    QueueHead->next = NULL;

    LQ->front = QueueHead;
    LQ->rear = QueueHead;

    return 0;
}

// 2.2 返回队列长度：遍历整个链表
int GetLengthLinkQueue(LinkQueue *LQ)
{
    LinkListPtr front = NULL;
    int length = 0;
    front = LQ->front;

    while (front != LQ->rear)
    {
        front = front->next;
        length++;
    }
    return length;
}

// 2.3 入队操作：在链表尾部插入结点,对于链队列不存在满的情况
int EnterLinkQueue(LinkQueue *LQ, int ele)
{
    LinkListPtr newNode = (LinkListPtr) malloc(sizeof(Node));
    if (NULL == newNode)
    {
        printf("newNode malloc error!\n");
        return -1;
    }
    newNode->data = ele;

    newNode->next = NULL;        
    LQ->rear->next = newNode;
    LQ->rear = newNode;            // 类似链表的尾插法

    return 0;
}

// 2.4 出队操作：若队列非空，则将链表中第一个结点删除，并返回其值给ele
int DeleteLinkQueue(LinkQueue *LQ, int *ele)
{
    LinkListPtr Linkfront;
    if (LQ->front == LQ->rear)
    {
        printf("空队列!\n");
        return -1;
    }

    Linkfront = LQ->front->next;
    *ele = Linkfront->data;

    LQ->front->next = Linkfront->next;

    if (LQ->rear == Linkfront)
    {
        LQ->rear = LQ->front;
    }
    free(Linkfront);
    Linkfront = NULL;

    return 0;
}

// 2.5 遍历输出队列元素:从队头到队尾
int TraverseLinkQueue(LinkQueue *LQ)
{
    LinkListPtr traversePtr = NULL;

    if (LQ->front == LQ->rear)
    {
        printf("空队列!\n");
        return -1;
    }
    traversePtr = LQ->front->next; //指向头结点的下一个结点

    while (traversePtr)
    {
        printf("%d\t ", traversePtr->data);
        traversePtr = traversePtr->next;
    }
    printf("\n");

    return 0;
}

// 2.6 返回队头结点元素
int GetQueueHead(LinkQueue *LQ, int *e)
{
    LinkListPtr head;
    if (LQ->front == LQ->rear)
    {
        return -1;
    }
    head = LQ->front->next;
    *e = head->data;

    return -1;
}

// test demo
int main(int argc, char * argv[])
{
    int ele = 0, length = 0;
    LinkQueue LQ;
    // 1. 队列初始化
    InitLinkQueue(&LQ);

    // 2. 入队列
    EnterLinkQueue(&LQ, 1);
    TraverseLinkQueue(&LQ);

    EnterLinkQueue(&LQ, 2);
    TraverseLinkQueue(&LQ);

    EnterLinkQueue(&LQ, 3);
    TraverseLinkQueue(&LQ);

    EnterLinkQueue(&LQ, 4);
    TraverseLinkQueue(&LQ);

    EnterLinkQueue(&LQ, 5);
    TraverseLinkQueue(&LQ);

    // 3. 返回队列长度
    length =  GetLengthLinkQueue(&LQ);
    printf("length: %d\n", length);

    // 4. 出队列
    DeleteLinkQueue(&LQ, &ele);
    printf("出队元素: %d \n", ele);
    TraverseLinkQueue(&LQ);

    GetQueueHead(&LQ, &ele);
    printf("队头元素: %d \n", ele);

    DeleteLinkQueue(&LQ, &ele);
    printf("出队元素: %d \n", ele);
    TraverseLinkQueue(&LQ);

    // 5. 队头元素
    GetQueueHead(&LQ, &ele);
    printf("队头元素: %d \n", ele);

    DeleteLinkQueue(&LQ, &ele);
    printf("出队元素: %d \n", ele);
    TraverseLinkQueue(&LQ);

    return 0;
}

THE END!

本博文只能阅读，谢绝转载，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2963033731@qq.com