理解循环队列长度与栈的数据结构

该资源是一份关于数据结构的课件，重点讲解了循环队列的长度计算方法以及栈和队列的基本概念、操作和实现。 循环队列是一种线性数据结构，它的特点是首尾相接形成一个环状，用于解决传统队列在达到数组边界时可能出现的溢出问题。在循环队列中，`front`表示队头，`rear`表示队尾，队列长度可以通过`rear - front`计算，但由于循环特性，需要将结果加上数组大小`MAXQSIZE`取模来得到正确长度。例如，当`rear = 5`，`front = 3`时，队列长度 `(5 - 3 + MAXQSIZE) % MAXQSIZE = 2`。 栈和队列是两种基础的线性数据结构，它们的操作受限。栈遵循“后进先出”（LIFO）原则，而队列遵循“先进先出”（FIFO）原则。 3.1 栈的定义与特点： - 定义：栈是一种只允许在表尾（栈顶）进行插入和删除操作的线性表。栈底通常固定，栈顶则随着元素的入栈和出栈移动。 - 特点：栈的操作顺序遵循“先进后出”（FILO）或“后进先出”（LIFO）。栈可以形象地理解为一叠盘子，新放上去的盘子（元素）会放在最上面，要拿走盘子（元素）时，必须先拿最上面的。 栈的基本操作包括： - InitStack：创建栈。 - DestroyStack：销毁栈。 - ClearStack：清除栈内容。 - StackEmpty：判断栈是否为空。 - StackLength：返回栈中元素的数量。 - GetTop：返回栈顶元素但不删除。 - Push：入栈，将元素添加到栈顶。 - Pop：出栈，移除并返回栈顶元素。 - StackTraverse：遍历栈中的所有元素。 3.1 栈的存储结构： - 顺序栈：使用动态分配的一维数组来实现，初始分配一定容量，当空间不足时，通过增加容量（如增加 STACK_INCREMENT）来扩展。栈顶指针 `top` 指向栈顶元素的下一个位置，初始指向栈底，栈空时 `top == base`。 在顺序栈中，入栈操作会使 `top` 向上移动，出栈操作则使 `top` 回退。如果 `top` 在达到数组末尾后继续移动，即 `S.top - S.base >= S.stacksize`，表示栈满；若 `top` 等于栈底指针 `base` 且尝试出栈，将导致下溢错误。 以上内容涵盖了循环队列的长度计算方法以及栈的基本概念、操作和存储结构，是数据结构学习的重要组成部分。通过这些知识，可以帮助理解和实现各种数据结构算法，如递归、回溯、深度优先搜索等。