数据结构与算法-【栈与队列】

导语

栈是限定仅在表尾进行插入和删除操作的线性表
队列是只允许在一端进行插入操作而在另一端进行删除操作的线性表

一.栈

1.栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表
栈 是先进后出的线性表
栈的插入操作被称为进栈
栈的删除操作被称为出栈
在这里插入图片描述

2.顺序栈

顺序栈其实是线性表的顺序存储结构的简化，顺序栈的大小是固定的，因为数组的大小是固定的

进栈

在这里插入图片描述

出栈

在这里插入图片描述

3.链栈

链栈的大小是可变的，因为链式存储结构的缘故

进栈

在这里插入图片描述

出栈

在这里插入图片描述

4.递归问题

把一个直接调用自己或者通过一系列的调用语句间接的调用自己的函数，称为递归函数
必须至少有一个条件，满足时递归不再进行！

原理：

在这里插入图片描述

5.栈的应用-四则运算表达式求值

后缀表达式计算结果在这里插入图片描述

中缀表达式计算结果

在这里插入图片描述

二.队列

1.队列的定义

队列是只允许在一端进行插入操作而在另一端进行删除操作的线性表
特性：先进先出
在这里插入图片描述

2.队列的抽象数据类型

在这里插入图片描述

3.队列循环（顺序存储结构）

普通的队列不适用顺序存储结构的实现，因为数组的长度是固定的，如图
在这里插入图片描述

循环队列

我们把队列的这种头尾相接的顺序存储结构称为循环队列

4.队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它称为链队列
在这里插入图片描述
在这里插入图片描述

入队操作

在这里插入图片描述

出队操作

在这里插入图片描述

三.总结

在这里插入图片描述

版权声明：本文为xiongwen_li原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。