的八进制、十六进制表示。此问题可以利用栈来解决。首先,将十进制数除以基数(8或16),然后对每次除法的余数进行收集,余数从低位到高位依次入栈。当十进制数除以基数得到的商为0时,停止除法。接下来,依次弹出栈中的元素,这些元素就是对应的八进制或十六进制表示的各位数字。
例二、表达式求值
中缀表达式(如2+3*4)的求值通常采用逆波兰表示法(后缀表达式,如2 3 4 * +),也就是将运算符放在操作数之后。通过栈,我们可以很容易地实现这个转换和求值过程。首先,遍历中缀表达式,遇到数字就压入栈,遇到运算符则比较栈顶两个元素进行运算,结果再入栈。最后栈中剩下的元素就是表达式的结果。
例三、括号匹配
在编译原理中,括号的匹配也是一个经典的栈应用。遍历字符串,遇到左括号就入栈,遇到右括号时检查栈顶是否为匹配的左括号,如果是则弹出栈顶元素,否则表示括号不匹配。遍历结束后,如果栈为空则表示括号匹配,否则表示有未配对的括号。
3.3 队列的类型定义
与栈类似,队列也是线性数据结构,但其特点是“先进先出”(FIFO)。队列的数据对象和数据关系与栈相同,但其基本操作有所不同:
- InitQueue(&Q): 构造一个空队列Q。
- DestroyQueue(&Q): 队列Q已存在,将其销毁。
- ClearQueue(&Q): 队列Q已存在,将其清空。
- QueueEmpty(Q): 队列Q已存在,判断是否为空,为空则返回TRUE,否则FALSE。
- QueueLength(Q): 返回队列Q的元素个数,即队列的长度。
- GetFront(Q, &e): 队列Q非空,返回队首元素e,但不删除。
- EnQueue(&Q, e): 向队列Q尾部插入元素e。
- DeQueue(&Q, &e): 队列Q非空,删除队首元素并返回其值e。
3.4 队列的应用
队列广泛应用于操作系统中的任务调度、打印机任务队列以及网络数据包传输等场景。例如,在操作系统中,多个进程或线程等待CPU执行时,会形成一个等待队列,系统会按照先进先出的原则分配CPU时间片。
3.5 循环队列与链式队列
循环队列是为了解决顺序存储队列在满和空时带来的边界问题,通过巧妙的索引处理,使得队列可以在数组内循环使用。链式队列则通过链表结构实现,具有更好的动态扩展性。
总结:
数据结构中的栈和队列是两种基础但极其重要的线性数据结构。栈遵循“后进先出”原则,常用于实现递归、表达式求值、括号匹配等问题;而队列遵循“先进先出”原则,常见于任务调度、资源分配等场景。理解并熟练掌握这两种数据结构及其操作,是深入学习数据结构和算法的基础。