栈和队列的逻辑结构与线性表相同,其特点在于运算有所限制(运算受限的线性表),栈操作按照后进先出(LIFO)的规则,队列按先进先出(FIFO)的规则。
栈通过访问它的一端来实现数据存储与检索的线性结构。
进行插入和删除操作的一端称为栈顶(Top),另一端称为栈底(Bottom),不包含数据元素的栈,称为空栈。
- 运算过程:
初始化栈->判断栈是否为空->入栈(Push)->出栈(Pop)->读取栈顶元素
初始化栈:创建一个空栈。
判断栈是否为空:为空是返回true(真),否则false(假)
入栈:将元素加入栈顶,并更新栈顶指针。
出栈:将栈顶元素删除,并更新栈顶指针。
读栈元素:返回栈顶元素的值,不更新指针。
- 存储结构
顺序存储(顺序栈):
用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时指针指示栈顶元素的位置。这种存储方式下,栈的空间容量是有限的,当元素入栈时,需要判断是否栈满,如栈满,则不能入栈。
链式存储(链栈):
栈中元素的插入和删除只在栈顶一端进行,因此不需要设置头指针,链表的头指针就是栈顶指针。
队列队列是一种先进先出(FIFO)的线性表,它只允许在表的一端(队尾)插入元素,在另一端(队头)删除元素。
- 运算过程
初始化->判断是否为空 ->入队 ->出队 -> 读队头元素
初始化:创建一个空队列(队头和队尾指针在同一位置)。
判断是否为空:为空是返回true(真),否则false(假)
入队:将元素加入队尾(Rear),并更新队尾指针。
出队:将队头(Front)元素从队列删除,并更新队头指针。
读队头元素:读取队头元素的值,不更新队头指针。
- 存储结构
顺序存储(顺序队列):
用一组地址连续的存储单元存储队列元素,队列的操作是两端进行的,因此设置队头指针和队尾指针,分别指出队头和队尾。
元素入队时,修改队尾指针。元素出队时,修改队头指针。
由于顺序队列的存储空间是预先设定的,因此队尾指针会有一个上限值(下图所示)。
元素入队出队以及指针修改过程
当队尾指针达到上限时,只能通过修改队尾指针来实现新元素的入队。
,