【数据结构初阶】一文详解顺序栈和链队列的基本操作（下）

2023-01-09 59

版权

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

简介： 【数据结构初阶】一文详解顺序栈和链队列的基本操作

1.队列的概念

队列是一种特殊的线性表，特殊在只能从一端进行插入操作，另一端进行删除操作，队列具有Fist In First Out的原则。

队尾：进行插入操作的一端，这个过程叫做入队列

队头：进行删除操作的一端，这个过程叫做出队列

抽号机：先来先服务，先给号码排队（涉及嵌入式）

2.队列的结构

队列我们采用链表实现：顺序表在满了要扩容，删完了后再入队列的时候还得扩容

链表的话，入队列就是尾插，定义一个尾指针。出队列就是头删，定义一个头指针

3.实现队列的基本操作

3-1结构体定义

typedef int QDateType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDateType val;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;

3-2队列的初始化

这里的链表队列我并没有带头，没有带头就要在入队列和出队列时有一点特殊情况的考虑

void QueueInit(Queue* ps)
{
  assert(ps);
  ps->head = ps->tail = NULL;
}

3-3入队列

相当于尾插，考虑特殊情况：队列为空的情况

//入队列：尾插
void QueuePush(Queue* ps,QDateType x)
{
  assert(ps);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->next = NULL;
  newnode->val = x;
  if (newnode == NULL)
  {
    perror("malloc fail.");
    exit(-1);
  }
  if (ps->tail == NULL)
  {
    ps->head = ps->tail = newnode;
  }
  else
  {
    ps->tail->next = newnode;
    ps->tail = ps->tail->next;
  }
}

3-4出队列

相当于头删，考虑特殊情况：只有一个结点的情况，出队列后要改变ps->tail

void QueuePop(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));
  if (ps->head->next == NULL)
  {
    free(ps->head);
    ps->head = ps->tail = NULL;
  }
  else
  {
    QueueNode* next = ps->head->next;
    free(ps->head);
    ps->head = next;
  } 
}

3-5取队头元素

QDateType QueueFront(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));
  return ps->head->val;
}

3-6取队尾元素

QDateType QueueBack(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));
  return ps->tail->val;
}

3-7队列判空

1. bool QueueEmpty(Queue* ps)
2. {
3.  assert(ps);
4.  return ps->tail == NULL;
5. }

3-8队列长度

int QueueSize(Queue* ps)
{
  assert(ps);
  int size = 0;
  QueueNode* cur = ps->head;
  while(cur)
  {
    ++size;
    cur = cur->next;
  }
  return size;
}

3-9队列销毁

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

4.源代码

4-1queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
void QueueInit(Queue* ps)
{
  assert(ps);
  ps->head = ps->tail = NULL;
}
void QueueDestory(Queue* ps)
{
  assert(ps);
  QueueNode* cur = ps->head;
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  ps->head = ps->tail = NULL;
}
//入队列：尾插
void QueuePush(Queue* ps,QDateType x)
{
  assert(ps);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->next = NULL;
  newnode->val = x;
  if (newnode == NULL)
  {
    perror("malloc fail.");
    exit(-1);
  }
  if (ps->tail == NULL)
  {
    ps->head = ps->tail = newnode;
  }
  else
  {
    ps->tail->next = newnode;
    ps->tail = ps->tail->next;
  }
}
void QueuePop(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));
  if (ps->head == ps->tail)
  {
    free(ps->head);
    ps->head = ps->tail = NULL;
  }
  else
  {
    QueueNode* next = ps->head->next;
    free(ps->head);
    ps->head = next;
  } 
}
QDateType QueueFront(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));
  return ps->head->val;
}
QDateType QueueBack(Queue* ps)
{
  assert(ps);
  assert(!QueueEmpty(ps));
  return ps->tail->val;
}
bool QueueEmpty(Queue* ps)
{
  assert(ps);
  return ps->tail == NULL;
}
int QueueSize(Queue* ps)
{
  assert(ps);
  int size = 0;
  QueueNode* cur = ps->head;
  while(cur)
  {
    ++size;
    cur = cur->next;
  }
  return size;
}

4.2queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDateType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDateType val;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
void QueueInit(Queue* ps);
void QueuePush(Queue* ps, QDateType x);
void QueuePop(Queue* ps);
QDateType QueueFront(Queue* ps);
QDateType QueueBack(Queue* ps);
bool QueueEmpty(Queue* ps);
int QueueSize(Queue* ps);
void QueueDestory(Queue* ps);

4.3test.c

#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);
  QDateType ret1 = QueueFront(&Q);
  printf("QueueFront:%d\n", ret1);
  QDateType ret2 = QueueBack(&Q);
  printf("QueueBack:%d\n", ret2);
  int size = QueueSize(&Q);
  printf("size：%d\n", size);
  while (!QueueEmpty(&Q))
  {
    printf("%d", QueueFront(&Q));
    QueuePop(&Q);
  }
  QueueDestory(&Q);
  return 0;
}