首页 > 试题广场 >

若采用带头、尾指针的单向链表表示一个栈，那么该堆栈的栈顶指针

[单选题]

若采用带头、尾指针的单向链表表示一个栈，那么该堆栈的栈顶指针top应该如何设置（） 

  • 将表头项设置为top
  • 将链表尾设置为top
  • 随便哪端作为top都可以
  • 链表头、尾都不适合作为top
查看正确选项
添加回答
泼夫头像 泼夫
这里头尾指针是链表的，和栈没关系，即头指针≠栈底，尾指针≠栈顶。
出栈入栈都是针对栈顶元素进行的操作，考虑到这个链表是单项的（从前往后不能从后往前），所以把头指针设成top，这样出栈入栈就是对表头操作，时间上快很多。
发表于 2020-04-30 12:56:06 回复(4)
江关庾信头像 江关庾信
a 表尾为top 删除的时候复杂度太大
编辑于 2017-01-12 00:14:02 回复(1)
我头发茂盛头像 我头发茂盛
表头插入删除复杂度O(1) 表尾插入O(1)，删除尾部需要找到尾节点的前驱，所以为O(n)，
发表于 2021-05-10 18:23:53 回复(1)
Nancy_Grange头像 Nancy_Grange
我的理解是top在尾部无法判空，而表头为top可以根据指针是否指向空判断栈空。
发表于 2021-09-26 19:10:25 回复(2)
xiaolaoshu头像 xiaolaoshu
队尾不知道上一个对象地址
发表于 2022-07-28 21:18:20 回复(0)
陳丶奕丶迅头像 陳丶奕丶迅
如果将栈顶指针top设置在链表尾，那么每次出栈操作需要的时间复杂度为O(n)，因为出栈之后要重新指定top指针的位置，你也可以想象成重新设置链表尾指针的位置。而重新设置链表尾指针需要从表头开始一直遍历到链表的最后一个节点，这样做就得不偿失了
发表于 2022-07-16 10:46:32 回复(0)
淇神头像 淇神
表尾的话删除操作的时间复杂度为O(n)
发表于 2020-05-16 18:14:15 回复(0)
毁人不倦*头像 毁人不倦*
单向链表，如果把表尾设置为栈顶，无法获取栈顶下一个元素，即表尾的上一个元素 把表头设置为栈顶，栈顶出栈，单向链表的下一个元素作为栈顶
发表于 2023-02-28 00:03:37 回复(0)
清欢Qinghuan_头像 清欢Qinghuan_
复杂也不代表不能实现啊
发表于 2022-03-31 19:02:54 回复(0)
风忧子头像 风忧子
单向链表的头结点本身不存储数据，仅作为标记。所有可以直接插入和提取之后的头一元素，做top更合适
发表于 2024-09-01 01:05:51 回复(0)
牛客594745606号头像 牛客594745606号
这题有问题，选C也不是不能实现，题目也没说必须是效率最高的
发表于 2024-07-21 11:36:06 回复(0)
simon_free头像 simon_free
链表可以在任意位置插入，用来实现栈，应该控制在链头，栈删除时也是发生在链头，可以省去遍历的时间
发表于 2023-10-28 13:47:34 回复(0)
皮皮鲁鲁西西头像 皮皮鲁鲁西西
栈是后进先出的，设置链表头指针为栈顶，头插法建立链表本身也是从头入遍历删除，出栈入栈在链表头部操作
发表于 2023-09-12 15:04:43 回复(0)
包子快递头像 包子快递
尾指针找不到前面的节点了。。。
发表于 2023-03-13 17:39:43 回复(0)
Hacynn头像 Hacynn
因为是单向链表，只能从前往后，不能从后往前，所以如果尾指针作为栈顶指针top时无法向前移动。
发表于 2023-01-29 23:05:21 回复(0)
牛客119871344号头像 牛客119871344号
入栈头插法插到表前，单项链表，栈顶指针放到表头比较方便，不用遍历
发表于 2022-07-05 19:00:47 回复(0)
旁又头像 旁又
注意 单向链表
发表于 2022-04-19 14:55:36 回复(0)
看书掉头发头像 看书掉头发
想明白了，链尾为top 删除则需要遍历一次o(n)复杂度，链头为o(1)
发表于 2022-03-13 12:18:16 回复(0)
单手提煤气罐头像 单手提煤气罐
A吧

发表于 2020-03-25 20:59:10 回复(0)
平凡马修头像 平凡马修
A
发表于 2019-10-27 17:06:35 回复(0)
提交观点

问题信息

C++工程师 栈 牛客
上传者：城市里的养猫者
难度：
20条回答 16555浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号