I have a generic stack that I will use in a console application. I need the stack to behave like a .Net stack but with extra functionality. Below is part of the code for the stack

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);
    }

}

How can I implement the pop method above to remove the tail node without having to traverse the entire list as I did in the above code using the while loop? Is there any way in which track the tail node and remove it directly?

CodePudding user response：

In a stack you are not really interested in the bottom. You have three main methods:

• push: adds a new item over the top
• pop: removes the top
• top: reads the top

Change 1: next -> prev

You will need to always track what the top is and therefore you will need to know what are the previous elements.

public Node Prev { get; set; }

Change 2: Apply the same idea for Node constructor

    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;
    }

Change 3: Apply this logic at Pop

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

CodePudding user response：

A single linked list is good enough for a stack, and only a head reference is needed.

To push onto the stack:

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

To pop from the stack:

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