备案控制台
探索云世界
开发者社区 云计算 文章 正文

数据结构——栈和队列

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

栈

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

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

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

动态开辟在堆区，堆向上增长，递归次数过多会导致栈溢出


栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。


习题

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出

栈的顺序是（ ）。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA


B 先进后出


2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

C A1先入，再出1，然后入2，3，4，出4，3，2


   B先入1，2出2，入3，出3，入4，出4，出1


   D入1，2，3出3，入4，出4，出2，出1


结构体的创建

typedef int STDdtaTtype;
typedef struct Stcak
{
  STDdtaTtype* data;
  int top;
  int capacity;
}ST;

初始化 

void StackInit(ST* ps)
{
  assert(ps);
  ps->data = NULL;
  ps->capacity = ps->top = 0;
}

销毁开辟空间 

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

入栈 

void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1
{
  assert(ps);
  int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  if (ps->capacity == ps->top)//判断是否满了
  {
  STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity);
  if (tmp == NULL)
  {
    perror("realloc fail");
    exit(-1);
  }
  ps->data = tmp;
  ps->capacity = newcapacity;
  }
  ps->data[ps->top] = x;
  ps->top++;
}


出栈 

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

当前栈顶

STDdtaTtype StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->data[ps->top - 1];
}

判断栈是否为空 

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

统计个数 

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

力扣习题——有效的括号

3.png

20. 有效的括号 - 力扣（LeetCode）

4.png

当s指向左括号时，把该括号放入栈内

5.png6.png

入完栈之后s不等于左括号，s等于右括号，然后将栈内的元素一个个拿出来跟s所指括号比较，若能匹配成功，则进行下一轮比较，反之则直接返回false

7.png

typedef char STDdtaTtype;
typedef struct Stcak
{
  STDdtaTtype* data;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDdtaTtype x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
STDdtaTtype StackTop(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->data = NULL;
  ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
  assert(ps);
  free(ps->data);
  ps->capacity = ps->top = 0;
  ps->data = NULL;
}
void StackPush(ST* ps, STDdtaTtype x)//注意要看top的位置是0还是-1
{
  assert(ps);
  int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  if (ps->capacity == ps->top)//判断是否满了
  {
    STDdtaTtype* tmp = realloc(ps->data, sizeof(ps) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->data = tmp;
    ps->capacity = newcapacity;
  }
  ps->data[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}
STDdtaTtype StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->data[ps->top - 1];
}
bool StackEmpty(ST* ps)//判断是否为空栈
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}

把上面栈的函数都复制下来，进行括号匹配

bool isValid(char * s){
ST st;
StackInit(&st);
while(*s)
{
    if(*s=='['||*s=='{'||*s=='(')
    {
       StackPush(&st,*s);
    }
    else
    {
        if(StackEmpty(&st))//若栈内为空，直接返回false，这种情况如只S数组只有一个[
{ 
       StackDestory(&st);//防止内存泄漏
        return false;
}
       STDdtaTtype top=StackTop(&st);
       StackPop(&st);
        if(*s==']'&&top!='['
        ||*s=='}'&&top!='{'
        ||*s==')'&&top!='(')
        {
            return false;
        }
    }
    s++;
}
bool flag=(StackEmpty(&st));//若全部匹配则，栈内为空，若没有则不为空
StackDestory(&st);
return flag;
}

队列

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

FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头，一般用单链表实现队列，双向链表比较浪费

8.png

结构体的建立

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

初始化 

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

动态内存销毁 

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

入队

void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  assert(newnode);
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
  pq->head = pq->tail = newnode;
  }
  else
  {
  pq->tail->next = newnode;
  pq->tail = pq->tail->next;
  }
  pq->size++;
}


出队

void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }//如果只剩一个节点，单独处理，要不染当head遍历到tail时候，tail会成为野指针，这里要防止tail变为野指针
  else
  {
  QNode* cur = pq->head;
  pq->head = pq->head->next;
  free(cur);
  cur = NULL;
  }
  pq->size--;
}


提取数据

QDataType QueueFront(Queue* pq)//取头数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QDataType QueueBack(Queue* pq)//取尾数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

判断是否为空

bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head==NULL && pq->tail==NULL;
}

队内元素个数统计 

int QueueSize(Queue* pq)
{
  return pq->size;
}
关键词：
数据结构队列
数据结构栈
数据结构栈和队列
数据结构栈队列
jefcfxcg6xxjg
目录
相关文章
Kevin_17
|
22天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列（二）：队列
深入理解栈和队列（二）：队列
Kevin_17
35 0
阿森要自信
|
23天前
|
存储 算法 索引
【算法与数据结构】队列的实现详解
【算法与数据结构】队列的实现详解
阿森要自信
41 0
shark-chili
|
4天前
|
算法 索引
数据结构与算法-三种队列基础入门
数据结构与算法-三种队列基础入门
shark-chili
8 0
yma16
|
5天前
|
C语言
数据结构中顺序栈的进栈和出栈用C语言表示
数据结构中顺序栈的进栈和出栈用C语言表示
yma16
12 1
时雨h
|
15天前
|
存储 算法 调度
数据结构期末复习（3）栈和队列
数据结构期末复习（3）栈和队列
时雨h
19 0
阿森要自信
|
26天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
12 1
阿森要自信
|
26天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
22 0
阿森要自信
|
27天前
|
存储 缓存 算法
【算法与数据结构】栈的实现详解
【算法与数据结构】栈的实现详解
阿森要自信
19 0
游客i66wb7w7cg4tk
|
27天前
|
存储 算法 编译器
【数据结构】栈算法（算法原理+源码）
【数据结构】栈算法（算法原理+源码）
游客i66wb7w7cg4tk
16 0
【数据结构】栈算法（算法原理+源码）
修修修也
|
1月前
|
存储
【数据结构】什么是栈?
【数据结构】什么是栈?
修修修也
31 0
【数据结构】什么是栈?

热门文章

最新文章

  • 1
    数据结构期末复习（fengkao课堂）
  • 2
    python学习-函数模块，数据结构，字符串和列表（下）
  • 3
    【算法与数据结构】队列的实现详解
  • 4
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
  • 5
    【数据结构】八大排序之快速排序算法
  • 6
    【数据结构】C语言实现链队列(附完整运行代码)
  • 7
    深入理解栈和队列（二）：队列
  • 8
    【算法与数据结构】深入二叉树实现超详解（全源码优化）
  • 9
    【数据结构】什么是栈?
  • 10
    【数据结构】深入浅出理解链表中二级指针的应用
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【数据结构与算法】—— 手撕红黑树
    37
  • 3
    【排序算法】数据结构排序详解
    42
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
    43
  • 5
    【堆】数据结构堆的实现（万字详解）
    53
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    25
  • 7
    【双向链表】数据结构双向链表的实现
    21
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    34
  • 10
    数据结构——二叉树的链式结构
    36

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考