链式队列的基本操作

2023-05-18 81

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 链式队列的基本操作

结构

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);//取队尾的数据
int QueueSize(Queue* pq);//有多少个数据
bool QueueEmpty(Queue* pq);//判断队列是否为空

队列的初始化

//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}

队列的销毁

void QueueDestory(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur)
  {
  QueueNode* next = cur->next;
  free(cur);
  cur = cur->next;
  }
  pq->head = pq->tail = NULL;
}

这里和单链表的销毁几乎一模一样，先用指针cur指向head（QueueNode* cur = pq->head;），然后只要cur不为空，就一直循环下去，直到cur为空为止，最后别忘记把头和尾均置为空。

队列的尾插（队尾入）

void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
  pq->head = pq->tail = newnode;
  }
  else
  {
  pq->tail->next = newnode;
  pq->tail = newnode;
  }
}

队列尾插（这里就相当于队尾入）的思路：首先肯定要新建一个节点。接下来就要分为两种情况(一种是队列为空的情况，另外一种就是队列不为空的时候)。当队列为空的时候，我们直接把新建的节点newnode复制该head和tail；当队列不为空的时候，先把新建的节点newnode赋值给tail->next，然后再把newnode赋值给tail，所以，直接按部就班操作就行（pq->tail->next = newnode;pq->tail = newnode;）。

当我们在队尾插入了一个元素之后，我们来看一下调试结果：

判断队列是否为空

bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

队尾的头删（队头出）

//删除
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //if (pq->head == NULL)
  //{
  //  return;
  //}//温柔的处理
  QueueNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  if (pq->head == NULL)
  {
  pq->tail=NULL;
  }
}

取队头数据

QDataType QueueFront(Queue* pq)//取队头的数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}

取队头数据的话，我们首先要保证队列中有数据，要加上断言（assert(!QueueEmpty(pq));）所以如果队列已经为空了但是我们仍要删除数据就会直接报错来提示我们。

取队尾数据

QDataType QueueBack(Queue* pq)//取队尾的数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

这里需要注意的是当我们调用此函数直到把队列中的元素删除完之后，不要忘记把tail置为空指针，否则tail就会成为野指针，也会就会影响我们取队尾的数据。

有多少个元素

int QueueSize(Queue* pq)//有多少个数据
{
  assert(pq);
  int n = 0;
  QueueNode* cur = pq->head;
  while (cur)
  {
  n++;
  cur = cur->next;
  }
  return n;
}

遍历整个队列即可。

总代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue1()
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  QueuePop(&q);
  QueuePop(&q);
  QueuePop(&q);
  QueuePop(&q);
  //QueuePop(&q);
  //printf("%d\n", QueueFront(&q));
  //printf("%d\n", QueueFront(&q));
  QueuePush(&q, 10);
  QueuePush(&q, 20);
  QueueDestory(&q);
}
void TestQueue2()
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  while (!QueueEmpty(&q))
  {
    QDataType front = QueueFront(&q);
    printf("%d ", front);
    QueuePop(&q);
  }
  printf("\n");
}
//测试队列为空时但想要取数据就会直接报错
void TestQueue3()
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  QueuePop(&q);
  QueuePop(&q);
  QueuePop(&q);
  QueuePop(&q);
  QDataType back = QueueBack(&q);
}
int main()
{
  //TestQueue1();
  //TestQueue2();
  TestQueue3();
  return 0;
}

quene.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = cur->next;
  }
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == 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 == NULL)
  //{
  //  return;
  //}//温柔的处理
  QueueNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  if (pq->head == NULL)
  {
    pq->tail=NULL;
  }
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
QDataType QueueBack(Queue* pq)//取队尾的数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
QDataType QueueFront(Queue* pq)//取队头的数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
int QueueSize(Queue* pq)//有多少个数据
{
  assert(pq);
  int n = 0;
  QueueNode* cur = pq->head;
  while (cur)
  {
    n++;
    cur = cur->next;
  }
  return n;
}

quene.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.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);//取队尾的数据
int QueueSize(Queue* pq);//有多少个数据
bool QueueEmpty(Queue* pq);//判断队列是否为空