考试网 >> IT认证 >> 水平 >> 其它 >> 数据结构中队列的复习要点

发布时间：2006-06-28 03:02     点击：

链队列

队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。

对于什么情况下用栈和队列作为解决问题的数据结构。判断的要点就是：如果这个问题满足后进先出(LIFO)的原则，就可以使用栈来处理。如果这个问题满足先进先出(FIFO)的原则，就可以使用队列来处理。比如简单的说，有一个数组序列，我们输入时按顺序输入，但是输出时需要逆序输出，那么它就可以利用栈来处理，把这个数组存入一个栈中就可以容易地按逆序输出结果了。

例：设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?

解答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。