数据结构——栈与队列

目录一 栈1 什么是栈2 栈的基本操作a 基本框架​编辑b 入栈c出栈 获取栈顶元素二队列1什么是队列2队列的基本操作a基本框架b 入队列c 出队 获取队头元素三循环队列1什么是循环队列2 循环队列的基本操作a:基本框架b 入队 出队c 队列是否为空 队列是否为满d 获取队头元素 获取队尾元素一 栈1 什么是栈数据结构中的栈与计算机内存中的栈并不相同 这里不做详细解释栈是一种特殊的线性表 也就是说 栈是用来存放一连串的元素但特殊的是 栈只能从一端存储元素 并且后入栈的元素先出栈类似于将水倒入水杯中 杯顶区域的水 比 杯底区域的水先倒出2 栈的基本操作接下来 我们以整型为例利用链表来模拟实现栈的基本操作虽然数组也能够实现 但是数组的大小并不灵活 修改起来并不方便而链表就很好的解决了这个问题a 基本框架b 入栈c出栈 获取栈顶元素二队列1什么是队列队列是一种线性的数据结构 用来存放一连串的元素。队列 顾名思义 就是同种元素所排成的一条队伍 。特殊的是 先入队的元素后出队。类似于现实生活中的排队。2队列的基本操作同样 我们以整型为例 。利用链表来模拟实现队列a基本框架b 入队列c 出队 获取队头元素三循环队列1什么是循环队列循环队列 顾名思义 一个围成圈的队列。包含队列的所有基本操作与队列不同的是 ① 循环队列的大小一般是固定的 。② 循环队列的每一个空间可以重复利用 有利于节省空间。我们先思考一下 为了实现循环队列 入队与出队时 队头指针与队尾指针分别该如何操作。以front表示队头指针 rear表示队尾指针 k表示队列的长度既然涉及到循环 那么 front 就不能简单的1来让其移动 rear 也是同理。不难发现 front 与 rear 都是在 【 0 k 】这个区间内的 所以我们可以利用%来令front与rear移动。但是 这也会导致另一个问题 队列会出现一个空位 不论 队列中元素有多少 这个位置始终是空的 。不过利大于弊 通过牺牲一个空间来让后续的操作 变得简易 。2 循环队列的基本操作a:基本框架b 入队 出队c 队列是否为空 队列是否为满d 获取队头元素 获取队尾元素