MENU

尾指针循环队列

• October 29, 2020 • 队列和堆栈

假设以带头结点的单循环链表实现链式队列,并且要求只设尾指针,不设头指针,编写实现这种链式队列初始化、入队列和出队列操作的函数


题目分析:

队列具有队头和队尾,即头指针和尾指针。本题要求只使用尾指针,在我们之前的 头指针和计数器构成的循环队列,我们使用了顺序表构建只带头指针和计数器的队列,在那篇文章中,我们使用头指针和奇数器找到了尾指针,所以能够攻破题目。而此题只允许用一个尾指针,该怎么办呢?

回想单链表知识,我们只根据头结点可以找到链表上的任意一个结点,那么相对应的,我们可以把单链表的头结点当做是队列的尾结点,将队列的最后一个数据元素的指针域指向队列的尾结点(实际是单链表的头结点),而尾结点的指针域直接指向队列的第一个数据结点,这样就构成了一个循环队列(环),达到题目要求:带头结点,循环,只有尾指针。

接下来给大家画一下过程,因为我在学数据结构这门课时,正是这道题我搞了好久,一直都是脑子凭空想,结果错误的思路剪不断理还乱,第一次做没有做出来,到第二次做的时候我首先画了结构示意图,根据示意图来敲代码,很快就敲出来啦,示意图如下:

入队:


出队:


代码实现:

注:此代码包含一个头文件《Queue.h》和一个测试源文件《main.cpp》

Queue.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef int DataType; //数据类型为int
//定义结点结构体
struct Node
{
    DataType data;    //数据域
    Node *next;       //指针域
};
//定义队列结构体,只有尾指针
struct Queue
{
    Node *rear;
};
//初始化队列
void Initiate(Queue *queue)
{
    queue->rear = (Node*)malloc(sizeof(Node));//分配内存空间而没有值,相当于单链表的头结点
    queue->rear->next = queue->rear;
}
//判断队列是否为空
int isNotEmpty(Queue *queue)
{
    if (queue->rear->next == queue->rear)  //尾指针的下一个就是尾指针,所以就没有数据结点,即队列为空
        return 0;
    else
        return 1;
}
//入队函数
int queuePush(Queue *queue, int x)
{
    Node *p = queue->rear;        //创建替身指针,以保证在后续过程中原先指针保持不变
    //遍历队列,使p指向尾结点的前一个结点(队尾结点)
    while (p->next!=queue->rear)
    {
        p = p->next;
    }
    Node *q;
    q = (Node*)malloc(sizeof(Node));//为新结点分配内存空间
    q->data = x;                    //新结点的数据域为x
    q->next = queue->rear;          //新结点的下一个结点是队列尾结点
    p->next = q;                    //把新结点放在尾结点的前面,因为p现在指向的是尾结点的前一个结点
    printf("入队成功!\n");
    return 1;
}
//出队函数,将成功出队的数据赋给d
int queuePop(Queue *queue, int *d)
{
    //要出队就要判断队列是不是还有数据元素
    if (isNotEmpty(queue) == 0)
    {
        printf("队列为空!");
        return 0;
    }
    Node *q = queue->rear->next;       //q指向队列第一个结点
    queue->rear->next = q->next;       //尾结点指针域直接指向原队列第二个结点
    *d = q->data;                      //将出队数据赋给d,带出函数
    free(q);                           //释放内存空间
    return 1;
}
//打印队列函数
void print(Queue *queue)
{
    Node *p = queue->rear;
    printf("队列:");
    if (isNotEmpty(queue) == 0)
    {
        printf("队列为空");
        return;
    }
    //遍历输出
    while (p->next != queue->rear)
    {
        printf("%d  ", p->next->data);
        p = p->next;
    }
    printf("\n");
}

main.c:

#include"Queue.h"
int main()
{
    Queue queue, *p;
    p = &queue;
    Initiate(p);
    printf("队列原始有几个数:");
    int n, data;
    scanf_s("%d", &n);
    /*建立一条有n个数的队列*/
    for (int i = 0; i < n; i++)
    {
        scanf_s("%d", &data);
        queuePush(p, data);
    }
    print(p);
    system("pause");
    int x;
    /*测试出队*/
    if(queuePop(p, &x))
        printf("已取出数据:%d\n", x);
    print(p);
    system("pause");
    if (queuePop(p, &x))
        printf("已取出数据:%d\n", x);
    print(p);
    system("pause");
    if (queuePop(p, &x))
        printf("已取出数据:%d\n", x);
    print(p);
    system("pause");
    /*测试入队*/
    printf("请输入要入队的数据:");
    scanf_s("%d", &data);
    queuePush(p, data);
    print(p);
    system("pause");
    /*又测试出队*/
    if (queuePop(p, &x))
        printf("已取出数据:%d\n", x);
    print(p);
    system("pause");
    if (queuePop(p, &x))
        printf("已取出数据:%d\n", x);
    print(p);
    system("pause");
    if (queuePop(p, &x))
        printf("已取出数据:%d\n", x);
    print(p);
    system("pause");
    if (queuePop(p, &x))
        printf("已取出数据:%d\n", x);
    print(p);
    system("pause");
    return 0;
}

运行结果:


测试一


测试二


测试三


代码编译器:Visual Studio 2017
ok,没问题

Archives QR Code Tip
QR Code for this page
Tipping QR Code