【数据结构】—手把手带你用C语言实现栈和队列（超详细！）-阿里云开发者社区

后进先出—栈

什么是栈？

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

什么是后进先出？

一图让你明白~

栈的实现？

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。但是由于数组是在定义完后对于空间是固定的，因此如果单纯用数组实现，如果申请空间过大会浪费空间，太小又会造成空间不够的问题，因此，本文采用支持动态增长的栈，也就是动态开辟空间的方法。

对此，我们先了解一下咱们栈的操作

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈实现需要设置的参数？

由于咱们要实现的是动态扩容因此定义如下：

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
  STDataType* _a;
  int _top;   // 栈顶
  int _capacity;  // 容量 
}Stack;

此处对于相关栈所定义的元素进行解释：

1、 STDataType* _a 作为动态扩容的作用。

2、int _top 作为记录栈顶位置的作用。

3、int _capacity 作为记录栈容量的作用。

啥意思呢？

一图让你明白~

要实现的功能？

同我们之前所学的链表、线性表一样，需要实现基本的增、删、查、改！但是需要注意的是，我们的查与修只能在固定的一端进行！而不能进行改的操作！对此我们写出相应的接口函数。
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

栈的C语言代码实现

初始化

void StackInit(Stack* ps)
{
  assert(ps);
  ps->_a = NULL;
  ps->_capacity = 0;
  ps->_top = -1;
}

注意：解释一下为什么这里top要设置成-1，主要是因为后续的操作中，比如：判空的操作的差异、在入栈时操作的差异，当然，top也可以设置成0，但后续的操作会有所差异。

入栈

void StackPush(Stack* ps, STDataType data)
{
  assert(ps);
  if (ps->_capacity - 1 == ps->_top)//匹配上初始化top=-1
  {
    int newcap = ps->_capacity == 0 ? MAX : ps->_capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->_a, newcap*sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->_capacity = newcap;
    ps->_a = tmp;
  }
  ps->_a[++ps->_top] = data;
}

入栈时首先判断空间是否足够，如果不够则扩容，够则直接入栈

判空

int StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->_top==-1;
}

出栈

void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->_top--;
}

取栈顶元素

void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->_top--;
}

计算栈内数据个数

int StackSize(Stack* ps)
{
  assert(ps);
  return ps->_top+1;
}

销毁栈

void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->_a);
  ps->_a = NULL;
}

栈的整体代码

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#define MAX 4
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
  STDataType* _a;
  int _top;   // 栈顶
  int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

函数实现

#include "stack.h"
void StackInit(Stack* ps)
{
  assert(ps);
  ps->_a = NULL;
  ps->_capacity = 0;
  ps->_top = -1;
}
void StackPush(Stack* ps, STDataType data)
{
  assert(ps);
  if (ps->_capacity - 1 == ps->_top)
  {
    int newcap = ps->_capacity == 0 ? MAX : ps->_capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->_a, newcap*sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->_capacity = newcap;
    ps->_a = tmp;
  }
  ps->_a[++ps->_top] = data;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->_top--;
}
STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->_a[ps->_top];
}
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->_top+1;
}
int StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->_top==-1;
}
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->_a);
  ps->_a = NULL;
}

测试用例

#include"stack.h"
void test()
{
  Stack st;
  StackInit(&st);
  StackPush(&st, 1);
  StackPush(&st, 2);
  StackPush(&st, 3);
  StackPop(&st);
  StackPush(&st, 4);
  StackPush(&st, 5);
  printf("%d\n", StackSize(&st));
  while (!StackEmpty(&st))
  {
    printf("%d ", StackTop(&st));
    StackPop(&st);
  }
  printf("\n%d\n", StackSize(&st));
  StackDestroy(&st);
}
int main()
{
  test();
  return 0;
}

测试结果：

先进先出—队列

什么是队列？

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头。

什么是先进先出？

相信在前面了解过后进先出的你应该有一定的概念了，一图让你明白~

队列的实现？

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

队列的实现需要设置的参数？

根据链表的定义如下：

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
  struct QListNode* _next;
  QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
  QNode* _front;
  QNode* _rear;
}Queue;

注意：QNode是基本的链表结构，而在QNode的基础上建立的Queue是作为真正的队列的结构，其中 _front 是作为记录队头位置的一个指针，而相应的 _rear 是作为记录队尾位置的一个指针。

一图让你明了~

要实现的功能？

同我们之前所学的链表、线性表一样，需要实现基本的增、删、查、改！但是需要注意的是，增的操作在一端进行，而删的操作在另外一端进行，并且同栈一样不能进行改的操作！对此我们写出相应的接口函数。

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

队列的C语言实现

初始化

void QueueInit(Queue* q)
{
  assert(q);
  q->_front = NULL;
  q->_rear = NULL;
}

你可能有个问题？为什么需要将两个指针都置空呢？初始化指针是一方面，而最主要的是为了让两个指针在最开始都指向同一个位置，然后头指针（也就是front）是只有在出队时才会移动的！尾指针（也就是rear）是只有在出队时才会移动的！这也是后续判空等操作的关键。

入队列

void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->_next = NULL;
  newnode->_data = data;
  if (q->_rear == NULL)
  {
    assert(q->_front == NULL);
    q->_front = q->_rear = newnode;
  }
  else
  {
    q->_rear->_next = newnode;
    q->_rear = newnode;
  }
}

入队列时需要判断头、尾指针是否为都为空，以此来确定是在头部插入还是在尾部插入。

判空

int QueueEmpty(Queue* q)
{
  assert(q);
  return q->_front==NULL&&q->_rear==NULL;
}

出队列

void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  if (q->_front == q->_rear)//一个节点
  {
    free(q->_front);
    q->_front = NULL;
    q->_rear = NULL;
  }
  else
  {
    QNode* next = q->_front->_next;
    free(q->_front);
    q->_front = next;
  }
}

取头节点元素

QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  return q->_front->_data;
}

计算队列内数据个数

int QueueSize(Queue* q)
{
  QNode* cur = q->_front;
  int size = 0;
  if (cur != NULL)
  {
    size++;
    while (cur != q->_rear)
    {
      size++;
      cur = cur->_next;
    }
  } 
    return size;
}

销毁队列

void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->_front;
  while (cur)
  {
    QNode* next = cur->_next;
    free(cur);
    cur = next;
  }
  q->_front = NULL;
  q->_rear = NULL;
}

队列的整体代码

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
  struct QListNode* _next;
  QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
  QNode* _front;
  QNode* _rear;
}Queue;
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

函数实现

#include "queue.h"
void QueueInit(Queue* q)
{
  assert(q);
  q->_front = NULL;
  q->_rear = NULL;
}
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->_next = NULL;
  newnode->_data = data;
  if (q->_rear == NULL)
  {
    assert(q->_front == NULL);
    q->_front = q->_rear = newnode;
  }
  else
  {
    q->_rear->_next = newnode;
    q->_rear = newnode;
  }
}
void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  if (q->_front == q->_rear)//一个节点
  {
    free(q->_front);
    q->_front = NULL;
    q->_rear = NULL;
  }
  else
  {
    QNode* next = q->_front->_next;
    free(q->_front);
    q->_front = next;
  }
}
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  return q->_front->_data;
}
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(&q));
  return q->_rear->_data;
}
int QueueSize(Queue* q)
{
  QNode* cur = q->_front;
  int size = 0;
  if (cur != NULL)
  {
    size++;
    while (cur != q->_rear)
    {
      size++;
      cur = cur->_next;
    }
  } 
    return size;
}
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->_front==NULL&&q->_rear==NULL;
}
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->_front;
  while (cur)
  {
    QNode* next = cur->_next;
    free(cur);
    cur = next;
  }
  q->_front = NULL;
  q->_rear = NULL;
}1. #i

测试用例

#include"queue.h"
void test()
{
  Queue qu;
  QueueInit(&qu);
  QueuePush(&qu, 1);
  QueuePush(&qu, 2);
  printf("%d\n", QueueBack(&qu));
  QueuePush(&qu, 3);
  QueuePush(&qu, 4);
  printf("%d\n", QueueSize(&qu));
  while(!QueueEmpty(&qu))
  {
    printf("%d ", QueueFront(&qu));
    QueuePop(&qu);
  }
  printf("\n%d\n", QueueSize(&qu));
  QueueDestroy(&qu);
}
int main()
{
  test();
  return 0;
}

测试结果：

感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！

【数据结构】—手把手带你用C语言实现栈和队列（超详细！）

后进先出—栈

什么是栈？

什么是后进先出？

栈的实现？

栈实现需要设置的参数 ？

要实现的功能？

栈的C语言代码实现

初始化

入栈

判空

出栈

取栈顶元素

计算栈内数据个数

销毁栈

栈的整体代码

头文件

函数实现

测试用例

先进先出—队列

什么是队列？

什么是先进先出？

队列的实现？

队列的实现需要设置的参数？

要实现的功能？

队列的C语言实现

初始化

入队列

判空

出队列

取头节点元素

计算队列内数据个数

销毁队列

队列的整体代码

头文件

函数实现

测试用例

热门文章

最新文章

相关课程

相关电子书

栈实现需要设置的参数？