Stack

In the previous topic, we implemented a stack structure based on arrays. However, with such a structure, we encounter the need to dynamically resize the array by allocating new memory for it or, conversely, reducing it. An alternative is to create a stack based on a singly linked list. The singly linked list structure is simple, yet quite efficient for creating other data structures.

Each element in the stack, as in a singly linked list, will be represented by a Node class:

1
2
3
4
5
6
7
8
9
public class Node<T>
{
public Node(T data)
{
Data = data;
}

public T Data { get; set; }
public Node<T> Next { get; set; }
}

Based on the Node class, we can implement a stack structure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using System;
using System.Collections.Generic;
using System.Collections;

namespace SimpleAlgorithmsApp
{
public class NodeStack<T> : IEnumerable<T>
{
Node<T> head;
int count;

public bool IsEmpty
{
get { return count == 0; }
}

public int Count
{
get { return count; }
}

public void Push(T item)
{
Node<T> node = new Node<T>(item);
node.Next = head; // Link the new node to point to the current top element
head = node; // Move the head pointer to the new node
count++;
}

public T Pop()
{
// if the stack is empty, throw an exception
if (IsEmpty)
throw new InvalidOperationException(“Stack is empty”);

Node<T> temp = head;
head = head.Next,// Move the head pointer to the next element down
count–;

return temp.Data;
}

public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException(“Stack is empty”);

return head. Data;
}

// Non-generic enumerator (Fixed to call the generic implementation to avoid stack overflow)
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

// Generic forward enumerator (Iterates from top of the stack to the bottom)
public IEnumerator<T> GetEnumerator()
{
Node<T> current = head;
while (current != null)
{
yield return current. Data;
current = current. Next;
}
}
}
}

Unlike the previous stack implementation, which relied on arrays, here we overcome the limitations of arrays—we don’t need to recreate the array when adding or removing data. We simply reset the reference to the head element, which is the top of the stack. The algorithmic complexity of both Push and Pop is O(1) .

Thus, we have obtained a relatively simple and quite effective solution.

Stack usage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using System;
using System.Collections;
using System.Collections.Generic;

class Program
{
static void Main()
{
// Your original code now works flawlessly with the implementation below
NodeStack<string> stack = new NodeStack<string>();
stack.Push(“Tom”);
stack.Push(“Alice”);
stack.Push(“Bob”);
stack.Push(“Kate”);

foreach (var item in stack)
{
Console.WriteLine(item);
}
Console.WriteLine();

string header = stack.Peek();
Console.WriteLine($”Top of stack: {header}”);
Console.WriteLine();

header = stack.Pop();
foreach (var item in stack)
{
Console.WriteLine(item);
}
}
}

// — Debugged Custom NodeStack Implementation —

public class Node<T>
{
public T Data { get; set; }
public Node<T> Next { get; set; }

public Node(T data)
{
Data = data;
}
}

public class NodeStack<T> : IEnumerable<T>
{
private Node<T> _head;
public int Count { get; private set; }

public bool IsEmpty => _head == null;

// Adds an item to the top of the stack
public void Push(T item)
{
Node<T> newNode = new Node<T>(item);
newNode.Next = _head;
_head = newNode;
Count++;
}

// Removes and returns the top item
public T Pop()
{
if (IsEmpty)
throw new InvalidOperationException(“Stack contains no elements.”);

T data = _head.Data;
_head = _head.Next;
Count–;
return data;
}

// Returns the top item without removing it
public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException(“Stack contains no elements.”);

return _head.Data;
}

// Crucial for making your ‘foreach’ loops work
public IEnumerator<T> GetEnumerator()
{
Node<T> current = _head;
while (current != null)
{
yield return current.Data;
current = current.Next;
}
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}

Console output:

Kate
Bob
Alice
Tom

Top of the stack: Kate

Bob
Alice
Tom

Explore More IT Terms

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Share this term: Facebook X LinkedIn WhatsApp Email
CONTINUE LEARNING Next: Queue →

RELATED ARTICLES

Circular singly linked list

    Deque

      Queue

        Array-based stack

          Algorithms and Data Structures in C#

            Doubly linked lists

              Leave a Reply

              Your email address will not be published. Required fields are marked *

              Powered by
              ►
              Necessary cookies enable essential site features like secure log-ins and consent preference adjustments. They do not store personal data.
              None
              ►
              Functional cookies support features like content sharing on social media, collecting feedback, and enabling third-party tools.
              None
              ►
              Analytical cookies track visitor interactions, providing insights on metrics like visitor count, bounce rate, and traffic sources.
              None
              ►
              Advertisement cookies deliver personalized ads based on your previous visits and analyze the effectiveness of ad campaigns.
              None
              Powered by