Stack in Python is an important linear data structure that follows the LIFO (Last In, First Out) principle. In a stack, the element that is added last is the first element that is removed. This simple rule makes stacks useful in many programming situations where the most recently added item needs to be processed first.
A stack can be compared to a pile of plates in a kitchen. When a new plate is added, it is placed on the top of the existing plates. When a plate needs to be removed, the top plate is taken first. In the same way, a stack allows elements to be added and removed from the top.
Python provides several ways to implement a stack. A Python list can be used for basic stack operations, while collections.deque provides an efficient implementation. Python also provides queue.LifoQueue, which can be used when a thread-safe stack implementation is required.
Table of Contents
What is a Stack?
A stack is a linear data structure that works according to the LIFO principle. LIFO stands for Last In, First Out. It means that the last element inserted into the stack will be the first element removed from it.
For example, suppose we add the following elements to a stack:
A
B
CThe element C was added last, so it will be removed first. After removing C, B becomes the top element, followed by A.
This behavior makes a stack different from a queue. A stack works with the last-added element first, while a queue follows the first-in, first-out approach.
The concept of a stack is commonly used in programming and computer science because many operations naturally follow the LIFO pattern.
YT:- DecodeIT
How Does a Stack Work?
A stack normally allows elements to be added and removed from the same end, known as the top of the stack.
When a new element is inserted, it is placed at the top. This operation is called Push. When the top element is removed, the operation is called Pop.
For example, if a stack contains:
['A', 'B', 'C']then C is the top element. If C is removed using a pop operation, B becomes the new top element.
The LIFO behavior continues until all elements have been removed from the stack.
Real-World Examples of Stack
Stacks are not limited to theoretical data structures. The LIFO concept can be found in several real-world programming features and applications.
Undo Feature in Text Editors
The Undo feature in text editors is an example of stack behavior. When multiple actions are performed, the most recent action is normally undone first.
For example, if a user performs several editing actions, pressing Undo removes the latest action before going back to earlier actions. This follows the LIFO principle.
Back Button in Web Browsers
The Back button in web browsers is another example where stack-like behavior can be observed. Recently visited pages can be accessed in reverse order, with the latest page being returned to first.
Function Call Stack
The function call stack in programming also follows a LIFO structure. When functions call other functions, the most recently called function needs to finish before returning to the previous function.
This makes the stack an important concept for understanding how function calls are handled in programming.
Basic Stack Operations
There are several basic operations commonly associated with stacks. These operations allow programmers to insert, remove, inspect, and manage elements in the stack.
1. Push
Push is the operation used to add a new element to the top of the stack.
For example, if a stack contains A and B, adding C using a push operation results in:
A
B
CC becomes the new top element of the stack.
2. Pop
Pop removes the top element from the stack and returns it.
If the stack contains A, B, and C, the first pop operation removes C. The next pop removes B, and the final pop removes A.
This demonstrates the Last In, First Out principle of the stack.
3. Peek or Top
Peek, also known as Top, returns the element currently present at the top of the stack without removing it.
This operation is useful when you need to inspect the next element that would be removed without actually changing the stack.
4. Is Empty
The Is Empty operation checks whether the stack contains any elements.
If the stack does not contain any elements, the operation returns a value indicating that the stack is empty. This is useful before performing operations that require an available element.
5. Size
The Size operation indicates the number of elements currently stored in the stack.
For example, if a stack contains A, B, and C, its size is 3.
Methods of Stack in Python
Python provides different methods and approaches that can be used to implement stack functionality.
| Method | Description | Time Complexity |
|---|---|---|
empty() | Returns True if the stack is empty; otherwise returns False. | O(1) |
size() | Returns the number of elements in the stack. | O(1) |
top() | Returns the top element without removing it. | O(1) |
push(g) | Adds element g to the stack. | O(1) |
pop() | Removes and returns the top element. | O(1) |
Implementing Stack in Python
There are three common approaches for implementing a stack in Python:
- Using a Python list
- Using
collections.deque - Using
queue.LifoQueue
1. Stack Implementation Using List
Python’s built-in list can be used as a stack. The append() method can be used to add elements, while the pop() method can be used to remove elements from the top.
Consider the following example:
# Stack implementation using list
my_stack = []
# Push elements onto the stack
my_stack.append('A')
my_stack.append('B')
my_stack.append('C')
print("Stack after pushing elements:", my_stack)
# Pop elements from the stack
print("Popped element:", my_stack.pop())
print("Popped element:", my_stack.pop())
print("Popped element:", my_stack.pop())
print("Stack after popping elements:", my_stack)Output
Stack after pushing elements: ['A', 'B', 'C']
Popped element: C
Popped element: B
Popped element: A
Stack after popping elements: []The output clearly demonstrates the LIFO behavior. C was added last, so it was removed first. B was removed next, followed by A.
Drawbacks of Using Lists
Although Python lists can be used to implement stacks, they are not specifically optimized for stack operations in every situation.
- Lists are not optimized specifically for stack operations.
- The
pop()operation can become less efficient when the list grows because of memory reallocation.
For simple programs and basic stack operations, however, a list provides an easy way to understand and implement the stack concept.
2. Stack Implementation Using collections.deque
The deque data structure available through Python’s collections module provides another way to implement a stack.
A deque is a double-ended queue and provides efficient operations for adding and removing elements. It can therefore be used effectively when implementing a stack.
Example:
from collections import deque
# Stack implementation using deque
my_stack = deque()
# Push elements onto the stack
my_stack.append('X')
my_stack.append('Y')
my_stack.append('Z')
print("Stack after pushing elements:", my_stack)
# Pop elements from the stack
print("Popped element:", my_stack.pop())
print("Popped element:", my_stack.pop())
print("Popped element:", my_stack.pop())
print("Stack after popping elements:", my_stack)Output
Stack after pushing elements: deque(['X', 'Y', 'Z'])
Popped element: Z
Popped element: Y
Popped element: X
Stack after popping elements: deque([])Here, Z is removed first because it was the last element added to the stack. Y is removed next, followed by X.
Advantages of deque Over List
The collections.deque approach provides advantages when working with stack operations.
- It provides faster append and pop operations.
- It avoids the memory reallocation issues associated with lists in the described use case.
Because of these characteristics, deque is a useful choice for implementing a stack in non-threaded applications.
3. Stack Implementation Using queue.LifoQueue
Python’s queue module provides LifoQueue, which is specifically designed to provide a last-in, first-out queue structure.
One important characteristic of LifoQueue is that it is thread-safe. This makes it suitable when stack operations need to be used in multithreaded applications.
Example:
from queue import LifoQueue
# Stack implementation using LifoQueue
my_stack = LifoQueue(maxsize=5)
# Push elements onto the stack
my_stack.put('1')
my_stack.put('2')
my_stack.put('3')
print("Stack is full:", my_stack.full())
print("Stack size:", my_stack.qsize())
# Pop elements from the stack
print("Popped element:", my_stack.get())
print("Popped element:", my_stack.get())
print("Popped element:", my_stack.get())
print("Stack is empty:", my_stack.empty())Output
Stack is full: False
Stack size: 3
Popped element: 3
Popped element: 2
Popped element: 1
Stack is empty: TrueThe output shows that the elements are removed in reverse order of insertion. The value 3 was added after 1 and 2, so it is removed first.
Advantages of LifoQueue
The LifoQueue implementation provides additional functionality that can be useful in specific situations.
- It is thread-safe and suitable for multithreading applications.
- It provides methods such as
maxsize(),empty(), andfull().
These features make LifoQueue useful when a stack is required in an environment where thread safety is important.
Choosing the Right Stack Implementation
Python provides more than one way to implement a stack, so the appropriate approach depends on the requirements of the program.
| Implementation | Use Case |
|---|---|
| List | Suitable for small programs, but may have performance issues with large data. |
| Deque | Best choice for non-threaded applications because of fast push and pop operations. |
| LifoQueue | Recommended for multi-threaded applications. |
A list is a straightforward option when you need a simple stack implementation. It uses familiar Python methods such as append() and pop().
For applications where efficient stack operations are important and thread safety is not required, deque is a suitable choice.
When the application requires a thread-safe stack, LifoQueue provides the required functionality along with additional queue management methods.
Stack in Python for Beginners
Understanding stacks is important for anyone learning Python and data structures. The LIFO principle is simple, but it appears in many areas of programming.
The easiest way to understand a stack is to imagine adding and removing objects from the top of a pile. The most recently added object is always the first one available for removal.
In Python, the concept can be practiced using a list, deque, or LifoQueue. Working through simple push and pop examples makes it easier to understand how each implementation follows the LIFO principle.
Conclusion
The Stack in Python is a fundamental data structure based on the Last In, First Out principle. The element added last is the first element removed. The main stack operations include Push, Pop, Peek or Top, Is Empty, and Size.
Python provides several ways to implement a stack. A standard list can be used for simple stack operations, while collections.deque provides an efficient approach for non-threaded applications. The queue.LifoQueue class provides a thread-safe implementation that can be useful for multithreaded applications.
Choosing the right implementation depends on the requirements of the program. Lists are convenient for simple programs, deque is suitable when efficient push and pop operations are required, and LifoQueue is appropriate when thread safety is important.
By understanding the stack data structure and its different implementations, Python learners can build a stronger foundation in data structures and programming concepts.
Keywords:-
stack in python w3schools
stack in python code
stack in python library
stack in python class 12
stack in python using list
stack in python dsa
stack in python geeksforgeeks
empty stack in python
stack in python a complete guide w3schools
stack program in python
stack in python a complete guide example
stack program in python class 12
stack in python a complete guide geeksforgeeks
stack python
stack peek python
stack pop python
