Stack data structure implementation in C# (using linked lists)

The Stack data structure is studied in most Computer Science courses on Data Structure and Algorithms. In this post, you will learn one C# implementation of this important data structure.

What is a Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last object going into the stack is the first one going out of the stack.

Because of this principle, the operations on a stack are limited. So, however you use a Stack data structure, the LIFO principle is enforced through its operations.

Operations of a Stack

A stack data structure has only 4 operations. Some programming languages have implementations with more operations. However, if you use them, you probably are violating the LIFO principle.

The operations are the following:

push: add an element to the stack. There is no need to specify the position of the new element because it will be added to the top of the stack.
pop: removes an element from the stack. There is no need to specify what element you want to remove. This operation will always remove the element at the top of the stack.
top: this operation will return the element at the top of the stack.
isEmpty: returns true if the stack is empty, otherwise, it returns false.

You need only the operations above to use the Stack data structure to solve problems. Extra operations like size, or get an element at a certain position, usually don’t make sense in this data structure.

To implement the Stack data structure, we can use arrays or linked lists.

I won’t show here the implementation with arrays because it has a fixed number of elements, and to make the number of elements variable requires a more complex implementation and it is not the goal of this post.

Stack data structure implementation using linked lists

When you study data structures, the first data structure you implement is the list data structure.

A list can be implemented using arrays or linked lists.

Here we are going to use the Java linked list implementation.

public class Stack<T>{
        private LinkedList<T> info;
        public Stack(){
            info = new LinkedList<T>();
        }
        public void push(T x) {
            info.AddLast(x);
        }
        public T pop() {
            T e = info.Last.Value;
            info.RemoveLast();
            return e;
        }
        public bool isEmpty() {
            return info.Count > 0;
        }
        public T top() {
            if (info.Last != null)
                return info.Last.Value;
            else
                throw new Exception("The stack is empty");
        }
    }

In this case, we are reusing the operations implemented in a linked list. Doing that, we are following one of the principles of Object-Oriented Programming: reusability. You can read more about OOP principles in this post.

Notice that there are two methods that can throw an exception. If you try to extract one element or retrieve the element in the top of the stack, and the stack is empty, an exception will be thrown.

You can also return null values to indicate that there is no data, but in this example, I’ll throw an exception so you can also practice that topic.

Anytime you want to use the Stack data structure to solve a certain problem, you can do it by using only the four methods implemented above. Let’s see an example.

Example of usage of the Stack data structure

The usual way to use the Stack data structure is by using a while loop and the operation isEmpty.

Search operations are not common in a stack, but you can implement them using an auxiliary stack as in the example below.

class StackUsageExample{
    public static void Main(string[] args)
        {
            Console.WriteLine("Command line arguments example");
            foreach (String argument in args) {
                Console.WriteLine(argument);
            }

            Stack<String> stack = new Stack<String>();
            stack.push("John");
            stack.push("Jane");
            stack.push("Jude");
            stack.push("Josh");
            //Print all the elements in the stack and
            //the stack must keep its initial state
            Stack<String> aux = new Stack<String>();
            String elem;
            while (!stack.isEmpty())
            {
                elem = stack.pop();
                Console.WriteLine(elem);
                // Add the element to an auxiliary queue
                aux.push(elem);
            }
            // Put back the elements into the original queue
            // using the auxiliary queue
            while (!aux.isEmpty())
            {
                stack.push(aux.pop());
            }

        }
}

If you execute the code above, you will get the following result.

Stack data structure usage example in C#

As you can see, the names are in the inverse order that we add them. This effect is caused by the LIFO principle. It is one of the many ways we can use the stack data structure implementation: to invert a collection of elements.

Summary

You can use the Stack data structure to model situations that follow the LIFO principle.

To solve problems using stacks you only need four operations: push, pop, top and isEmpty.

Practice

For you to practice what you learned in this post, you create the following C# console applications:

Create a C# console application that receives several values as command-line arguments and print them in inverse order.
Create a C# console menu application that give the user choices to test how a stack works. The choices in the menu can be the four operations available in the stack class implemented above.

Related posts:

H@ppy coding!