Definition – What is Stack in Python
Python Stack is a conceptual structure consisting of a set of homogeneous elements and is based on the principle of last in first out (LIFO). It is a commonly used abstract data type with two major operations, namely, push and pop. Push and pop are carried out on the topmost element, which is the item most recently added to the stack.
The push operation in Python Stack adds an element to the stack while the pop operation removes an element from the top position of Python Stack. The stack concept is used in programming languages (ex. Python) and memory organization in computers.
Working of Python Stack
A Python stack represents a sequence of objects or elements in a linear data structure format. The stack consists of a bounded bottom and all the operations are carried out on the top position. Whenever an element is added to the stack by the push operation, the top value is incremented by one, and when an element is popped out from the stack, the top value is decremented by one. A pointer to the top position of the stack is also known as the stack pointer.
A Python stack may be fixed in size or may have a dynamic implementation where the size is allowed to change. In the case of bounded capacity stacks, trying to add an element to an already full stack causes a stack overflow exception. Similarly, a condition where a pop operation tries to remove an element from an already empty stack is known as underflow.
Operations We Can Perform On Python Stack
A stack is considered to be a restricted data structure as only a limited number of operations are allowed. Besides the push and pop operations, certain implementations may allow for advanced operations such as:
- Push: Adds an item in the stack. Once the stack is full, it is said to be in an Overflow condition.
- Pop: Removes an item from the stack. It follows a reversed order to pop items similar to the way when items are pushed. It is said to be an Underflow condition.
- Peek: View the topmost item in the stack.
- Duplicate: Copy the top item’s value into a variable and push it back into the stack.
- Swap: Swap the two topmost items in the stack.
- Rotate: Move the topmost elements in the stack as specified by a number or move in a rotating fashion.
Software implementations of the stack concept are done using arrays and linked lists where the top position is tracked using a variable or header pointer respectively. Many programming languages provide built-in features to support stack implementation.
Hardware stacks are implemented for the purpose of memory allocation and access using a fixed origin and size. Stack registers are used to store the value of the stack pointer.
Push Operation in Python Stack
The process of putting a new data element onto the stack is known as a Push Operation. Push operation involves a series of steps −
Steps for Push Operation in Python
- Checks if the stack is full.
- If the stack is full, produces an error and exit.
- If the stack is not full, increments top to point next empty space.
- Adds data element to the stack location, where the top is pointing.
- Returns success.
Pop Operation in Python Stack
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.
Steps for Pop Operation in Python
- Checks if the stack is empty.
- If the stack is empty, produces an error and exit.
- If the stack is not empty, accesses the data element at which the top is pointing.
- Decreases the value of top by 1.
- Returns success.
Implementing Stack in Python
Python gives you a lot of options for implementing a Python stack. You can do so by using lists, tuples or by using third-party modules or packages. However, there are some basic implementations of Python stack that will fulfil most of your needs.
Some of those implementations are as follows:
- list
- collections.deque
- queue.LifoQueue
The functions associated with stack are:
- empty() – Returns whether the stack is empty – Time Complexity: O(1)
- size() – Returns the size of the stack – Time Complexity: O(1)
- top() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)
- push(g) – Adds the element ‘g’ at the top of the stack – Time Complexity: O(1)
- pop() – Deletes the topmost element of the stack – Time Complexity: O(1)
Implementing Stack in Python Using List
In Python, we can implement a stack by using list methods as they have the capability to insert or remove/pop elements from the end of the list.
The method that will be used:
- append(x): Appends x at the end of the list
- pop() : Removes last elements of the list
The built-in list is the structure that you likely use frequently in your programs can be used as a stack. Instead of .push(), you can use .append() to add new elements to the top of your stack, while .pop() removes the elements in the LIFO order:
Program to use list stack
# Python Example: use list as stack
# Declare a list named as "stack"
stack = [10, 20, 30]
print ("stack elements: ");
print (stack)
# push operation
stack.append(40)
stack.append(50)
print ("Stack elements after push opration...");
print (stack)
# push operation
print (stack.pop (), " is removed/popped...")
print (stack.pop (), " is removed/popped...")
print (stack.pop (), " is removed/popped...")
print ("Stack elements after pop operation...");
print (stack)Output:
stack elements:
[10, 20, 30]
Stack elements after push opration...
[10, 20, 30, 40, 50]
50 is removed/popped...
40 is removed/popped...
30 is removed/popped...
Stack elements after pop operation...
[10, 20]Implementing Stack in Python Using 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):
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"Implementing Stack in Python Using 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.
# How to use queue.LifoQueue as a stack:
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...
Also Read:
Python Remove Duplicates From List
Python Print Without Newline
Learn Python the Hard Way Review PDF
How to Get a Data Science Internship With No Experience
Python Map
Parsing
To implement the previous algorithm, we need to be able to traverse a string and break it into operands and operators.
Python provides a split method in both string objects and the re (regular expression) module. A string’s split method splits it into a list using a single character as a delimiter. For example:
>>> "Now is the time".split(" ")
['Now', 'is', 'the', 'time']
In this case, the delimiter is the space character, so the string is split at each space.
The function re.split is more powerful, allowing us to provide a regular expression instead of a delimiter. A regular expression is a way of specifying a set of strings. For example, [A-z] is the set of all letters and [0-9] is the set of all numbers. The ^ operator negates a set, so [^0-9] is the set of everything that is not a number, which is exactly the set we want to use to split up postfix expressions:
>>> import re
>>> re.split("([^0-9])", "123+456*/")
['123', '+', '456', '*', '', '/', '']
The resulting list includes the operands 123 and 456 and the operators * and /. It also includes two empty strings that are inserted after the operands.
Applications of Python Stack
Stacks are considered as the backbone of Data Structures. Most of the algorithms and applications are implemented using stacks.
Some of the key applications of Python Stacks are—
- used in “undo” mechanism in the text editor.
- Language processing:
- space for parameters and local variables is created internally using a stack.
- compiler’s syntax check for matching braces is implemented by using stack.
- support for recursion.
- Expression evaluation like postfix or prefix in compilers.
- Backtracking (game playing, finding paths, exhaustive searching.
- Python Stack is also used in Memory management, run-time environment for nested language features. etc
- Used in Algorithms like Tower of Hanoi, tree traversals, histogram problem and also in graph algorithms like Topological Sorting.
Conclusion
Python Stack is simple data structures that allow us to store and retrieve data in a sequential fashion. They are very useful in real-world cases. Having a clear understanding of stacks would help us in solving data storage problems in an efficient manner.
The Python stack is an important data structure for realizing solutions to various programming problems. As such, it is even more essential to understand the running time evaluations and working mechanism of these data structures.
Happy Coding!