0

这是我用链表实现的堆栈

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

你会验证这个吗？怎么提高 ？

谢谢

4

2 回答 2

1

您可以提高数据结构的一致性：

  1. 列表头的prev总是NIL
  2. 不在列表中的元素具有next并prev设置为 NIL

考虑到 1. 考虑到您的 POP 存在不一致，这可能是错误的来源：当您弹出一个元素prev时，头部是头部本身，当您推送一个元素prev时，头部是 NIL。

于 2013-03-27T13:26:18.377 回答
0

尝试这个...

定义：

  • 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)

将节点推入x堆栈：

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（之前的新堆栈顶部）。

最后，我质疑为什么要使用双链表来实现堆栈，只需要一个带有指向其下一个元素的指针的单链表

于 2013-03-27T14:40:28.603 回答