栈和队列（stack和queue）

2023-06-12 115

版权

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

简介： 栈和队列（stack和queue）

一、栈

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）

一、栈

1.1 什么是栈？

1.2 栈的相关操作

1.2.1 结构体变量的声明

1.2.2 栈的初始化

1.2.3 栈的销毁

1.2.4 元素入栈

1.2.5 元素出栈

1.2.6 取栈顶元素

1.2.7 求栈里面元素的数目

1.2.8 判断栈是否为空

1.3 栈的代码汇总

1.3.1 Stack.h

1.3.2 Stack.c

1.3.3 test.c

二、队列

2.1 什么是队列？

2.2 队列相关操作

2.2.1 结构体变量的声明

2.2.2 队列的初始化

2.2.3 队列的销毁

2.2.4 队列的插入

2.2.5 队列的删除

2.2.6 队列元素的数目

2.2.7 判断队列是否为空

2.2.8 取队列头部的元素

2.2.9 取队列尾部的元素

2.3 队列的代码汇总

2.3.1 Queue.h

2.3.2 Queue.c

2.3.3 test.c

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

栈和队列（stack和queue）

一、栈

1.1 什么是栈？

1.2 栈的相关操作

1.2.1 结构体变量的声明

1.2.2 栈的初始化

1.2.3 栈的销毁

1.2.4 元素入栈

1.2.5 元素出栈

1.2.6 取栈顶元素

1.2.7 求栈里面元素的数目

1.2.8 判断栈是否为空

1.3 栈的代码汇总

1.3.1 Stack.h

1.3.2 Stack.c

1.3.3 test.c

二、队列

2.1 什么是队列？

2.2 队列相关操作

2.2.1 结构体变量的声明

2.2.2 队列的初始化

2.2.3 队列的销毁

2.2.4 队列的插入

2.2.5 队列的删除

2.2.6 队列元素的数目

2.2.7 判断队列是否为空

2.2.8 取队列头部的元素

2.2.9 取队列尾部的元素

2.3 队列的代码汇总

2.3.1 Queue.h

2.3.2 Queue.c

2.3.3 test.c

热门文章

最新文章

相关课程

相关电子书