栈和队列的逻辑结构与线性表相同,其特点在于运算有所限制(运算受限的线性表),栈操作按照后进先出(LIFO)的规则,队列按先进先出(FIFO)的规则。

通过访问它的一端来实现数据存储与检索的线性结构。

进行插入和删除操作的一端称为栈顶(Top),另一端称为栈底(Bottom),不包含数据元素的栈,称为空栈。

初始化栈->判断栈是否为空->入栈(Push)->出栈(Pop)->读取栈顶元素

初始化栈:创建一个空栈。

判断栈是否为空:为空是返回true(真),否则false(假)

入栈:将元素加入栈顶,并更新栈顶指针。

出栈:将栈顶元素删除,并更新栈顶指针。

读栈元素:返回栈顶元素的值,不更新指针。

顺序存储(顺序栈):

用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时指针指示栈顶元素的位置。这种存储方式下,栈的空间容量是有限的,当元素入栈时,需要判断是否栈满,如栈满,则不能入栈。

链式存储(链栈):

栈中元素的插入和删除只在栈顶一端进行,因此不需要设置头指针,链表的头指针就是栈顶指针。

队列

队列是一种先进先出(FIFO)的线性表,它只允许在表的一端(队尾)插入元素,在另一端(队头)删除元素。

初始化->判断是否为空 ->入队 ->出队 -> 读队头元素

初始化:创建一个空队列(队头和队尾指针在同一位置)。

判断是否为空:为空是返回true(真),否则false(假)

入队:将元素加入队尾(Rear),并更新队尾指针。

出队:将队头(Front)元素从队列删除,并更新队头指针。

读队头元素:读取队头元素的值,不更新队头指针。

顺序存储(顺序队列):

用一组地址连续的存储单元存储队列元素,队列的操作是两端进行的,因此设置队头指针和队尾指针,分别指出队头和队尾。

元素入队时,修改队尾指针。元素出队时,修改队头指针。

由于顺序队列的存储空间是预先设定的,因此队尾指针会有一个上限值(下图所示)。

数据结构队列详解(数据结构基础-栈和队列)(1)

元素入队出队以及指针修改过程

当队尾指针达到上限时,只能通过修改队尾指针来实现新元素的入队。

,