欢迎来到军工软件开发人才培养基地——学到牛牛

数组实现队列

时间:2024-05-06 07:01:10 来源:学到牛牛

 

队列是一种非常基础的数据结构,其特点是先入先出,也就是我们常说的FIFO(first in first on), 即操作数据从两端进行。

 

 

 

如上图就是生活中常见的队列的应用场景,这样的应用场景在我们生活中也有很多。在队列中主要的操作包括数据的入队和出队、求队列中的元素个数、判断队列是否为空和为满、以及队列中的首位元素的获取。

 

 

如上图就是队列元素的入队列和出队列的操作过程,在入队列时,元素只能从队尾进入队列,而在出队列的时候则只能从队首出,也就是我们常说的“先进先出“。

针对队列中的元素进出队列,我们也可以通过数组的方式来实现该操作。

#include <stdio.h>

#include <stdlib.h>

 

#define MAX_SIZE 10

 

struct stack{

int arr[MAX_SIZE];

int tail;

int head;

};

 

void init(struct stack *p) //初始化队列

{

p->tail = 0;

p->head = 0; //定义头尾指针的初始状态

memset(p->arr, 0, sizeof(arr)); //将队列的内存置零

}

 

int isFull(struct stack *p) //判断队列是否为满

{

if(p->tail == MAX_SIZE) //当尾指针为队列最大值时队列为满

{

return 1;

}

else

{

return 0;

}

}

 

int isEmpty(struct stack *p) //判断队列是否为空

{

if(p->tail == p->head) //当头指针和尾指针重合时队列为空

{

return 1;

}

else

{

return 0;

}

}

 

int push(struct stack *p, int val) //入队列

{

if(isFull(p) == 1) //先判断队列是否为满

{

printf(“FULL!\n”);

return -1;

}

p->arr[p->tail] = val;

p->tail++;

return val;

}

 

int pop(struct stack *p) //出队列

{

if(isEmpty(p) == 1) //先判断队列是否为空

{

printf(“EMPTY!\n”);

return -1;

}

int result = p->arr[p->head]; //先将要出队列的元素存放

p->arr[p->head] = 0; //再将该元素置零

p->head++; //头指针指向下一元素

return result;

}

 

void show(struct stack *p) //队列的遍历

{

int i = 0;

for(i = p->head; i < p->tail; i++)

{

printf(“队内元素为:%d\n”, p->arr[i]);

}

}

 

int main()

{

struct stack sta;

struct stack *p = &sta;

init(p);

int i = 0;

for(i = 0; i < MAX_SIZE; i++) //入队列操作

{

printf(“入队列的元素是:%d\n”, push(p, i+1));

show(p);

printf(“\n”);

}

for(i = 0; i < MAX_SIZE; i++) //出队列操作

{

printf(“出队列的元素是:\n”, pop(p));

show(p);

printf(“\n”);

}

return 0;

}   

通过数组的形式表现队列的进出队列操作,是利用一组地址连续的存储单元用来存放队列中的元素。在这当中,为了避免当队列中只有一个元素的时候,队首和队尾因为重合而使得处理变得麻烦,所以我们可以使用两个指针,head指针指向队首元素,tail元素指向队尾元素的下一个位置。将头尾指针的初始值都设为0,入队列时尾指针tail加1,出队列时头指针head加1,当头尾指针相等的时候队列为空。