Table of Contents
A Stack is an Abstract Data Type that stores the order in which items were added to the structure but only allows additions and deletions to the top of the Stack. This follows a Last-In-First-Out (LIFO) principle which does as it says in the name. You can imagine this as the way in which you would eat a Stack of Pancakes (unless you like to eat parts of all the Stack at Once) or the way in which you would use Plates after you washed them after dinner and then were going to reuse them (unless for some reason you wanted to risk breaking them all!). These can be used when we want to store outputs in a structure that retains their order but we only want the user to be able to access the last thing they added to that structure. Common examples of this include the back button in your browser which goes to the last item added into the stack or the undo button on your word processor to undo the last addition you made.
When thinking about this we need to be able to define the key methods associated with this data structure. Common operations can include:
- push(item): Push an item to the top of the stack
- pop(): Remove the top item of the stack and return it
- peek(): Return the top item of the stack without removing it
- is_empty(): Return True if the Stack is empty
- size(): Return how many items are in the Stack
How can we implement a stack in Python?
In Python, we can implement python stacks by:
- Using the built-in List data structure. Python’s built-in List data structure comes with methods to simulate both stack and queue operations.
- Using the deque library which efficiently provides stack and queue operations in one object.
- Using the queue.LifoQueue Class.
As mentioned earlier, we can add items to a stack using the “PUSH” operation and remove items using the “POP” operation.
“Ready to take your python skills to the next level? Sign up for a free demo today!”
PUSH Operation
Pushing to the stack
Steps
- Check whether stack is FULL. (top == SIZE-1)
- If it is FULL, then terminate the function and throw an error.
- If it is NOT FULL, then increment top value by one (top++) and set stack[top] to value ( stack[top] = value).
- void push(int value) {
- if(top == SIZE-1)
- printf(“\nOverflow. Stack is Full”);
- else{
- top++;
- stack[top] = value;
- printf(“\nInsertion was successful”);
- }
- }
Push – adds an element at the top of the stack. Refer the below image for more understanding:
POP Operation
Pop – removes an element from the top of the stack.
Here is a simple program to illustrating Stack in Python-
| 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 |
class Stack
def_init_(self): self.items=[] def is_empty(self): return self.items==[] def push(self, data): self.items.append(data) def pop(self): return self.items.pop() s= Stack() while True: print(‘push<value>’) print(‘pop’) print(‘quit’) do= input(‘What would you like to do?’).split() operation= do[0].strip().lower() if operation== ‘push’: s.push(int(do[1])) elif operation== ‘pop’: if s.is_empty(): print(‘Stack is empty’) else: print(‘Popped value:’, s.pop()) elif operation==’quit’: break |
More about Usage of Stacks in Python and related programs
Stacks provide a wide range of uses in algorithms, for eg, in language parsing and run-time memory management (“call stack”). A short and useful algorithm using a stack is a depth-first search (DFS) on a tree or graph data structure. Python plays with several stack implementations and each has slightly different characteristics. Let’s take a brief look at them:
The list Built-in
Python’s built-in list type makes a decent stack data structure as it supports push and pop operations in amortized O(1) time.
Python’s lists are implemented as dynamic arrays internally which means they occasionally need to resize the storage space for elements stored in them whenever they are added or removed. The storage space is allocated more than required, so that not every push or pop requires resizing and you get an amortized O(1) time complexity for these operations.
Although this makes their performance less consistent than the stable O(1) inserts and deletes provided by a linked list-based implementation. On the other hand, lists provide fast O(1) time random access to elements on the stack which can be an added benefit.
Here’s an important performance caveat while using lists as stacks:
To get the amortized O(1) performance for insertion and deletion, new is added to the end of the list with the append() method and are removed from the end using pop(). Stacks based on Python lists extend to the right and shrink to the left.
Adding and removing from the front takes much more time (O(n) time), as the existing elements have to be shifted around to make room for the new element to be added.
“Experience the power of our web development course with a free demo – enroll now!”
# Using a Python list as a stack (LIFO):
| 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
s = []
s.append(‘eat’) s.append(‘sleep’) s.append(‘code’)
>>> s [‘eat’, ‘sleep’, ‘code’]
>>> s.pop() ‘code’ >>> s.pop() ‘sleep’ >>> s.pop() ‘eat’
>>> s.pop() IndexError: “pop from empty list” |
We know that a list is mutable, it can be changed, and we can easily and simply add and remove items from the beginning and end using the already inbuilt functionality of the list to implement a Stack.
In using a list we have to define a class that uses this but only has specific functionality that allows the user to interact with it in the way that we want. For this, we can use Python’s class structure to be able to define the information that the data structure will contain and also the methods that we want to use.
The first thing to do then is to name the class as Stack and create the constructor for this new class. For this, what we want is once a new instance of the object is created is to create an empty list that could be accessed using the .items attribute. We can instantiate the class as follows:
This means that when an instance of the Stack class is created then the item attribute will represent an empty list.
We can then start to add the main functionality to our Stack class. The first thing we want to be able to do is to add an item to the end of our stack. The good thing about lists is that there is an inbuilt method for this in the .append() method. The benefit of this is that it has a constant time complexity O(1) meaning that the time it takes to run will not change with the number of items already in the list because it only adds the item to the end. We can thus take advantage of this to push an item to the end of our Stack as follows:
Nice and simple right! In this instance we don’t care about what exactly we are adding to the end of the stack, just that we can add it. You can add more functionality to this but for now this is fine.
What about removing items from the Stack? For this, we first of all need to check that the Stack isn’t empty as you can’t remove items from an empty Stack right? If the stack is empty then we can simply return none so that we do actually return something, but if it is not empty then we can remove the final item and return it. Since we are using Python’s inbuilt list class, we can use the .pop() method which in Python 3.6+ removes the last item from a list and returns it. This also runs in constant time O(1) because we are only removing the last item and not affecting any other index. We can implement this as:
The benefit of checking whether a list exists first before popping ensures that an error isn’t thrown which could otherwise stop your code from running if it is not handled. Putting this in the actual implementation of the Data Structure just ensures that if you didn’t think of it when running the code using this Data Structure then the code keeps running to some degree.
We now have our main methods associated with a stack but we can also add some additional functionality just to make it more useful for our end-user.
The first thing we can add is a method to peek at the final value in a stack, allowing the user to look at the value before we decide to remove it or not. This can follow a similar implementation tothe pop() method but instead of using .pop()we access the item with the last index in the list. Again, this is has a time complexity of O(1) as we are accessing an item from a list using an index making this nice and simple.
We can also provide a method of checking whether the Stack is empty or not. This would simply return a boolean value of True if the stack is empty and False if it is not empty. This also runs in constant time as it is simply checking whether the list within the stack exists or not.
Finally, we can create a method that returns the size of the stack. This tells us the length of the stack, just like it would for a list, and allows the user to see how many items have been added.
We now have the main functionality of our Stack class and most of the additional functionality as well. This just makes it easier and simpler for our end user to interact with this Data structure in the final interface that we created.
The only issue is, if we try to print an instance of the class we get the ugly output of
<__main__.Stack object at 0x0000027F2C960FD0>
which doesn’t look good and also doesn’t tell us much about the actual instance of the class. What can do then is to use the special __str__ dunder method of the class to tell the interpreter how we want to print out an instance of the class. In this case we simply want to return the entire list contained within the stack which can be implemented as:
The final thing to do then is to put all of this together so that we can create instances of this Stack class in our code.
“Get hands-on with our python course – sign up for a free demo!”
The collections.deque Class
The deque class implements a double-ended queue which supports addition and removal of elements from either end in O(1) time (non-amortized).
Because deques support adding and removing elements from both ends equally well, they can serve both as queues and as stacks.
Python’s deque objects are implemented as doubly-linked lists which gives them proper and consistent performance insertion and deletion of elements, but poor O(n) performance as they randomly access elements in the middle of the stack.
collections.deque is a favourable choice if you’re looking for a stack data structure in Python’s standard library with the performance characteristics of a linked-list implementation.
# Using collections.deque as a stack (LIFO):
| 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
from collections import deque
q = deque()
q.append(‘eat’) q.append(‘sleep’) q.append(‘code’)
>>> q deque([‘eat’, ‘sleep’, ‘code’])
>>> q.pop() ‘code’ >>> q.pop() ‘sleep’ >>> q.pop() ‘eat’
>>> q.pop() IndexError: “pop from an empty deque” |
The queue.LifoQueue Class
This stack implementation in the Python standard library is synchronized and provides locking semantics to support multiple concurrent producers and consumers.
The queue module contains several other classes implementing multi-producer, multi-consumer queues that are useful for parallel computing.
Depending on your use case the locking semantics might be helpful, or just incur unneeded overhead. In this case you’d be better off with using a list or a deque as a general purpose stack.
# Using queue.LifoQueue as a stack:
| 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from queue import LifoQueue
s = LifoQueue()
s.put(‘eat’) s.put(‘sleep’) s.put(‘code’)
>>> s <queue.LifoQueue object at 0x108298dd8>
>>> s.get() ‘code’ >>> s.get() ‘sleep’ >>> s.get() ‘eat’
>>> s.get_nowait() queue.Empty
>>> s.get() # Blocks / waits forever… |
