AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】第六站：栈和队列

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


一、栈

1.栈的概念和结构

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

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

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

2.栈的实现方案

对于这个栈，想必我们也不难想到他有两种实现的方案了，第一种方案是使用顺序表来实现，第二种方案是使用链表来实现

顺序表实现

如果采用顺序表来实现的话，由于只有在栈顶会出数据和入数据，所以栈顶就应该对应着数组的尾。

而这种方式，我们不难发现他是很优的，而且由于cpu的局部性原理，也是具有一定的优势的。因此我们发现栈是一种很适合使用顺序表实现的

链表来实现

如果采用链表来实现的话，我们可以选择使用单链表和带头双向循环链表。

如果我们使用单链表

我们这里又可以细分为栈顶在链表头和在链表尾

如下图所示是栈顶在链表尾部，这样的话我们显然可以得知他的效率是很低的

如果栈顶在链表头的话，这样就可以提升了效率，但是仍然没有顺序表更具有优势

而如果使用带头双向循环链表的话，确实也可以高效的实现栈，但是是没有顺序表具有优势的

3.栈的具体实现

栈的定义

根据上面的分析，我们决定采用顺序表来实现栈，使用顺序表又可以分为静态的和动态的。当然动态的性能是要优于静态的。我们使用动态顺序表

typedef int  STDateType;
typedef struct Stack
{
  STDateType* a;
  int top;
  int capacity;
}Stack;

栈的初始化

对于栈的初始化，与动态顺序表的初始化完全一样。初始为其分配四个数据的空间。然后让top和capacity分别置为0和4

//栈的初始化
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps->top = 0;
  ps->capacity = 4;
}

栈的销毁

由于这个栈的本质是一个顺序表，所以直接释放顺序表中指针所对应的那块空间即可

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

入栈

对于入栈，我们需要先检查容量，容量不够则扩容，然后直接尾插即可

//入栈
void StackPush(Stack* ps, STDateType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->top] = x;
  ps->top++;
}

出栈

对于出栈，我们得先确定栈内元素不为空，然后我们直接让top--即可

//出栈
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}

栈的个数

由于我们的top代表的就是栈的个数，所以直接返回即可

//栈的个数
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}

栈是否为空

对于判断栈是否为空，我们直接根据top的值即可判断

//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}

取出栈顶的元素

我们先确定栈不为空，然后直接返回栈顶元素即可

//取出栈顶的数据
STDateType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}

4.栈的完整代码

Stack.h

#pragma once
#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
#include<assert.h>
typedef int  STDateType;
typedef struct Stack
{
  STDateType* a;
  int top;
  int capacity;
}Stack;
//栈的初始化
void StackInit(Stack* ps);
//栈的销毁
void StackDestroy(Stack* ps);
//入栈
void StackPush(Stack* ps, STDateType x);
//出栈
void StackPop(Stack* ps);
//栈的个数
int StackSize(Stack* ps);
//栈是否为空
bool StackEmpty(Stack* ps);
//取出栈顶的数据
STDateType StackTop(Stack* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//栈的初始化
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps->top = 0;
  ps->capacity = 4;
}
//栈的销毁
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, STDateType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
//栈的个数
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
//取出栈顶的数据
STDateType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}

Test.c

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

5.有效的括号

题目链接：力扣

题目解析：对于这道题，最简单的方法就是使用一个栈来记录左括号，如果是左括号，则入栈，如果不是左括号，先取出栈顶的元素，并出栈。然后将栈顶元素与当前的字符进行比较。如果满足错误条件，则销毁栈后直接返回即可。

如果可以匹配，则直接让s++即可。最后当所有字符串遍历完成以后，然后根据栈是否为空，返回即可

typedef char STDateType;
typedef struct Stack
{
  STDateType* a;
  int top;
  int capacity;
}Stack;
//栈的初始化
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps->top = 0;
  ps->capacity = 4;
}
//栈的销毁
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, STDateType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
//出栈
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
//栈的个数
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
//取出栈顶的数据
STDateType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
bool isValid(char * s){
    Stack st;
    StackInit(&st);
    while(*s!='\0')
    {
        if( (*s=='(')||(*s=='[')||(*s=='{'))
        {
            StackPush(&st,*s);
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            char p=StackTop(&st);
            StackPop(&st);
            if( ((*s!=')')&&(p=='('))|| 
                ((*s!=']')&&(p=='['))||
                ((*s!='}')&&(p=='{')))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    bool ret =StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

二、队列

1.队列的概念及结构

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.队列的实现方案

对于队列的实现，我们仍然又两种方法可以选择，一种是链表形式，一种是顺序表形式

如果采用顺序表来实现的话，我们会发现头删操作时间复杂度较高。

如果采用链表来实现的话，我们发现找尾部结点的时间复杂度较高，但是我们可以多定义一个结点来随时知道尾部结点的地址。这样就可以优化掉找尾的时间复杂度。而且对于计算队列长度的话，我们也可以多定义一个变量size，我们在删除和插入数据的时候调整好size的大小。就可以优化掉计算队列长度的时间复杂度

这里我们也产生一个新的问题，对于单链表，能否多定义一个指针来控制尾部的地址，从而优化找尾的时间复杂度。

其实是不行的，对于尾插显然可以优化，但是对于尾删就不可以了。因为他需要找前一个结点的地址。

对于单链表我们也可以使用一个变量size，用来优化计算单链表长度的时间复杂度

综上所述，我们发现采用链表的结构是最优的。这个链表有一些不同的是，我们需要使用头尾两个指针以及一个size变量来进行优化，既然如此，那么我们就最好使用一个结构体来连接这些变量。否则传参的时候我们需要传三个以上的变量。

typedef int QDateType;
typedef struct QNode
{
  QDateType data;
  struct QNode* next;
}QNode;
typedef  struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;

3.队列的实现

1.初始化队列

//初始化队列
void QueueInit(Queue* q)
{
  assert(q);
  q->head = NULL;
  q->tail = NULL;
  q->size = 0;
}

如上代码所示，我们直接传结构体的地址就可以了。

2.队尾入数据

//申请一个结点
QNode* BuyQNode(QDateType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->next = NULL;
  newnode->data = x;
  return newnode;
}
//队尾入队列
void QueuePush(Queue* q, QDateType x)
{
  assert(q);
  QNode* newnode = BuyQNode(x);
  if (q->tail == NULL)
  {
    q->head = q->tail = newnode;
  }
  else
  {
    q->tail->next = newnode;
    q->tail = q->tail->next;
  }
  q->size++;
}

队尾入数据的话，与单链表的入数据思路是一致的，我们先申请一个结点，然后判断这个链表是否为空，如果为空，则特殊处理，否则正常尾插即可

3.队头出数据

//队头出队列
void QueuePop(Queue* q)
{
  assert(q);
  assert(q->head);
  QNode* first = q->head->next;
  free(q->head);
  q->head = first;
  q->size--;
  if (q->head == NULL)
  {
    q->tail = NULL;
  }
}

对于出数据，与单链表是一样的，但是我们需要特别注意尾指针，如果删了队列最后一个结点后队列为空，那么需要将尾结点置为空

4.获取头部尾部数据

//获取队列头部元素
QDateType QueueFront(Queue* q)
{
  assert(q);
  assert(q->head);
  return q->head->data;
}
//获取队列尾部元素
QDateType QueueBack(Queue* q)
{
  assert(q);
  assert(q->head);
  return q->tail->data;
}

对于这两个函数，基本思路是一样的，我们先判断链表不为空，然后直接返回数据即可

5.获取队列中的有效元素的个数

//获取队列中的有效元素个数
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}

对于这段代码，我们直接返回size即可

6.检测队列是否为空

//检测队列是否为空
bool QueueEmpty(Queue* q)
{
  assert(q);
  return q->head == NULL;
}

这段代码也很简单，直接返回这个判断条件即可

7.销毁队列

//销毁队列
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->head = q->tail = NULL;
  q->size = 0;
}

销毁队列的方法与单链表的销毁是一样的，我们需要注意的是，别忘记置空head和tail以及size。

4.队列实现的完整代码

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDateType;
typedef struct QNode
{
  QDateType data;
  struct QNode* next;
}QNode;
typedef  struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
//初始化队列
void QueueInit(Queue* q);
//队尾入队列
void QueuePush(Queue* q, QDateType x);
//队头出队列
void QueuePop(Queue* q);
//获取队列头部元素
QDateType QueueFront(Queue* q);
//获取队列尾部元素
QDateType QueueBack(Queue* q);
//获取队列中的有效元素个数
int QueueSize(Queue* q);
//检测队列是否为空
bool QueueEmpty(Queue* q);
//销毁队列
void QueueDestroy(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化队列
void QueueInit(Queue* q)
{
  assert(q);
  q->head = NULL;
  q->tail = NULL;
  q->size = 0;
}
//申请一个结点
QNode* BuyQNode(QDateType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->next = NULL;
  newnode->data = x;
  return newnode;
}
//队尾入队列
void QueuePush(Queue* q, QDateType x)
{
  assert(q);
  QNode* newnode = BuyQNode(x);
  if (q->tail == NULL)
  {
    q->head = q->tail = newnode;
  }
  else
  {
    q->tail->next = newnode;
    q->tail = q->tail->next;
  }
  q->size++;
}
//队头出队列
void QueuePop(Queue* q)
{
  assert(q);
  assert(q->head);
  QNode* first = q->head->next;
  free(q->head);
  q->head = first;
  q->size--;
  if (q->head == NULL)
  {
    q->tail = NULL;
  }
}
//获取队列头部元素
QDateType QueueFront(Queue* q)
{
  assert(q);
  assert(q->head);
  return q->head->data;
}
//获取队列尾部元素
QDateType QueueBack(Queue* q)
{
  assert(q);
  assert(q->head);
  return q->tail->data;
}
//获取队列中的有效元素个数
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
//检测队列是否为空
bool QueueEmpty(Queue* q)
{
  assert(q);
  return q->head == NULL;
}
//销毁队列
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->head = q->tail = NULL;
  q->size = 0;
}

Test.c

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

本期内容就到这里了

如果对你有帮助的话，不要忘记点赞加收藏哦！！！

关键词：
数据结构栈
数据结构队列
数据结构栈队列
数据结构栈和队列
青色忘川
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
137 9
那年春天
|
25天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
24 1
龙大吉
|
12天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
30 5
德国都芳最好
|
28天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
78 21
html的七十二变
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
31 2
dufadayang
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
50 4
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
21 1
星霜旅人
|
2月前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
22 1
白子寰
|
2月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
白子寰
18 0
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
39 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器