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!