系列文章目录
线性结构(一)顺序表及其代码实现
线性结构(二)单链表及其代码实现
线性结构(三)头结点的循环双链表
线性结构(四)栈及其代码实现及OJ题
线性结构(五)队列及代码实现
目录
- 系列文章目录
- 前言
- 1.前言
- 1.1 队列介绍
- 1.2 代码实现
- 总结
前言
1.前言
1.1 队列介绍
队列也是一种线性结构,队列要求,队尾插入元素,队头删除元素。所以队列元素是“First In First Out”,也即FIFO.
由于队列只能在队头删除,队尾插入,那么记录尾指针效率更高;因此要记录头指针、尾指针、数据元素个数,多个数据我们考虑存在结构体中,因此要定义新的结构体代表队列。这种情况下,求队列长度无需遍历,时间复杂度为O(1),无独有偶,单链表也可以这样处理,记录头指针和size,存在数据结构中,代表单链表。求单链表长度无需遍历,时间复杂度为O(1).
还有双向带头循环链表,或许有的小伙伴考虑头结点存储链表长度,但是如果链表数据类型是char,链表长度>127就溢出(溢出不等于截断,打个比方,截断是int赋给char,char存不下)了。再者,如果类型是double呢,链表长度为浮点数?好生奇怪。
1.2 代码实现
Queue.h
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode//代表队列的一个结点
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue//代表队列
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
bool QueueEmpty(Queue* pq);
void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head,*next=NULL;
while (cur)
{
next= cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc failed");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
assert(pq->tail==NULL);
pq->tail = pq->head = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head!=NULL);
/*QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
if (pq->head == NULL)
pq->tail = NULL;*/
if (pq->head->next == NULL)//只剩一个元素时,尾删要置尾指针为NULL.
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
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;
}
Test.c
#include "Queue.h"
int main()
{
Queue q;
QueueInit(&q);
for(int i=0;i<5;i++)
QueuePush(&q, i + 1);
printf("%d\n", QueueBack(&q));
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);//队列的性质,一边出队,一边访问队头元素
}
printf("%d\n", QueueSize(&q));
QueueDestroy(&q);
return 0;
}
总结
队列在队尾入队,队头出队。一个很新的点就是,除定义表示结点的结构体之外,还定义表示队列的结构体,这也能运用到单链表中,但用头结点存储链表元素个数不可取。