数据结构——顺序队列与链式队列的实现-1

简介: 数据结构——顺序队列与链式队列的实现

一、概念

1、队列的定义

 队列 是仅限在 一端 进行 插入,另一端 进行 删除 的 线性表。

 队列 又被称为 先进先出 (First In First Out) 的线性表,简称 FIFO 。

b81c994f8ed4640616663b6e237b1f6a_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1doZXJlSXNIZXJvRnJvbQ==,size_2,color_FFFFFF,t_70#pic_center.png


2、队首

 允许进行元素删除的一端称为 队首。如下图所示:


fe6d9b5256ec7aec9d301e6e9cbd9387_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1doZXJlSXNIZXJvRnJvbQ==,size_2,color_FFFFFF,t_70#pic_center.png

3、队尾

 允许进行元素插入的一端称为 队尾。如下图所示:

edb7453c48364db9a016a798dc86faea_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1doZXJlSXNIZXJvRnJvbQ==,size_2,color_FFFFFF,t_70#pic_center.png


二、接口

1、可写接口

1)数据入队

 队列的插入操作,叫做 入队。它是将 数据元素 从 队尾 进行插入的过程,如图所示,表示的是 插入 两个数据(绿色 和 蓝色)的过程:

image.gif


2)数据出队

 队列的删除操作,叫做 出队。它是将 队首 元素进行删除的过程,如图所示,表示的是 依次 删除 两个数据(红色 和 橙色)的过程:

ee4bfda682f54a5688b2c6a7c31c709c.gif


3)清空队列

 队列的清空操作,就是一直 出队,直到队列为空的过程,当 队首 和 队尾 重合时,就代表队尾为空了,如图所示:

bb6b16d141c7465699c21ac703f39a13.gif


2、只读接口

1)获取队首数据

 对于一个队列来说只能获取 队首 数据,一般不支持获取 其它数据。


2)获取队列元素个数

 队列元素个数一般用一个额外变量存储,入队 时加一,出队 时减一。这样获取队列元素的时候就不需要遍历整个队列。通过 O(1) 的时间复杂度获取队列元素个数。


3)队列的判空

 当队列元素个数为零时,就是一个 空队,空队 不允许 出队 操作。


三、队列的顺序表实现

1、数据结构定义

对于顺序表,在 C语言 中表现为 数组,在进行 队列的定义 之前,我们需要考虑以下几个点:

 1)队列数据的存储方式,以及队列数据的数据类型;

 2)队列的大小;

 3)队首指针;

 4)队尾指针;


我们可以定义一个 队列结构体,C语言实现如下所示:

#define MAXSIZE 10
typedef int datatype;
 
typedef struct seqqueue{
  datatype data[MAXSIZE];
  int front,rear;
}seq_queue,*seq_pqueue;

2、初始化创造队列

第一种无形参,C语言实现如下所示:

seq_pqueue init1_seqqueue(void)
{
  seq_pqueue q;
  q=(seq_pqueue)malloc(sizeof(seq_queue));
  if(q==NULL)
  {
    perror("malloc");
    exit(-1);
  }
  q->front=q->rear=MAXSIZE-1;
 
  return q;
}

第二种有形参,C语言实现如下所示:

void init_seqqueue(seq_pqueue *Q)
{
  *Q=(seq_pqueue)malloc(sizeof(seq_queue));
  if((*Q)==NULL)
  {
    perror("malloc");
    exit(-1);
  }
  (*Q)->front=(*Q)->rear=MAXSIZE-1;
  
  return;
}

3、判断队列是否满

C语言实现如下所示:

bool is_full_seqqueue(seq_pqueue q)
{
  if((q->rear+1)%MAXSIZE == q->front)
    return true;
  else
    return false;
}

4、判断队列是否空

C语言实现如下所示:

bool is_empty_seqqueue(seq_pqueue q)
{
  if(q->rear == q->front)
    return true;
  else
    return false;
}

5、入队C语言实现如下所示:

bool in_seqqueue(datatype data,seq_pqueue q)
{
  //判断队列是否满
  if(is_full_seqqueue(q)){
    printf("队列已满!\n");
    return false;
  }
 
  //入队
  q->rear=(q->rear+1)%MAXSIZE;
  q->data[q->rear]=data;
  return true;
}


数据结构——顺序队列与链式队列的实现-2

https://developer.aliyun.com/article/1507983

相关文章
|
28天前
|
存储 Java 容器
深入浅出 栈和队列(附加循环队列、双端队列)
深入浅出 栈和队列(附加循环队列、双端队列)
|
11天前
数据结构——栈和队列
数据结构——栈和队列
13 1
|
22天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现(两个方式实现)
【数据结构】栈和队列的模拟实现(两个方式实现)
|
5天前
|
Python
数据结构===队列
数据结构===队列
|
1天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
7天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
8 1
|
11天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
18 4
|
11天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
14天前
|
算法 调度 Python
数据结构与算法-队列篇
数据结构与算法-队列篇
13 3
|
19天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
16 2

热门文章

最新文章