栈和队列概观:
使用最广泛的两种辅助性数据结构,主要用于数据缓存。
存入和取出数据时,不能指定数据的位置或内容,只支持默认方式的操作。
栈和队列的差异在于存入和取出数据元素的顺序。栈后进先出(LIFO),队列先进先出(FIFO)。
栈的后进先出意味着各种重要操作都在表的一端进行,从效率考虑:对顺序表,应该在尾端操作;对链接表,应该在首端操作。
队列的先进先出意味着在表的一端插入,另一端删除。对于链接表,加了尾节点指针后,尾端插入具有O(1)复杂度。对于顺序表,需要采用循环顺序表的技术。
栈和队列的应用包括支持程序设计语言中的函数调用和递归函数实现、状态空间搜索等大量具体应用。