Stack Data Structure in Python and C#

In my data structures class we are talking about stacks and ways to implement them using arrays and linked-lists. When I first started learning Python I learned that Python's built-in List Type provides stack functionality.

Python Stack using List Type

If you have ever done a search for stacks in Python, I am sure you have run into the Using Lists as Stacks part of the Python documentation. One can simply use the append method to push items on the stack and pop to remove them.

s = []

s.append(1)
s.append(2)
s.append(3)

print(s.pop())  # 3
print(s.pop())  # 2
print(s.pop())  # 1

Custom Stack Class for Abstraction

For a bit more abstraction, it might be nice to create a custom Stack class in Python that hides the details of the underlying storage and provides a more formal contract. We can still leverage the List Type in Python as the underlying storage. A simple Stack class in Python using the List Type as the underlying storage with push, pop, and is_empty methods may look like the following.

class Stack:
    def __init__(self):
        self.__list = []

    def push(self, key):
        self.__list.append(key)

    def pop(self):
        return self.__list.pop()

    def is_empty(self):
        return len(self.__list) == 0

I can now using the custom Stack class in my Python applications.

s = Stack()

s.push(1)
s.push(2)
s.push(3)

print(s.pop())  # 3
print(s.pop())  # 2
print(s.pop())  # 1

The abstraction allows us to easily change the implementation later should we decide not to use the List Type in Python as the underlying storage. The abstraction also hides all the other methods offered by the List Type, providing assurance that the user code doesn't abuse the underlying storage by using non-Stack operations on it. It's simple, yet elegant.

Using Deque from Python's Collections as a Stack

Python has a collections module that offers several high-performance container types: namedtuple(), deque, Counter, OrderedDict, and defaultdict. Deque ( double-ended queue ) is a list-like container with fast appends and pops on both the front and the end of the list, which makes it useful as both a stack and a queue (although it is the queue functionality that really makes it shine). We can easily use deque as a stack in Python as shown below. All appends and pops occur from the right-side of deque.

from collections import deque


s = deque()

s.append(1)
s.append(2)
s.append(3)

print(s.pop())  # 3
print(s.pop())  # 2
print(s.pop())  # 1

One could use deque as a stack and append and pop everything from the left-side of deque.

from collections import deque


s = deque()

s.appendleft(1)
s.appendleft(2)
s.appendleft(3)

print(s.popleft())  # 3
print(s.popleft())  # 2
print(s.popleft())  # 1

We can easily replace the List Type with deque used by the custom Stack class we coded earlier in Python. Here we see the power of the abstraction offered by the Stack class by allowing us to easily replace the storage and implementation details of the stack functionality.

from collections import deque


class Stack:
    def __init__(self):
        self.__list = deque()

    def push(self, key):
        self.__list.append(key)

    def pop(self):
        return self.__list.pop()

    def is_empty(self):
        return len(self.__list) == 0


s = Stack()

s.push(1)
s.push(2)
s.push(3)

print(s.pop())  # 3
print(s.pop())  # 2
print(s.pop())  # 1

Stack Class in C#

Stack as a data structure is very useful and one can find an implementation of stack in C# in System.Collections. There is also a strongly-typed variation, called Stack<T>, in System.Collections.Generic.

using System;
using System.Collections.Generic;

namespace StackSample {
    class Program {
        static void Main(string[] args) {
            var s = new Stack<int>();

            s.Push(1);
            s.Push(2);
            s.Push(3);

            Console.WriteLine(s.Pop());  // 3
            Console.WriteLine(s.Pop());  // 2
            Console.WriteLine(s.Pop());  // 1
        }
    }
}

If you wanted to create your own Stack class in C#, you can use a similar solution to the Python example. Generic Lists don't offer the pop method like the List Type in Python, but we can just remove the last item in the list easily enough.

public class Stack<T> {
    private readonly List<T> _list = new List<T>();

    public void Push(T item) {
        _list.Add(item);
    }

    public T Pop() {
        var item = _list[_list.Count - 1];
        _list.RemoveAt(_list.Count - 1);
        return item;
    }

    public bool IsEmpty() {
        return _list.Count == 0;
    }
}

Link List as Stack in Python

So far all the custom stack implementations have been using lists, which are simply dynamic arrays. One can use a single link list with only a head pointer as a stack quite easily. Here is an implementation in Python, and it's pretty easy to build something similar in C#.

class Node:
    def __init__(self, key):
        self.key = key
        self.next = None


class Stack:
    def __init__(self):
        self.__root = None

    def push(self, key):
        new_node = Node(key)

        if self.__root is None:
            self.__root = new_node
            return

        new_node.next = self.__root
        self.__root = new_node

    def pop(self):
        if self.is_empty():
            raise IndexError('pop from empty stack.')

        temp = self.__root.key
        self.__root = self.__root.next
        return temp

    def is_empty(self):
        return self.__root is None


s = Stack()

s.push(1)
s.push(2)
s.push(3)

print(s.pop())  # 3
print(s.pop())  # 2
print(s.pop())  # 1

Conclusion

This article should give you a pretty good understanding how to use the Stack data structure in Python and C#. Deque in Python is a high-performance, multi-threaded solution for both stacks and queues. In C#, you have a similar high performance solution from Stack in System.Collections or Stack<T> in System.Collections.Generic. I'd recommend those before rolling your own or using the simplicity of a list. It's good to be familiar will all these solutions, however, and I am sure there are more.

Hope this helps!

Related Posts: