【数据结构】队列

2023-12-13 20:06:53

队列的基本概念及描述

队列是一种特殊的线性表,它的特殊之处在于队列的插入和删除操作分别在表的两端进行。插入的那一端称为队尾,删除的那一端称为队首。队列的插入操作和删除操作分别简称为进队和出队。

生活中的排队购物等现象就是队列的例子。它的特点是先到先享受购票服务,对于一个队列
k 0 , k 1 , k 2 . . . , k n ? 1 {k_0,k_1,k_2...,k_{n-1}} k0?,k1?,k2?...,kn?1?

如果 k 0 k_0 k0?那端是队首, k n ? 1 k_{n-1} kn?1?那端是队尾,则 k 0 k_0 k0?是这些结点中最先插入的结点,若要进行删除操作, k 0 k_0 k0?将首先被删除,所以说,队列有“先进先出”(First In First Out,FIFO)特点的线性结构。

顺序队列及其实现

在C语言中,队列的顺序存储可以用一维数组表示。为了标识队首和队尾,需要附设两个指针fronth和rear,front指示的是队列中最前面,即队首结点在数组中元素的下标。rear指示的是队尾结点在数组中元素下标的下一个位置,也就是说rear指示的是即将插入的结点在数组中的下标。
下面所示是队列的几种状态。

①空队列

②连续插入几个结点后的状态

③连续删除几个结点后的状态

④在③状态下再删除一个结点后的状态

⑤连续插入若干个结点后的状态,但数组前部有空位置

队列顺序存储结构的C语言描述

队列顺序存储的头文件

文件名seqqueue.h

#define MAXSIZE 100
typedef int datatype;
typedef struct
{
    datatype a[MAXSIZE];
    int front;
    int rear;
}sequence_queue;

队列的初始化

void init(sequence_queue *sq)
{
   //这里注意rear和front不是指针类型变量
   //注意看结构体定义 front 和rear都为int型
   //即初始化让让front 和rear都指向数组的第一个元素的位置
    sq->front=sq->rear=0;
}

判断队列是否为空

int empty(sequence_queue sq)
{
    //判空条件 front==rear
    return (sq.front==sq.rear?1:0);
}

打印队列的结点值

void display(sequence_queue sq)
{
    int i;
    if(empty(sq))
        printf("\n顺序队列是空的。");
    else
        {
            for (i=sq.front;i<sq.rear;i++)
            {
                printf("%5d",sq.a[i]);
            }
        }
}

取得队列的队首结点值

datatype get(sequence_queue sq)
{
    if(empty(sq))
    {
        printf("\n顺序队列是空的!无法获得队首结点值!")exit(1);
    }
    return sq.a[sq.front];
}

进队操作

void insert(sequence_queue *sq,datatype x)
{
    int i;
    if (sq->rear==MAXSIZE)
    {
        printf("\n顺序队列是满的!");
        exit(1);
    }
    else
    sq->a[sq->rear]=x;
    sq->rear=sq->rear+1;  
}

出队操作

void del(sequence_queue *sq)
{
    if (sq->rear==sq->front)
    {
        printf("\n顺序队是空的!不能做删除操作!");
        exit(1);
    }
    sq->front++;
}

顺序循环队列及其实现

给定一个大小为MAXSIZE的数组存储一个队列,经过若干次插入和删除操作后,当队尾指针rea==MAXSIZE时,呈现队满的状态,而事实上数组的前部分可能还有空闲的位置。为了有效利用空间,将顺序存储的队列想象成一个环状,把数组中的最前面和最后面的两个元素看作是相邻的,这就是 循环队列

在循环队列中,如果队列中最后一个结点存放在数组的最后一个位置,而数组前面有空位置的话,则下次再进行插入操作时,将插入数组最前面那个元素的位置。其他情况下的插入操作和一般的队列的插入操作一样。

下面给出循环队列的几种状态。
①空的循环队列

②插入几个元素之后的循环队列

③剩余一个空间的循环队列

④只有一个结点的循环队列

在第三种情况下:
如果再插入一个新的结点,则数组空间被全被占用,队列已满,且rear=front。
在第④种情况下:
若删除一个结点,则队列成为空队列,此时也有rear=front。
也就是说循环队列队满与空的条件都是rear=front。
这个问题如何解决呢?
一种方法是设置一个标志,标识是由于rear增1使得rear=front还是front增1使rear=front,前者是队满而后者是队空。
另一种方法是牺牲一个数组元素的空间,即若数组的大小是MAXSIZE,则该数组所表示的循环队列最后允许存储MAXSIZE-1个结点。这样队满的条件是:
(rear+1)%MAXSIZE=front
而对空的条件是:
rear=front

循环队列的顺序存储与一般队列一致,但是循环队列基本操作的实现和一般队列是有去区别的。主要区别在于判断对空与队满的条件以及相关指针增1的表达上,循环队列中指针增1时要增加一个取模操作,使之成为一个循环队列。

循环队列的插入操作

void insert_sequence_cqueue(sequence_queue *sq,datatype x)
{
    if((sq->rear+1)%MAXSIZE==sq->front)
    {
        printf("\n顺序循环队列是满的!无法进行插入操作")
    }
    sq->a[sq->rear]=x;
    sq->rear=(sq->rear+1)%MAXIZE;
}

循环队列的删除操作

void dele_sequence_cqueue(sequence_queue *sq)
{
    if (sq->front==sq->rear)
    {
       printf("\n循环队列是空的!无法进行删除操作!");
       exit(1);
    }
    sq->front(sq->front+1)%MAXSIZE;
}

文章来源:https://blog.csdn.net/2302_76305195/article/details/134978131
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。