链表实现的一个堆栈

Question

这是我用linkedlist实现的堆栈

STACK using linked list 
STACK-EMPTY:
if L.head == NIL
    return True
else return False
PUSH(x):
x.next = L.head 
if L.head != NIL
    L.head.prev = x
L.head = x
x.prev = NIL
POP():
x = L.head
L.head = x.next
x.next.prev = L.head
return x

你会验证这个吗?如何改进?

谢谢

Answer 1

您可以改进数据结构的一致性:

1. 列表头的prev始终是NIL
2. 不在列表中的元素将next和prev设置为NIL

1。考虑到你的POP有一个不一致的地方，这可能是错误的来源:当你弹出一个元素，头部的prev是头部本身，当你推送一个元素，头部的prev是NIL。

Answer 2

试试这个…

定义:

• S.top是指向堆栈顶部X类型节点的指针
• X是一个有两个指针的节点，top和base
• X.top指向栈顶的下一个节点
• X.base指向堆栈底部的下一个节点

首先初始化栈顶指针:

STACK-INITIAL:
S.top = NIL
return true  // Never fails

空栈测试:

STACK-EMPTY:
return (S.top == NIL)

Push节点x on stack:

PUSH(x):
x.top = NIL     // Top of stack, therfore top is NIL
x.base = S.top  // base is previous top
S.top = x       // x is now top of stack  
return true

弹出并返回堆栈顶部(这是唯一"有趣"的部分):

POP():
x = S.top          // Top node on stack (could be NIL)
if S.top != NIL    // Check in case stack was empty
  S.top = x.base   // New top = next node toward base
  x.base = NIL     // Disconnect x from stack
  if S.top != NIL  // Is stack now empty?
    S.top.top = NIL // No, set top node's top pointer to NIL
return x            // x could be NIL if stack was empty

值得考虑的事情……我在上面使用双链表是因为看起来你用的就是这个。然而，你只需要一个单链表，其中链接指向堆栈的基础。注意，上面算法中的x.top指针非常无用(设置但从未引用)。只要你跟踪堆栈顶部(S.top)唯一的事情您需要做的是在POP操作期间向下跟踪堆栈。

对注释的回应

当一个元素被从堆栈中弹出时，所有与它相关的指针应该设置为NIL。这是因为它不再是一部分的，所以不应该指向任何堆栈元素。这是我加的回复我最初的答案(见上文)。

以类似的方式，新的堆栈顶部元素(除非堆栈变为空)需要它的指针指向它上面的元素设置为NIL(因为它上面的元素被删除了)。在我的例子中，这就是S.top.top = NIL所有的东西都是关于(S.top指向栈顶元素，所以S.top.top是该元素的上指针)。我认为你会对x.next.prev = NIL做同样的事情，假设x是您指定的元素，而不是NIL本身。在伪代码中，它看起来是这样的像x.next.prev = L.head这样的操作将使栈顶元素的prev指针指向自身因为L.head被设置为x.next(在此之前的新栈顶)。

最后，我质疑为什么要使用双链表来实现一个栈，只有一个链表与指针指向