栈和队列(跑路人笔记)

简介: 栈和队列(跑路人笔记)

前言🤪

老样子数据结构


注重逻辑

平时敲代码易忽略的点培养

特殊例子的想象

调试能力的培养

复习一下,省的学习时失去目标🤪

本次是栈和队列代码的实现和易错点的解析

感觉博主写的带劲的来点带劲的赞😁

(PS:栈和队列在代码实现方面其实很简单🤪,如果大家实现过顺序表链表之路的会发现这个简单的yap).

栈的代码实现🤪

还是讲个闲话,这里的栈的实现可以通过链表的形式或者通过顺序表的形式实现,不过通过栈的特性-----栈顶如栈顶出,我们不难发现栈使用顺序表的形式实现有很多优点,这个大家应该不用例子吧😜.


结构体类型

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;



a用来储存数据,top来记录栈顶,capacity用来保存容量大小


初始化

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



像之前完成顺序表一样我们可以用两种方式来进行这个栈实现的初始化不过有一说一还是在初始化时直接给一段空间会很舒服.而且方便未来的更改调试,模块化也比较到位,所以我推荐这样进行初始化,不过你感觉舒服最重要🤪.


摧毁栈🤪

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



顺序表的优点来了,在摧毁的时候真的很方便👍,直接free置空就好.记得置空=-=.


入栈

void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  // 满了->增容
  if (ps->top == ps->capacity)
  {
  STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
  if (tmp == NULL)
  {
    printf("realloc fail\n");
    exit(-1);
  }
  else
  {
    ps->a = tmp;
    ps->capacity *= 2;
  }
  }
  ps->a[ps->top] = x;
  ps->top++;
}



这里我没有把扩容功能单独包装,其实很简单因为只有一个地方用到了扩容功能,不过你要是想单独包装一下也是挺好的看着很简洁.不过博主这里就偷个懒了🤪.


这里用了==来判断是否增容当然也可以用>=但是top是一个一个涨的所以用==我个人认为更优可以比较直观一些😎.

没了=-=也是很简单的一个函数.


栈的推出

void StackPop(ST* ps)
{
  assert(ps);
  if (ps->top == 0)
  {
  printf("栈内已没有元素\n");
  return;
  }
  ps->top--;
}



直接用top–来使后一块空间可以被覆盖就好了.


其他琐碎接口🤓🤓🤓

STDataType StackTop(ST* ps)
{
  assert(ps);
  // 栈空了,调用Top,直接中止程序报错
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}



第一个接口,用来返回栈顶元素.

第二个接口,用来返回栈顶位置

第三个接口,测试栈是否为空, 为空就返回1,否则返回0

可以看到这三个函数简单的不能再简单了哪为啥还要专门弄个函数呢???

其实很简单这些代码虽然简单但是在别人使用时如果不看看你代码是很难直接写出这些程序的更不用说未来几万行代码时别痛苦的翻找你的代码时骂骂咧咧的嘴脸了🤣.

所以这些接口是非常非常重要的千万不可以图省事不写!!!⚠


队列的代码实现🤓

应该有一些人不知到队列是啥东西,其实很简单队列就跟我们排队一样数据从队尾进入从队头出去.

举个例子: 1 2 3 4 分别进入队列要想删除4就只能先删除1 2 3 最后才可以删除4.

希望上面这个例子大家可以看懂毕竟舒文的语言表达能力实在一般🤪.

也正因为队列的这个特点队列使用单链表是很香的🤪毕竟如果使用顺序表的话找队尾比较麻烦,使用带头循环双向链表的结构又很麻烦,所以使用单链表就刚刚好,又够用又方便👍


队列的结构类型

typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;



很标准的单链表结构哈.


初始化

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


初始化时我们先将头尾置空,以防野指针----野指针是非常恐怖的=-=一定要小心野指针.


摧毁

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



摧毁也是很经典的单链表形式一个节点一个节点的释放, 至于这个为啥用cur做临时变量进行而不是直接用pq->head呢?


入元素

// 队尾入
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  printf("malloc fail\n");
  exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
  pq->head = pq->tail = newnode;
  }
  else
  {
  pq->tail->next = newnode;
  pq->tail = newnode;
  }
}



队尾入的第一件事当然是检查是否需要扩容然后因为我们初始化时是将队头和队尾直接NULL对待了所以在扩容时我们就需要下一些功夫🤪.

在newnode开辟好了之后我们先将要输入的值输进去,并把newnode->next置空—这一步挺重要的如果不置空的话摧毁函数就用不了了然后newnode->next也变成了野指针非常恐怖✌🤪✌.

填入数据后我们就分开进行处理


image.png


这个if else语句就是为了判断的👍


1.队列内无元素,无元素时直接让头尾都指向newnode.

2. 有元素连接尾部并将尾指针指向newnode.


出元素

void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  // 1、一个
  // 2、多个
  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;
  }
}



删元素按照队列是队头出其实和单链表的头删很像不过多了个头指针和尾指针罢了=-=.

这里暴力了一些将空pq和空链表都断言了大家也可以温柔温柔😜.


琐碎的重要接口

再次强调这部分的接口虽然简单但是绝对不能不实现⚠


QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
  ++size;
  cur = cur->next;
  }
  return size;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}


第一个函数QueueFront返回头部元素

第二个QueueBack返回尾部元素

第三个QueueSize返回链表现在的大小

第四个QueueEmpty判断是否为空链表




相关文章
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
15 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
41 4
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
30 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
初步认识栈和队列
初步认识栈和队列
58 10
|
1月前
数据结构(栈与列队)
数据结构(栈与列队)
17 1
|
1月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
44 3

热门文章

最新文章