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

数据结构之队列

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

1.简介

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。

队列和栈一样,是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。故队列又称为先进先出(FIFO—first in first out)线性表。

 

1.png

 

队列包含的基本操作:

1.入队操作:在队尾插入数据

2.出队操作:在对头删除数据

3.队列中没有元素时,称为空队列

4.队列中存储达到预定上限,称为队满

队列可以使用数组或链表作为物理存储结构,使用数组实现的队列称为顺序队列,使用链表实现的队列称为链式队列。

2.顺序队列

顺序队列使用数组作为物理存储结构,数组特点是内存连续,并且在初始状态就定义了数组的大小。数组在出队时后,需要注意对数据进行搬移。

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

 

struct SeqQueue {

int* buf; // 队列中存储空间的指针

int head; // 队头

int tail; // 队尾

int maxSize; // 队列最大值

};

 

// 初始化队列

void init(struct SeqQueue* que, int size)

{

que->head = 0;

que->tail = 0;

que->buf = (int *)malloc(sizeof(int) * size);

que->maxSize = size;

memset(que->buf, 0, sizeof(int) * size);

}

 

// 队列释放

void destroy( struct SeqQueue* que )

{

free(que->buf);

que->buf = NULL;

}

 

// 遍历队列数据

void display(struct SeqQueue* que)

{

printf("queue size = %d, show queue: ", que->tail - que->head );

int i = 0;

for (i = que->head; i != que->tail; i++) {

printf("%d,", que->buf[i]);

}

printf("\n");

}

 

// 队列是否为满

int isfull(struct SeqQueue* que)

{

return (que->tail - que->head) == que->maxSize;

}

 

// 队列是否为空

int isempty(struct SeqQueue* que)

{

return que->tail == que->head;

}

 

// 入队

int push(struct SeqQueue* que, int val)

{

if ( isfull(que)) { //  队满,无法插入

return -1;

}

if (que->tail == que->maxSize) {  // 如果队尾已经到了边界,需要把队列数据向数组最开始进行数据搬移

memmove(que->buf, que->buf + que->head, (que->tail - que->head)*4 );

que->tail -= que->head;

que->head = 0;

}

que->buf[que->tail] = val;

que->tail++;

return que->tail - 1;   // 返回插入位置,该位置可能进过数据搬移

}

 

// 出队

int pop(struct SeqQueue* que)

{

if (isempty(que)) {

return -1;

}

return que->head++;

}

 

int main()

{

struct SeqQueue queue;

init(&queue, 5);

display(&queue);

push(&queue, 20);

push(&queue, 30);

push(&queue, 40);

push(&queue, 50);

push(&queue, 60);

display(&queue);

printf("push = %d\n", push(&queue, 70) );  // 队满,此时无法插入

display(&queue);

printf("pop = %d\n", pop(&queue) );

printf("pop = %d\n", pop(&queue) );

printf("push = %d\n", push(&queue, 70));  // 经过搬移,可以插入数据

display(&queue);

destroy(&queue);

return 0;

}

3.链式队列

链式队列是基于链表实现的顺序表,区别于顺序队列它的内存可以是不连续的,队头和队尾的操作无需进行数据搬移。

struct LinkNode {

struct LinkNode* next;

int val;

};

 

struct LinkQueue {

struct LinkNode head; // 始终作为头节点

struct LinkNode* tail;  // 始终指向队列最后一个节点

};

 

void init(struct LinkQueue* que)

{

que->head.next = NULL;

que->tail = &que->head;

}

 

void display(struct LinkQueue* que)

{

if (que->head.next == NULL) { // 队列无节点

return;

}

printf("show queue: ");

struct LinkNode* ptr = que->head.next;

while (ptr != que->tail) {

printf("%d, ", ptr->val);

ptr = ptr->next;

}

printf("\n");

}

 

void push(struct LinkQueue* que, int val)

{

struct LinkNode* node = (struct LinkNode *)malloc(sizeof(struct LinkNode));

node->val = val;

node->next = NULL;

que->tail->next = node;

que->tail = node; // 队尾指针始终指向最后一个节点

}

 

struct LinkNode* pop(struct LinkQueue* que)

{

struct LinkNode* ret = NULL;

ret = que->head.next;

if (ret == NULL) {

return NULL; // 队列空,返回空

}

que->head.next = ret->next; // 返回头结点地址

return ret;

}

 

int main()

{

struct LinkQueue queue;

init( &queue );

display(&queue);

push(&queue, 20);

push(&queue, 30);

push(&queue, 40);

push(&queue, 50);

push(&queue, 60);

display(&queue);

push(&queue, 70); 

display(&queue);

printf("pop = %p\n", pop(&queue) );

printf("pop = %p\n", pop(&queue) );

push(&queue, 70);

display(&queue);

return 0;

}