若栈采用链式存储且仅设头指针，则( )时入栈和出栈操作最方便。
- A.采用不含头结点单链表且栈顶元素放在表尾结点
- B.采用不含头结点单链表且栈顶元素放在表头结点
- C.采用含头结点单循环链表且栈顶元素随机存放在链表任意结点
- D.采用含头结点双向链表且栈顶元素放在表尾结点
正确答案及解析
正确答案
B
解析
本题考查数据结构基础知识。
栈操作要求是后进先出，而且仅在表尾一端加入和删除元素。对单链表进行操作时，必须从头指针出发。根据栈操作要求，单循环链表和双向链表都是没有必要，而且选项c中将栈顶元素任意存放是错误。
可以采用单链表作为栈存储结构，将表头作为栈顶来使用。
含头结点单链表如下图所示，其中La为头指针，La指向结点为头结点。
不含头结点且栈顶元素放在表尾结点单链表如下图所示，其中La为头指针，La指向结点存储了先进入栈且没有出栈元素。显然，因为要从La出发遍历至表尾才能进行入栈和出栈操作，在这种情况下出栈和入栈都是最低效，时间复杂度都是O(n)。
如果采用不含头结点且栈顶元素放在表头单链表，如下图所示，出栈和入栈操作都在表头，时间复杂度都为O(1)。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案