队列精华总结

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int queuedata;
typedef struct queuenode
{
  struct queuenode*next;
  queuedata data;
}qnode;
//定义一个结构体，需要有一个头节点，和尾节点
typedef struct queue
{
  qnode*head;
  qnode*tail;
}queue;
//我们需要初始化一下
//我们可以需要用带哨兵位的头，这个主要是解决二级指针的问题
void queueinit(queue* pq);
//销毁,动态开辟必备，否则内存泄露
void queuedestroy(queue*pq);
//他的push是在队尾入，出是在队头出
void queuepush(queue*pq, queuedata x);
//队头出
void queuepop(queue*pq);
//取的是队头的数据
queuedata  queuefront(queue*pq);
//取队尾的数据
queuedata queueback(queue*pq);
//计算有多少个数据
int queuesize(queue*pq);
//对这个队列进行判空 
bool queueempty(queue*pq);

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
void queueinit(queue* pq)//传过来的是结构体的指针，所以我们传一级就可以了
{
  assert(pq);
  pq->head=pq->tail=NULL;//都初始化为空//但我们在单链表中不加tail这个尾巴节点，
                         //因为tail可以解决尾插，但是解决不了尾删,就很麻烦
}
//队尾入
void queuepush(queue*pq, queuedata x)
{
  assert(pq);
  //我们要入数据，一开始tail和head的都是空的
  qnode*newnode = (qnode*)malloc(sizeof(qnode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)//假如说尾巴也是空，就没办法把newnode插进去，也就是说还没有节点，
  {
    pq->head = pq->tail = newnode;//那么他们就是指向的是同一个，所以这个newnode既是头也是尾
  }
//否则，我们就插入一个节点，就链接一个节点，将tail指向他
  else
  {
    pq->tail->next = newnode;//把尾巴的next指向他，进行链接，头一直不变，尾巴在变多
    pq->tail= newnode;//
  }
}
//队头出，相当于头删
void queuepop(queue*pq)
{
  assert(pq);//指针不为空
  assert(pq->head);//链表为空就错了
  //一个节点
  if (pq->head->next == NULL)//即只有一个节点
  {
    free(pq->head);
    pq->head = pq->head = NULL;//释放掉之后，把他们都置空
  }
  //多个节点
  else
  {
    qnode*next = pq->head->next;//要保存住下一个节点，否则就找不到他了
    free(pq->head);//head不用置空
    pq->head = next;//head要指向新的节点
    //假如到最后都删除完了，tail就变成一个野指针
  }
}
bool queueempty(queue*pq)
{
  assert(pq);
  return pq->head == NULL;//假如说他为空就是真，就是没有节点了，假如说他不为空就为假，用来后面打印判断用
}
//取队头的数据
queuedata  queuefront(queue*pq)
{
  assert(pq);
  assert(pq->head);//头也不能为空
  return pq->head->data;
}
//取队尾的数据
queuedata  queueback(queue*pq)
{
  assert(pq);
  assert(pq->head);//头也不能为空
  return pq->tail->data;
}
int queuesize(queue*pq)
{
  assert(pq);
  int sz = 0;
  qnode*cur = pq->head;
  while (cur)//不为空才是队的，假如说是不等于tail的话就会少算一个
  {
    ++sz;
    cur = cur->next;
  }
  return sz;
}
void queuedestroy(queue*pq)
{
  assert(pq);
  qnode*cur = pq->head;
  while (cur)
  {
    qnode*next = cur->next;//要找到cur的下一个，否则就找不到下一个节点的 位置了
    //再free掉
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;//删除完后，再把head和tail置成空
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
int main()
{
  queue q;
  queueinit(&q);
  queuepush(&q, 1);
  queuepush(&q, 2);
  queuepush(&q, 3);
  queuepush(&q, 4);
  queuepush(&q, 5);
  queuepush(&q, 6);
  while (!queueempty(&q))//用我们写的函数来作为循环判断的条件，而不用自己写的东西，保证准确性
  {
    printf("%d ", queuefront(&q));
    //再删掉对头的数据
    queuepop(&q);
  }
  queuedestroy(&q);
  return 0;
}