信管网试题库

D．利用两个栈可以模拟一个队列的操作，反之亦可

信管网参考答案：D

信管网解析： 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。栈的修改是按后进先出的原则进行的，所以，栈称为后进先出(Last In First Oust)的线性表，简称LIFO表。
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队首(front)，允许插入的一端称为队尾(rear)。先进入队列的成员总是先离开队列。队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。
尾指针是指向终端节点的指针，用它来表示单循环链表可以使得查找链表的开始节点和终端节点都很方便，设一带头节点的单循环链表，其尾指针为rear，则开始节点和终端节点的位置分别是rear→next→next和rear，查找时间都是O(1)。
链表是指用一组任意的存储单元来依次存放数据，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中节点的逻辑次序和物理次序不一定相同。
顺序存储是把数据按逻辑顺序依次存放在一组地址连续的存储单元里。因此，如果队列的数据规模确定，则在顺序存储结构中存取数据的速度会比链式存储结构中的要快。
假设两个栈A和B，且都为空。可以认为栈A为提供入队列的功能，栈B提供出队列的功能。
入队列：入栈A。
出队列：①如果栈B不为空，直接弹出栈B的数据；②如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。
因此两个栈可以模拟一个队列的操作，但反之不可。