如何在不遍历列表的情况下为通用堆栈实现 pop 方法

Question

我有一个将在控制台应用程序中使用的通用堆栈。我需要堆栈的行为类似于 .Net 堆栈，但具有额外的功能。下面是堆栈的部分代码

class DynamicGenericStack<T>
{

    private class Node
    {
        public T element { get; private set; }
        public Node Next { get; set; }

        public Node(T element, Node prevNode)
        {
            this.element = element;
            Next = null;
            Previous = null;
            if (prevNode != null) //if this is not the first node
                prevNode.Next = this;
        }
    }

    private Node head, tail;

    public int Count { get; private set; } //Count

    public DynamicStack()
    {
        this.head = null;
        this.tail = null;
        this.Count = 0;
    } 



    public void Push(T item)
    {
        if (this.head == null)
            this.head = this.tail = new Node(item, null);
        else
            tail = new Node(item, tail);
        Count++;
    } Push

    public T Peek()
    {
        return tail.element;
    } Peek

    public T Pop()
    {
        if (Count > 0)
        {
            T item = tail.element;
            Node prev = null, current = head;
            while (current != tail)
            {
                prev = current;
                current = current.Next;
            }
            tail = prev;
            Count--;
            return item;

        }
        return default(T);
    }

}

如何实现上面的pop方法来移除尾节点，而不必像我在上面的代码中使用while循环那样遍历整个列表？有什么办法可以跟踪尾节点直接去掉吗？

Answer 1

在堆栈中，您对底部并不真正感兴趣。您有三种主要方法：

推送：在顶部添加一个新项目
pop：删除顶部
top: 读取顶部

变化一：下一个 -> 上一个

您需要始终跟踪顶部是什么，因此您需要知道前面的元素是什么。

public Node Prev { get; set; }

变化 2：对 Node 构造函数应用相同的想法

    public Node(T element, Node prevNode)
    {
        this.element = element;
        Next = null;
        Previous = null;
        if (prevNode != null) //if this is not the first node
            prevNode.Prev = this;
    }

更改 3：在 Pop 应用此逻辑

public T Pop()
{
    T element = default(T);
    if (Count > 0)
    {
            element = tail.element;
            if (tail.Prev != null) {
                tail = tail.Prev;
            } else {
                head = tail = null;
            }
    }
    return element;
}

Answer 2

单链表做栈就够了，只需要一个头引用

压入堆栈：

    create new_node
    new_node.next = head;
    head = new_node;
    count++;

从堆栈中弹出：

    if(count == 0)
        return null;
    tmp_node = head;
    head = head.next;
    count--;
    return tmp_node.element;

如何在不遍历列表的情况下为通用堆栈实现 pop 方法

How can i implement a pop method for a generic stack without traversing the list

c#

generics

data-structures

linked-list

stack

变化一：下一个 -> 上一个

变化 2：对 Node 构造函数应用相同的想法

更改 3：在 Pop 应用此逻辑