数据结构------栈(Stack)和队列(Queue)

简介: 数据结构------栈(Stack)和队列(Queue)

也是好久没写博客了,那今天就回归一下,写一篇数据结构的博客吧。今天要写的是栈和队列,也是数据结构中比较基础的知识。那么下面开始今天要写的博客了。


喜欢就点个赞吧。


栈(Stack)

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


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


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


简单描述栈的特点:栈数据的增删都是在一头进行,即在栈顶


那栈又该如何创建与使用呢?他的原理又是怎样的,这里我们就用C语言实现一下。


我们这里就要想这个栈是要用数组来实现还是用链表来实现呢?其实我们可以从其功能开始思考,这两者哪个更好去实现栈的功能,而且效率较高,其实说到这里,很多人可能已经有了结果,其实要说简洁与效率数组更适合来做栈。那么我们下面就来完成一下这个代码完成一个栈。


这里先给头文件因为其中有typedef来命名的类型,以免各位佬看得迷惑。


头文件


这里解释一下DataType是各位做栈时储存数据的类型,需要改变时只需要在头文件里改动一下即可,例如你想变成char类型的数据,即可将typedef int DataType; 改为 typedef char DataType;

然后栈的结构体我们就用ST来简化方便写代码。

然后top为栈的数据个数,capacity就表示栈的容量

 

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int DataType;
 
typedef struct Stack
{
  DataType* a;
  int top;
  int capacity;
  
}ST;
 
 
void StackInit(ST* ps);
void StackDestory(ST* ps);
// 入栈
void StackPush(ST* ps, DataType x);
// 出栈
void StackPop(ST* ps);
DataType StackTop(ST* ps);
 
int StackSize(ST* ps);
bool StackEmpty(ST* ps);


栈的格式化

void StackInit(ST* ps)
{
  assret(ps);
  ps->a = (DataType)mallco(4 * (sizeof(DataType)));
  if (ps->a == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  ps->capacity = 4;
  ps->top = 0;
 
}


先将数组a  mallco出四个数据的大小,然后将容量capacity改为4.


栈的销毁

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

使用完栈后进行销毁得函数,防止内存泄露。 及时free掉,然后将a指向NULL。


入栈

void StackPush(ST* ps, DataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    DataType* tem = (DataType*)recalloc(ps->a, 2*ps->capacity*sizeof(DataType));
    if (tem == NULL)
    {
      printf("racallco fail\n");
    }
    else
    {
      ps->a = tem;
      ps->capacity = 2 * ps->capacity;
    }
 
  }
 
    ps->a[ps->top] = x;
    ps->top++;
  
}
 


第一个if,先判断数组a是否还有空间入栈,如果满了就进行recallco增容即可增容我们现在时增容两倍较为合适,recallco的用法在前面动态内存创建的文章已经讲过了。所以现在就不多解释了。入栈后记得将top++一下 。


出栈

void StackPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
 
  
  ps->top--;
}


这里就比较简单粗暴将top--,即可将原本栈顶得书局给屏蔽即可。


求栈的长度和判断栈是否为空

int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
 
 
bool StackEmpty(ST* ps)
{
  assert(ps);
 
  return ps->top == 0;
}

接下来我们就来看看队列


队列(Queue)

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

 

队列的特点:队列与栈的不同是他是在一头进行增数据,一头删数据,而栈数据的增删都是在一头。


然后我们思考一下队列的功能实现是要数组好还是链表好呢,这么一想是不是马上就发现了,如果们还是用数组来实现的话,那么其出队列的时间复杂度为O(N),那么效率太低了,而链表实现的话则是O(1),显而易队列还是用链表实现较好。


下面就是队列函数的实现了。

还是先给大家看看头文件

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
 
typedef int Type;
 
typedef struct Queuenode 
{
  Type* date;
  struct Queue* next;
 
}Node;
 
 
typedef struct Queue
{
  Node* head;
  Node* tail;
}Queue;
 
 
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
 
// 队尾入
void QueuePush(Queue* pq, Type x);
// 队头出
void QueuePop(Queue* pq);
 


这里解释一下为什么创建了两个结构体 ,因为其中一个作为链表的节点而另一个队列结构体。队列的结构体我们只需要要一个队头和队尾。


队列的格式化

 

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

很简单将队头和队尾指向空NULL即可。


队列的销毁

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


这里我们运用一个while循环,创建一个辅助指针来保存节点的下一个。不断free 掉即可。

注意要将队头和队尾指空NULL。


进队

 

void QueuePush(Queue* pq, Type x)
{
  assert(pq);
  Node* new = (Node*)mallco(sizeof(Node));
  if (new == NULL)
  {
    printf("mallco fail\n");
  }
  new->date = x;
  new->next = NULL;
  if (pq->tail = NULL)
  {
    pq->tail = new;
        pq->head = new;
  }
 
 
  else
  {
    pq->tail->next = new;
    pq->tail = new;
 
  }
 
}


我们mallco一个空间,作为进队的一个节点,然后对节点进行赋值,然后对链表进行尾插就完成了一半了。


需要注意的是记得把原来的tail的next 指向新节点,也要把tail改为 新节点,因为尾插后new就为最后的节点也就是尾了。注意当前有没有节点那将head和tail至为new即可。

出队

void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }
 
 
  Node* next = pq->head->next;
  free(pq->head);
  pq->head = next;
 
 
 
}


这里也是根据队列的删数据特点,这里的出队就是头删了,我们先把head的next保存住,然后free掉head,再然后让next作为新的头。

 


今天就结束了,希望您能喜欢这篇文章。


目录
相关文章
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
14天前
数据结构(栈与列队)
数据结构(栈与列队)
15 1
|
18天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
54 1
|
15天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
12 0
|
27天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
84 64
|
20天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
20天前
初步认识栈和队列
初步认识栈和队列
47 10
|
2月前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
|
20天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
34 3
|
21天前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
26 2