栈和队列的实现(详解+图解!文末附完整代码)

简介: 栈和队列的实现(详解+图解!文末附完整代码)

栈的基本概念

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

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。

出栈和入栈的操作如下:

他们都只能从栈顶进行出栈和进栈操作,所以栈要遵守先进后出的原则

栈的先进先出原则如下:

栈的实现

栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。所以我们在这里选择用数组来实现栈。

数组栈的结构图:

下面我们就用数组来是具体实现栈的增删查改等操作

头文件如下:

#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<stdlib.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);
创建栈

首先我们在这里将int作为本次栈的数据类型

我们还要定义一个结构体里面有数组,栈顶元素的下标的+1和栈的容量(栈里面的最多元素个数)

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // 
  int capacity;  //  
}Stack;
栈的初始化

栈的初始化就比较简单了,直接将top和容量置为0,并且把数组置为空

void StackInit(Stack* ps)
{
  assert(ps);
  ps->top = 0;
  ps->capacity = 0;
  ps->a = NULL;
}
栈的销毁

栈的销毁同样很简单,将数组free掉,防止出现野指针,同时置空,然后容量和栈顶元素下标置为0

void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
判断栈是否为空

在后面的增删查改等操作我们需要断言,为了增加代码的可读性,我们直接写一个函数 ,更加容易理解,如果栈顶元素下标为0,那么这个栈就为空 ,所以直接return top等于 0这个表达式的值,为空则返回 1,不为空则返回0

int StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
数据进栈

数据进栈是从栈顶入,我们首先要判断这个 栈是否已满,如果满了的话那么栈顶的下标就和容量相等,对于top和capacity的不理解的可以看这个图,top的意思如下图:

当capacity和top相等时其实是有两种情况的,一种时为空,另一种是栈满,,我们在这里就用一个三目操作符,如果为0,就将capacity初始化为4,否则将capacity的原来的值乘2,然后动态开辟realloc一块新的空间,大小就是newcapacity,这样我们就完成了扩容

然后我们将新空间temp给数组a

最后直接把插入的数据data给a[top],同时top++

void StackPush(Stack* ps, STDataType data)
{
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* temp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
    if (temp == NULL)
    {
      perror("realloc");
      return;
    }
    ps->capacity = newcapacity;
    ps->a = temp;
  }
  ps->a[ps->top] = data;
  ps->top++;
}
数据出栈

出栈及其简单,直接先判断栈是否为空,然后将top–即可

void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
获取栈顶元素

栈顶元素的下标其实就是top-1,所以直接返回a[top-1]

STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
获取栈内的元素个数

栈内元素个数就是top的值,栈为空top为0

int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}

栈的实现就完成了,完整代码如下:

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;    // ջ
  int capacity;  //  
}Stack;
void StackInit(Stack* ps)
{
  assert(ps);
  ps->top = 0;
  ps->capacity = 0;
  ps->a = NULL;
}
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
int StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
void StackPush(Stack* ps, STDataType data)
{
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* temp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
    if (temp == NULL)
    {
      perror("realloc");
      return;
    }
    ps->capacity = newcapacity;
    ps->a = temp;
  }
  ps->a[ps->top] = data;
  ps->top++;
}
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 - 1];
}
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}

队列

栈的基本概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)

入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头

队列的实现

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

这里我们就用列表的结构来实现队列

头文件如下:

注意,这里我们定义了两个结构体,,第一个结构体其实只是链表的结构,里面有一个next一个data,第二个则是队列的结构,一个队头(出数据)指针,一个队尾指针(进数据),还有一个队列的大小

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<ctype.h>
// 链式结构:表示队列 
typedef int QDataType;
typedef struct QListNode
{
  struct QListNode* next;
  QDataType data;
}QNode;
// 队列的结构 
typedef struct Queue
{
  QDataType size;
  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);
队列的初始化

初始目前以及是熟能生巧了,很简单,size置为0,头尾指针置为空即可

void QueueInit(Queue* q)
{
  assert(q);
  q->size = 0;
  q->front = q->rear = NULL;
}
队列的销毁

队列的销毁我们需要花点功夫理解一下:

因为队列有多个节点,全部都要free掉 ,不然就可能会出现野指针的问题,所以我们在这里用一个while循环,将cur置为头指针,将next置为cur的next,这样当前cur的next就不会丢失。首先我们把cur给free掉,然后将cur置为next继续操作,直到cur为空,然后将front和rear置为空,size置为0即可。

void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->front = q->rear = NULL;
  q->size = 0;
}
判断队列是否为空

和栈一样,提高代码的可读性,如果size=0,其实队列就为空,但是头尾指针都为空时也可以,为空时返回1,不为空时返回0

int QueueEmpty(Queue* q)
{
  assert(q);
  return q->front == NULL && q->rear == NULL;
  /*return q->size == 0;*/
}
队列数据插入

要插入一个数据我们首先要做的就是开辟有一个新的链表节点,然后将他的next置为空,data置为你要插入的数据

插入数据分为两种情况,链表为空和不为空

链表为空时直接将front和rear置为新节点newnode同时size++

链表不为空时就将front的next置为newnode,rear置为newnode同时size++

void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->rear == NULL)
  {
    assert(q->front == NULL);
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->next = newnode;
    q->rear = newnode;
  }
  q->size++;
}
队列数据删除

队列的删除我们就要判断队列是否为空,为空就不能删除了

同样的有两种情况:

链表只有一个节点时直接将头尾指针都置为空即可,size–

链表有多个节点时就将front的next置为front,size–

void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  if (q->rear == q->front)
  {
    free(q->front);
    q->front = q->rear = NULL;
  }
  else
  {
    QNode* next = q->front->next;
    free(q->front);
    q->front = next;
  }
  q->size--;
}
获取队头数据

获取队头的元素 ,直接返回头指针的data即可

QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->front->data;
}
获取队尾数据

获取队尾元素 同样简单,直接返回rear的data即可

QDataType QueueBack(Queue* q)
{
  assert(q);
  return q->rear->data;
}
求队列元素个数

直接返回size的值即可

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

队列的实现就完成了

完整代码如下:

void QueueInit(Queue* q)
{
  assert(q);
  q->size = 0;
  q->front = 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 = q->rear = NULL;
  q->size = 0;
}
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->front == NULL && q->rear == NULL;
  /*return q->size == 0;*/
}
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->rear == NULL)
  {
    assert(q->front == NULL);
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->next = newnode;
    q->rear = newnode;
  }
  q->size++;
}
void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  //һڵʱ
  if (q->rear == q->front)
  {
    free(q->front);
    q->front = q->rear = NULL;
  }
  //ڵ
  else
  {
    QNode* next = q->front->next;
    free(q->front);
    q->front = next;
  }
  q->size--;
}
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->front->data;
}
QDataType QueueBack(Queue* q)
{
  assert(q);
  return q->rear->data;
}
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}

好了,今天的分享到这里就结束了,谢谢大家的支持!

相关文章
|
1天前
|
存储
【数据结构】队列(Queue)的实现 -- 详解
【数据结构】队列(Queue)的实现 -- 详解
|
1天前
|
存储
【数据结构】栈(Stack)的实现 -- 详解
【数据结构】栈(Stack)的实现 -- 详解
|
1天前
|
存储 算法 搜索推荐
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(下)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
20 1
|
1天前
|
算法 编译器
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(中)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
17 4
|
1天前
|
存储 算法 搜索推荐
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(上)
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)
20 6
|
1天前
|
机器学习/深度学习 算法 分布式数据库
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码(下)
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码
8 1
|
2天前
|
算法
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码(上)
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码
10 1
|
2天前
|
机器学习/深度学习 存储 算法
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)(下)
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)
4 0
|
2天前
|
算法 前端开发 C语言
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)(上)
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)
11 0
|
2天前
|
缓存 算法 C语言
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)
4 0