链式队列

链式队列结构体声明

typedef struct Linkqueue{
    data_t data;
    struct Linkqueue *next;
}Link;

队列的主体部分就是链表的定义

typedef struct{
    Link *front;
    Link *rear;
}queue;

队列的定义，通过指针front和rear来操作

链式队列的操作

基本操作：创建、入队、出队、遍历（打印）、求队列长度

创建一个队列

queue* create()
{
    Link *h = (Link*)malloc(sizeof(Link));
    queue *q = (queue*)malloc(sizeof(queue));
    q->front = h;
    q->rear = h;
    return q;
}

1、创建一个链表的头结点

2、创建一个队列的操作结点

3、队列的操作结点初始化均指向链表的头结点

4、q->front一直指向头结点h，当有数据插入后，q->rear一直指向最后一个数据结点，这符合队列的属性

创建一个数据结点

Link* createNode(data_t val)
{
    Link *node = (Link*)malloc(sizeof(Link));
    node->data = val;
    node->next = NULL;
    return node;
}

入队（尾插法）

void push(queue *q,data_t val)
{
    Link *node = createNode(val);
    q->rear->next = node;
    q->rear = node;
    size++;
}

也可以指定在头结点处为队尾，则入队操作相当于链表的头插法

链表不会出现没有队满的情况，除非计算机物理内存满了

判断队是否为空

int isEmpty(queue *q)
{
    return q->front->next==NULL?1:0;
}

出队（头删法）

data_t pop(queue *q)
{
    if(q->front->next==NULL)
    {
        printf("表空\n");
        return -1;
    }
    Link *temp = q->front->next;
    data_t data = temp->data;
    q->front->next = temp->next;
    free(temp);
    size--;
    return data;
}

先判断下链表是否为空

也可以指定链表的最后一个数据为队头，则出队相当于对最后一个数据结点的前驱结点修改next指针指向

遍历（打印）（队长）

void printLinkQueue(queue *q)
{
    Link *temp = q->front;
    while(temp->next!=NULL)
    {
        temp=temp->next;
        printf("%d ",temp->data);
    }
    putchar(10);
}

求链式队列长度有2中思路：

1）定义一个全局变量size记录出队入队的情况

2）遍历一遍

示例

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

typedef int data_t;
typedef struct Linkqueue{
    data_t data;
    struct Linkqueue *next;
}Link;
typedef struct{
    Link *front;
    Link *rear;
}queue;

queue* create();
Link* createNode(data_t val);
void push(queue *q,data_t val);
data_t pop(queue *q);
void printLinkQueue(queue *q);
int size = 0;
int main(int argc, const char *argv[])
{
    queue *q = create();
    push(q,1);
    printLinkQueue(q);
    push(q,2);
    printLinkQueue(q);
    push(q,3);
    printLinkQueue(q);
    push(q,4);
    printLinkQueue(q);
    push(q,5);
    printLinkQueue(q);
    printf("出队：%d\n",pop(q));
    printLinkQueue(q);
    printf("出队：%d\n",pop(q));
    printLinkQueue(q);
    printf("size:%d\n",size);
    return 0;
}
//创建一个队列
queue* create()
{
    Link *h = (Link*)malloc(sizeof(Link));
    queue *q = (queue*)malloc(sizeof(queue));
    q->front = h;
    q->rear = h;
    return q;
}
//创建一个数据结点
Link* createNode(data_t val)
{
    Link *node = (Link*)malloc(sizeof(Link));
    node->data = val;
    node->next = NULL;
    return node;
}
//入队（尾插法）
void push(queue *q,data_t val)
{
    Link *node = createNode(val);
    q->rear->next = node;
    q->rear = node;
    size++;
}
//出队（头删法）
data_t pop(queue *q)
{
    if(q->front->next==NULL)
    {
        printf("队空\n");
        return -1;
    }
    Link *temp = q->front->next;
    data_t data = temp->data;
    q->front->next = temp->next;
    free(temp);
    size--;
    return data;
}
//遍历（打印）
void printLinkQueue(queue *q)
{
    Link *temp = q->front;
    while(temp->next!=NULL)
    {
        temp=temp->next;
        printf("%d ",temp->data);
    }
    putchar(10);
}

结果

1 
1 2
1 2 3
1 2 3 4
1 2 3 4 5
出队：1
2 3 4 5
出队：2
3 4 5
size:3

本文链接：https://shengto.top/data_structure/159.html

转载时须注明出处及本声明

Last modification：2021 年 03 月 26 日 02 : 23 : 28
© 允许规范转载