C++数据结构的队列详解
程序员文章站
2022-03-07 11:37:25
目录前言1. 队列的概念及结构2. 队列的实现2.1 queue.h2.2 queue.c2.3 test.c总结前言hello,大家好,这期文章我们来分享数据结构关于队列的知识。希望对大家有所帮助,...
前言
hello,大家好,这期文章我们来分享数据结构关于队列的知识。希望对大家有所帮助,闲言少叙,现在开始。
1. 队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出fifo(first in first out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头
2. 队列的实现
2.1 queue.h
#include<stdio.h> #include<stdbool.h> #include<assert.h> #include<malloc.h> typedef int qdatatype; typedef struct queuenode { struct queuenode*next; qdatatype data; }queuenode; typedef struct queue { queuenode *head; queuenode *tail; }queue; void queueinit(queue *pq); void queuedestory(queue *pq); void queuepush(queue *pq,qdatatype x); void queuepop(queue *pq); qdatatype queuefront(queue *pq); qdatatype queueback(queue *pq); bool queueempty(queue *pq); int queuesize(queue *pq);
2.2 queue.c
#include"queue.h" void queueinit(queue *pq) { assert(pq); pq->head = pq->tail = null; } void queuedestory(queue *pq) { assert(pq); queuenode *cur = pq->head; while (cur) { queuenode *next = cur->next; free(cur); cur = next; } pq->head = pq->tail = null; } void queuepush(queue *pq, qdatatype x) { assert(pq); queuenode *newnode = (queuenode*)malloc(sizeof(queuenode)); if (newnode == null) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = null; if (pq->tail == null) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } void queuepop(queue *pq) { assert(pq); assert(!queueempty(pq)); if (pq->head->next == null) { free(pq->head); pq->head = pq->tail = null; } else { queuenode *next = pq->head->next; free(pq->head); pq->head = next; } } qdatatype queuefront(queue *pq) { assert(pq); assert(!queueempty(pq)); return pq->head->data; } qdatatype queueback(queue *pq) { assert(pq); assert(!queueempty(pq)); return pq->tail->data; } bool queueempty(queue *pq) { assert(pq); return pq->head == null; } int queuesize(queue *pq) { int size = 0; queuenode *cur = pq->head; while (cur) { queuenode *next = cur->next; ++size; cur = cur->next; } return size; }
2.3 test.c
#include"queue.h" void testone() { queue q; queueinit(&q); queuepush(&q, 1); queuepush(&q, 2); queuepush(&q, 3); queuepush(&q, 4); while (!queueempty(&q)) { printf("%d ", queuefront(&q)); queuepop(&q); } printf("\n"); queuedestory(&q); } int main() { testone(); return 0; }
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!