一、栈

1.1 什么是栈？

栈 (Stack)是一种线性存储结构，它具有如下特点：栈中的数据元素遵守”后进先出” (First In Last Out)的原则，简称FILO结构。限定只能在栈顶进行插入和删除操作。

栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。栈可以用动态数组的方式实现，也可以用链表来实现。以下是用动态数组的方式模拟实现栈。

1.2 栈的相关操作

1.2.1 结构体变量的声明

typedef int StackDataType;
typedef struct Stack
{
  //这里就是一个指向动态开辟内存的指针即可
  //和顺序表一个道理
  StackDataType* a;
  //top记录栈顶位置，top的初始值为0或者-1取决于
  //设计者设计top位置是栈顶元素的位置(top=-1)
  //还是栈顶元素位置的下一个(top=0)。
  int top;
  //capacity是栈的容量，容量不够就增容
  int capacity;
}ST;

1.2.2 栈的初始化

void STInit(ST* st)
{
  assert(st);
  //开辟空间
  st->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);
  if (st->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  st->capacity = 4;
  //st->top=0代表top是栈顶元素的下一个位置的下标而并非栈顶元素的下标
  st->top = 0;
}

1.2.3 栈的销毁

void STDestroy(ST* st)
{
  assert(st);
  free(st->a);
  st->a = NULL;
  st->capacity = 0;
  st->top = 0;
}

1.2.4 元素入栈

void STPush(ST* st, StackDataType x)
{
  assert(st);
  if (st->capacity == st->top)
  {
    //增容
    StackDataType* tmp = (StackDataType*)realloc(st->a, sizeof(StackDataType) * (st->capacity * 2));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    st->a = tmp;
    st->capacity *= 2;
  }
  //top位置是栈顶元素位置的下一个，所以直接把x入栈到top下标的位置
  st->a[st->top] = x;
  st->top++;
}

1.2.5 元素出栈

void STPop(ST* st)
{
  //出栈的条件之一是栈内必须有数据
  //所以不能为空
  assert(st && !STEmpty(st));
  //直接top--即可
  st->top--;
}

1.2.6 取栈顶元素

StackDataType STTop(ST* st)
{
  assert(st);
  //要取元素，栈不能为空
  assert(!STEmpty(st));
  //由于top是栈顶的下一个位置的下标，所以需要返回top-1位置的元素
  return st->a[st->top - 1];
}

1.2.7 求栈里面元素的数目

size_t STSize(ST* st)
{
  assert(st);
  //由于top是有0开始的，插入一个数据就+1
  //所以插入了多少个数据top就是多少，所以直接返回top的大小即可
  return st->top;
}

1.2.8 判断栈是否为空

bool STEmpty(ST* st)
{
  assert(st);
  //如果top==0，证明栈内无数据，
  //栈为空，st->top==0的逻辑结果true，直接返回即可
  return st->top == 0;
}

1.3 栈的代码汇总

1.3.1 Stack.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int StackDataType;
typedef struct Stack
{
  StackDataType* a;
  int top;
  int capacity;
}ST;
extern void STInit(ST* st);
extern void STDestroy(ST* st);
extern void STPush(ST* st, StackDataType x);
extern void STPop(ST* st);
extern StackDataType STTop(ST* st);
extern size_t STSize(ST* st);
extern bool STEmpty(ST* st);

1.3.2 Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void STInit(ST* st)
{
  assert(st);
  //开辟空间
  st->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);
  if (st->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  st->capacity = 4;
  //st->top=0代表top是栈顶元素的下一个的位置的下标而并非栈顶元素的下标
  st->top = 0;
}
void STDestroy(ST* st)
{
  assert(st);
  free(st->a);
  st->a = NULL;
  st->capacity = 0;
  st->top = 0;
}
void STPush(ST* st, StackDataType x)
{
  assert(st);
  if (st->capacity == st->top)
  {
    //增容
    StackDataType* tmp = (StackDataType*)realloc(st->a, sizeof(StackDataType) * (st->capacity * 2));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    st->a = tmp;
    st->capacity *= 2;
  }
  //top位置是栈顶元素位置的下一个，所以直接把x入栈到top下标的位置
  st->a[st->top] = x;
  st->top++;
}
void STPop(ST* st)
{
  assert(st && !STEmpty(st));
  //直接top--即可
  st->top--;
}
StackDataType STTop(ST* st)
{
  assert(st);
  //要取元素，栈不能为空
  assert(!STEmpty(st));
  //由于top是栈顶的下一个位置的下标，所以需要返回top-1位置的元素
  return st->a[st->top - 1];
}
size_t STSize(ST* st)
{
  assert(st);
  //由于top是有0开始的，插入一个数据就+1
  //所以插入了多少个数据top就是多少，所以直接返回top的大小即可
  return st->top;
}
bool STEmpty(ST* st)
{
  assert(st);
  //如果top==0，证明栈内无数据，
  //栈为空，st->top==0的逻辑结果true，直接返回即可
  return st->top == 0;
}

1.3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
int main()
{
  ST st;
  STInit(&st);
  STPush(&st, 1);
  STPush(&st, 2);
  STPush(&st, 3);
  STPush(&st, 4);
  STPush(&st, 5);
  while (!STEmpty(&st))
  {
    printf("%d ", STTop(&st));
    STPop(&st);
  }
  printf("\n");
  STDestroy(&st);
  return 0;
}

二、队列

2.1 什么是队列？

队列(Queue)也是一种线性的存储结构，它具有如下特点：队列中的数据元素遵守”先进先出” (First In First Out)的原则，简称FIFO结构。限定只能在队列的尾部进行插入数据，头部进行删除数据。

队列适合用单链表实现，因为单链表头删和尾插的时间复杂度是O(1)的，效率很高。

2.2 队列相关操作

2.2.1 结构体变量的声明

typedef int QNodeDataType;
//队列的每一个元素是一个结构体
typedef struct QueueNode
{
  //每一个结点内都存着下一个结点的指针(地址)
  struct QueueNode* next;
  //结点的有效数据
  QNodeDataType data;
}QNode;
typedef struct Queue
{
  //队列最好定义一个指向头节点的指针和
  //一个指向尾节点的指针，方便头删和尾插，提高效率
  QNode* head;
  QNode* tail;
  //记录队列一共有多少个结点，每插入一个结点就+1
  int size;
}Queue;

2.2.2 队列的初始化

void QueueInit(Queue* pq)
{
  assert(pq);
  //空队列的头和尾指针都要指向NULL
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}

2.2.3 队列的销毁

void QueueDestroy(Queue* pq)
{
  assert(pq);
  //由于每一个结点都是malloc出来的，所以
  //需要遍历逐一释放队列内的结点，防止内存泄露
  QNode* cur = pq->head;
  while (cur)
  {
    //先保存需要释放的结点del，释放后cur迭代地走下去
    //直到cur为空就全部释放完了
    QNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}

2.2.4 队列的插入

void QueuePush(Queue* pq, QNodeDataType x)
{
  assert(pq);
  //申请结点
  QNode* newNode = (QNode*)malloc(sizeof(QNode));
  if (newNode == NULL)
  {
    perror("");
    return;
  }
  newNode->data = x;
  newNode->next = NULL;
  //第一次插入时由于队列为空，所以pq->head和pq->tail
  //都为空，则应该直接赋值结点的结构体给p->head和pq->tail
  //如果直接pq->tail->next = newNode程序会崩的，因为pq->tail为空
  //不能访问
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newNode;
  }
  else
  {
    //插入到尾部
    pq->tail->next = newNode;
    //newNode更新为新的尾结点
    pq->tail = newNode;
  }
  //队列的数据数目+1
  pq->size++;
}

2.2.5 队列的删除

void QueuePop(Queue* pq)
{
  assert(pq);
  //删除的前提是不能队列为空
  assert(!QueueEmpty(pq));
  //如果只有一个结点的话，那删掉这个结点
  //同时把尾指针要置为NULL，不置空的话
  //尾指针就是一个野指针，存在越界访问的风险
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    //先保存下一个结点的地址，再释放当前的结点
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  //数目-1
  pq->size--;
}

2.2.6 队列元素的数目

int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

2.2.7 判断队列是否为空

bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}

2.2.8 取队列头部的元素

QNodeDataType QueueFront(Queue* pq)
{
  assert(pq);
  //取元素的前提是队列不能为空
  assert(!QueueEmpty(pq));
  return pq->head->data;
}

2.2.9 取队列尾部的元素

QNodeDataType QueueBack(Queue* pq)
{
  assert(pq);
  //取元素的前提是队列不能为空
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

2.3 队列的代码汇总

2.3.1 Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QNodeDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QNodeDataType data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
extern void QueueInit(Queue* pq);
extern void QueueDestroy(Queue* pq);
extern void QueuePush(Queue* pq, QNodeDataType x);
extern void QueuePop(Queue* pq);
extern int QueueSize(Queue* pq);
extern bool QueueEmpty(Queue* pq);
extern QNodeDataType QueueFront(Queue* pq);
extern QNodeDataType QueueBack(Queue* pq);

2.3.2 Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  //由于每一个结点都是malloc出来的，所以
  //需要遍历逐一释放队列内的结点，防止内存泄露
  QNode* cur = pq->head;
  while (cur)
  {
    //先保存需要释放的结点del，释放后cur迭代地走下去
    //直到cur为空就全部释放完了
    QNode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QNodeDataType x)
{
  assert(pq);
  //申请结点
  QNode* newNode = (QNode*)malloc(sizeof(QNode));
  if (newNode == NULL)
  {
    perror("");
    return;
  }
  newNode->data = x;
  newNode->next = NULL;
  //第一次插入时由于队列为空，所以pq->head和pq->tail
  //都为空，则应该直接赋值结点的结构体给p->head和pq->tail
  //如果直接pq->tail->next = newNode程序会崩的，因为pq->tail为空
  //不能访问
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newNode;
  }
  else
  {
    //插入到尾部
    pq->tail->next = newNode;
    //newNode更新为新的尾结点
    pq->tail = newNode;
  }
  //队列的数据数目+1
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  //删除的前提是不能队列为空
  assert(!QueueEmpty(pq));
  //如果只有一个结点的话，那删掉这个结点
  //同时把尾指针要置为NULL，不置空的话
  //尾指针就是一个野指针，存在越界访问的风险
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    //先保存下一个结点的地址，再释放当前的结点
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  //数目-1
  pq->size--;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}
QNodeDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QNodeDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

2.3.3 test.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);
  /*printf("%d ", QueueFront(&q));
  QueuePop(&q);
  printf("%d ", QueueFront(&q));
  QueuePop(&q);*/
  while (!QueueEmpty(&q))
  {
    printf("QueueFront:%d ", QueueFront(&q));
    printf("size = %d\n", QueueSize(&q));
    QueuePop(&q);
  }
  QueueDestroy(&q);
  return 0;
}

栈和队列（stack和queue）

一、栈