MENU

头指针和计数器构成的循环队列

• October 28, 2020 • 队列和堆栈

顺序循环队列常规的设计方法使用队尾指针和队头指针:队尾指针用于指示当前的队尾位置的下标,队头指针用于指示当前队头位置的下标。现要求设计一个使用队头指针和计数器的顺序循环队列,其操作包括初始化、入队列、出队列、取队头元素和判断队列是否非空


题目分析:

一般我们的顺序循环队列的结构体有四个属性:存储数组、头指针、尾指针、数据个数。 如果要添加数据,两步: (1)在最后一个数据后面添加新数据元素,并且改变 尾指针 的指向 (2)数据元素个数+1 如果要删除数据,两步: (1)在第一个数据后面添加新数据元素,并且改变 头指针 的指向 (2)数据元素个数-1 但按照题目的要求,我们只能使用三个属性:存储数组、头指针、数据个数(计数器)。 万变不离其中,我们只要能根据头指针和计数器找到尾指针,那么一切就ok了

很显然:queue->rear = queue->head+queue->count,即 尾指针 = 头指针 + 数据个数

但是,我们还需要注意一个问题,那就是顺序循环队列的"假溢出"问题,什么是假溢出呢?一句话,你在往队列里面加元素时,它说我的存储空间满了,但是它的实际存储空间并没有满,所以被称为“假溢出”。 其真实的存储状况是数组前面的部分的空间没有被队列占用,而后面的存储空间都被占用了。

为了防止假溢出现象,我们寻找尾指针的方法是: queue->rear = (queue->head + queue->count)%MAX,这样当出现“假溢出”时,我们就能把新添加的数据放置在数组的前面部分,来解决“假溢出"


考点:

**1.利用头指针和计数器寻找尾指针
2.队列的添加、删除、取头元素、判断非空的操作算法**


代码实现:

说明:此代码利用顺序存储结构,包含一个头文件"Queue.h",以及一个源文件"main.c"
Queue.h 部分

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char dataType;
const int MAX = 25;      //顺序表的最大容量
//定义结构体
typedef struct queue
{
    dataType array[MAX];
    int head;       //队头指针
    int count;      //计数器
}Queue;
//初始化队列
void queueInitiate(Queue *queue)
{
    queue->head = 0;
    queue->count = 0;
}
//判断队列是否非空
int queueIsNotEmpty(Queue *queue)
{
    if (queue->count <= 0)
        return 0;
    return 1;
}
//添加数据元素
int queuePush(Queue *queue,dataType data)
{
    //如果队满,不能添加
    if (queue->count >= MAX)
        return 0;
    //queue->count+queue->head:找到队列最后一个元素,%MAX防止假溢出
    queue->array[(queue->count + queue->head)%MAX] = data;
    queue->count++;               //元素个数加1
    return 1;
}
//删除数据元素,数据元素由data带出
int QueuePop(Queue *queue, dataType *data)
{
    //如果队空,不能删除
    if (!queueIsNotEmpty)
        return 0;
    //队头元素赋给data指向的位置
    *data = queue->array[queue->head];
    //重新定位头指针,%MAX:防止假溢出
    queue->head = (queue->head + 1) % MAX;
    queue->count--;
    return 1;
}
//取队头元素
int getHead(Queue *queue, dataType *data)
{
    //如果队空,没有头元素
    if (!queueIsNotEmpty)
        return 0;
    *data = queue->array[queue->head];
    return 1;
}
//遍历输出数据元素
void queuePrint(Queue *queue)
{
    printf("队列:   ");
    for (int i = queue->head; i < queue->head + queue->count; i++)
        printf("%c  ", queue->array[i]);
    printf("\n");
}

main.c 部分

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"Queue.h"
int main()
{
    Queue queue;
    Queue *p = &queue;
    char ch;
    queueInitiate(p);
    ch = 'A';
    //往队列里面放4个字母:A,B,C,D
    for (int i = 0; i < 4; i++)
        if (queuePush(p, ch))
            ch++;
        else
            printf("入队失败!数据元素已满!\n");
    queuePrint(p);                     //打印队列
    //测试出队列 ,连续出两个数据元素
    QueuePop(p, &ch);
    printf("%c 已出队列!\n", ch);
    queuePrint(p);                     //打印删除元素后的队列
    QueuePop(p, &ch);
    printf("%c 已出队列!\n", ch);
    queuePrint(p);
    //再往队列里面添加一个数据
    if (queuePush(p, 'Y'))
        printf("Y 已成功加入队列\n");
    else
        printf("Y加入队列失败\n");
    queuePrint(p);
    //测试取队头元素
    getHead(p, &ch);
    printf("队头元素:%c\n", ch);
    queuePrint(p);
    //测试队列非空函数
    if (queueIsNotEmpty(p))
        printf("当前队列非空!\n");
    else
        printf("当前队列已空!\n");
    system("pause");
    return 0;
}

运行结果:


代码编译器:Visual Studio 2017
ok

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