Implementing Python Stack: Functions, Methods, Examples & More

A stack push and pop in Python is a core concept in programming and computer science.
This article delves into implementing a Python stack, known for its Last-In-First-Out (LIFO)
behavior, crucial for data management and algorithms. We explore essential principles,
methods, and key considerations for efficient Python stack usage, important for all coders.

Table of contents

1. What is Stack in Python?

2. How to Use Stack in Python?

3. Methods of Python Stack

4. Functions of Python Stack

5. Implementation of Python Stack

6. Deque vs List

7. Python Stacks and Threading

o Thread Safety

o Using Deque for Thread-Safe Stacks

o Synchronization and Locks

8. Which Implementation of Stack should one consider?

o Deque (from the collections module)

o List (Python built-in)

9. Conclusion

10. Frequently Asked Questions

Free Certification Courses

Introduction to Python

Learn Python syntax • Variables & data types • Loops & functions

What is Stack in Python?

A stack is a linear data structure. It adheres to the Last-In-First-Out (LIFO) principle.

Functioning as a collection of elements, the last item added is the first one to be removed.
Some key operations associated with a stack in Python are as follows:

 Push: Adding an element to the top of the push and pop in Python.
  Pop: Removing and returning the top element from the stack.

 Peek: Viewing the top element without removing it.

 Check for Empty: Verifying if the push and pop in Python is devoid of elements.

Python stacks find utility in various applications, such as function call tracking, expression
evaluation, and parsing algorithms.

How to Use Stack in Python?

A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. This means the
last element added to the stack will be the first one to be removed. It’s like a stack of books:
you can only add or remove a book from the top of the stack.

In Python, we can use a list to represent a stack.

Creating a Stack

You can create a stack by initializing an empty list.

stack = []

Adding Elements to the Stack

We use the append() function to add elements to the top of the stack.

[Link]('A')

[Link]('B')

[Link]('C')

Now, our stack looks like this: ['A', 'B', 'C']. ‘C’ is at the top of the stack.

Removing Elements from the Stack

We use the pop() function to remove elements from the top of the stack.

top_element = [Link]()

This will remove ‘C’ from the stack, and now our stack looks like this: ['A', 'B'].

Checking if the Stack is Empty

To check if the stack is empty, we can use the not operator.

if not stack:

print("Stack is empty.")

else:

print("Stack is not empty.")

And that’s it! You now know how to use a stack in Python. Remember, practice is key when
learning new concepts in programming. So, try to incorporate the use of stacks in your next
project! Happy coding! 🚀

Methods of Python Stack

Stacks in Python, like in many programming languages, come equipped with several
fundamental methods and operations that facilitate the manipulation of data within this
data structure. Let’s explore Python stack methods:

 push(item): This method adds an element (item) to the top of the stack.

[Link](42)

 pop(): The pop() method is employed to remove and retrieve the top element from
the push and pop in python. This action reduces the amount of the stack by one. An
error occurs if the stack is empty.

top_element = [Link]()

 peek(): For observing the top element of the stack without removing it, the peek()
function is invaluable. It’s an excellent tool for inspecting the element at the stack’s
pinnacle without altering the stack itself.

top_element = [Link]()

 is_empty(): This method determines whether the push and pop in python is empty.
It returns True if the stack contains no elements and False otherwise.

if stack.is_empty():

print("The stack is empty.")

 size(): To determine the number of elements presently residing in the stack, you can
employ the size() method. It offers a straightforward means of gauging the stack’s
length.

stack_size = [Link]()

 clear(): When the need arises to remove all elements from the stack, effectively
rendering it empty, the clear() function comes into play.

[Link]()

 not stack: In Python, you can employ the not operator to ascertain whether the push
and pop in python contains any elements. This succinct approach allows you to
discern if the stack is devoid of items.

if not stack:

print("The stack is empty.")

Also Read: Top 10 Uses of Python in the Real World with Examples

Functions of Python Stack

There are a number of built-in functions and standard library modules for a stack, including

 List () and deque () Constructors: You can use the list() constructor or the deque ()
constructor from the collections module to create an empty stack.

stack_list = list()

stack_deque = deque()

 [Link](iterable) and [Link](iterable): These methods allow you to push

multiple elements onto the stack at once by extending it with an iterable (e.g., a list
or another stack).

stack_list.extend([1, 2, 3])

stack_deque.extend([4, 5, 6])

 [Link](index) and [Link](): We’ve previously covered the pop() method for
push and pop in python. Python lists also offer pop(index) to remove an element at a
specific index. The [Link]() method efficiently removes and returns a deque’s
leftmost (bottom) element, useful when simulating queue-like behavior with a
deque-based stack.

stack_list.pop(1) # Remove and return the element at index 1

bottom_element = stack_deque.popleft()

 heapq Module: The heapq module in Python provides functions to transform a list
(or deque) into a min-heap. While it’s not a traditional stack operation, you can use a
min-heap to implement certain stack-like behaviors, such as retrieving the smallest
element.

import heapqstack

= [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

[Link](stack) # Convert the list into a min-heap

smallest_element = [Link](stack) # Remove and return the smallest element

 functools.lru_cache: This decorator from the functools module can be used to

implement a cache with a stack-like behavior. It stores recently computed function
results and discards the least recently used values when the cache reaches a
specified size.

from functools import lru_cache

@lru_cache(maxsize=5)

def expensive_computation(n):

# Expensive computation here

return result

Implementation of Python Stack

 Using Lists

# Creating an empty stack using a list

stack = []

# Pushing elements onto the stack

[Link](1)

[Link](2)

[Link](3)

# Popping elements from the stack

top_element = [Link]()

To construct an empty stack, we utilize a Python list in the code above. Then, we use the
append() method to add items to the stack and the pop() method to remove them from it.
However, lists are a flexible approach to designing a stack; remember that deque may be
more effective for huge stacks.

 Using deque (from the collections module)

from collections import deque

# Creating an empty stack using a deque

stack = deque()

# Pushing elements onto the stack

[Link](1)

[Link](2)

[Link](3)

# Popping elements from the stack

top_element = [Link]()
In this code, we use the deque data structure from the collections module to create a push
and pop in python. Deques are optimized for fast append and pop operations from both
ends, making them more efficient than lists for implementing stacks, especially when dealing
with many elements.

 Custom Stack Class

You can also create a custom stack class to encapsulate stack operations and provide a clean
interface for working with stacks:

from collections import deque

class Stack:

def __init__(self):

[Link] = deque()

def push(self, item):

[Link](item)

def pop(self):

if not self.is_empty():

return [Link]()

else:

raise IndexError("Pop from an empty stack")

def peek(self):

if not self.is_empty():

return [Link][-1]

else:

return None

def is_empty(self):

return not [Link]

def size(self):

return len([Link])

In the custom Stack class, we use a deque as the underlying data structure and provide
methods for pushing, popping, peeking, checking if the stack is empty, and getting the size of
the stack. This class provides a handy way to work with stacks in your Python code by
abstracting the stack operations.

Deque vs List

Feature Deque List

Data Structure Double-ended queue Dynamic array

Optimized for fast appends and Slower for pops from the left side.
Efficiency
pops from both ends. Faster for pops from the right side.

Not inherently thread-safe; may

Thread-safe with proper
Thread Safety require manual synchronization in
synchronization.
multithreaded environments.

Memory More memory-efficient, especially May consume more memory for large
Efficiency for large stacks. stacks due to dynamic array resizing.

append(), pop(), and pop(index) are

append(), pop(), and popleft() are
Operations available. pop(index) can be less
efficient.
efficient when popping from the left.

Supports random access by index,

Random Access Not suitable for random access. which may not be needed for stack
operations.

Recommended for most stack Suitable for small stacks or when

Recommended
implementations, especially when additional list functionalities are
Use Cases
efficiency is crucial. required.

In summary, using a deque from the collections module is often the preferred choice for
implementing stacks in Python due to its efficiency, thread safety, and memory efficiency.
However, using a list can also be suitable for small stacks or when you need random access
by index. Your choice depends on the specific requirements of your program.

Python Stacks and Threading

In computer science, stacks are fundamental data structures frequently used for Last-In-
First-Out (LIFO) data management. It’s crucial to consider the effects of concurrency and
multi-threading while utilizing stacks in Python. In this part, we’ll talk about threading
interactions between Python stacks and the best ways to manage them in concurrent
settings.

Thread Safety

Thread safety is a crucial consideration when working with data structures like stacks in a
multi-threaded environment. The simultaneous access to shared data structures can result
in race situations, data corruption, and other unexpected behavior in Python because
threads share memory space.

Using Deque for Thread-Safe Stacks

One way to ensure thread safety when working with stacks in Python is to use the deque
data structure from the collections module, designed to be thread-safe. Deques provide
efficient append and pop operations from both ends, making them well-suited for stack
implementations.

Here’s an example of using a deque-based stack in a multi-threaded Python program:

import threading

from collections import deque

# Create a deque-based stack

stack = deque()

# Define a function to push items onto the stack

def push_item(item):

[Link](item)

# Define a function to pop items from the stack

def pop_item():

if stack:

return [Link]()

else:

print("Stack is empty.")

# Create multiple threads to manipulate the stack

thread1 = [Link](target=push_item, args=(1,))

thread2 = [Link](target=push_item, args=(2,))

thread3 = [Link](target=pop_item)

thread4 = [Link](target=pop_item)

# Start the threads

[Link]()

[Link]()
[Link]()

[Link]()

# Wait for all threads to finish

[Link]()

[Link]()

[Link]()

[Link]()

In this example, we use the threading module to concurrently create multiple threads that
push and pop items from the deque-based stack. The deque’s thread safety ensures that
these operations won’t interfere with each other, reducing the risk of data corruption.

Synchronization and Locks

Sometimes, you may need to use locks or synchronization mechanisms to coordinate access
to a stack shared among multiple threads, especially when using a standard Python list as
the underlying data structure. The threading module provides tools like Lock, Semaphore,
and Condition to help you manage thread synchronization.

Here’s a simplified example of using a lock to protect a list-based stack:

import threading

# Create a list-based stack

stack = []

# Create a lock to protect the stack

stack_lock = [Link]()

# Define a function to push items onto the stack

def push_item(item):

with stack_lock:

[Link](item)

# Define a function to pop items from the stack

def pop_item():

with stack_lock:

if stack:

return [Link]()
 else:

print("Stack is empty.")

# Create multiple threads to manipulate the stack

thread1 = [Link](target=push_item, args=(1,))

thread2 = [Link](target=push_item, args=(2,))

thread3 = [Link](target=pop_item)

thread4 = [Link](target=pop_item)

# Start the threads

[Link]()

[Link]()

[Link]()

[Link]()

# Wait for all threads to finish

[Link]()

[Link]()

[Link]()

[Link]()

In this example, we use a Lock (stack_lock) to ensure that only one thread can access the
stack at a time. This prevents concurrent access issues and ensures data consistency.

Which Implementation of Stack should one consider?

The choice of which implementation of a stack to consider in Python depends on your

specific requirements and the characteristics of your program. Both lists and deques have
advantages and are suitable for different use cases. Here’s a summary to help you decide
which implementation to consider:

Deque (from the collections module)

 Efficiency: Deques are optimized for fast appends and pops from both ends. They
provide efficient push-and-pop operations, making them an excellent choice for most
stack implementations, especially when dealing with many elements.

 Thread Safety: Deques are inherently thread-safe, which means they can be used in
multi-threaded environments with proper synchronization. A deque-based
implementation is safer if you plan to work with stacks in concurrent programs.
  Memory Efficiency: Deques are memory-efficient, particularly when dealing with
large stacks. They consume less memory than lists because they are implemented as
a double-ended queue.

 Recommended Use Cases: Deques are recommended for most stack

implementations, especially when efficiency and thread safety are crucial
considerations. They are well-suited for scenarios where you must manage many
elements and ensure data integrity in a multi-threaded environment.

List (Python built-in)

 Efficiency: Lists can be slightly less efficient for pop operations, especially when
popping from the left side. They are generally suitable for small stacks or when
additional list functionalities (e.g., random access by index) are required.

 Thread Safety: Lists are not inherently thread-safe. If you plan to use a list-based
stack in a multi-threaded program, you must implement manual synchronization
using locks or other mechanisms to avoid race conditions.

 Memory Efficiency: Lists may consume more memory for large stacks because they
are implemented as dynamic arrays. Consider using a deque if memory efficiency is a
concern, especially for a large stack.

 Recommended Use Cases: Lists are suitable for small stacks or random access by
index. Using a list-based stack is a suitable option if your program is single-threaded
and does not need thread safety.

 Consider adopting a deque-based stack for most situations, especially when you
need efficiency, memory efficiency, and thread safety. Deques are versatile and well-
suited for a wide range of stack implementations. However, if your program is single-
threaded and requires specific list functionalities, you can opt for a list-based stack.
In multi-threaded programs, ensure proper synchronization when using lists to
prevent concurrency issues.

Conclusion

In conclusion, mastering the implementation of stacks in Python is a fundamental skill for

any programmer. Whether you choose to use lists or the deque data structure,
understanding how to efficiently manage data in a Last-In-First-Out (LIFO) manner is
essential.
DSA Stacks

Stacks

A stack is a data structure that can hold many elements.

Result:

push()pop()peek()isEmpty()size()

Think of a stack like a pile of pancakes.

In a pile of pancakes, the pancakes are both added and removed from the top. So when
removing a pancake, it will always be the last pancake you added. This way of organizing
elements is called LIFO: Last In First Out.

Basic operations we can do on a stack are:

 Push: Adds a new element on the stack.

 Pop: Removes and returns the top element from the stack.

 Peek: Returns the top element on the stack.

 isEmpty: Checks if the stack is empty.

 Size: Finds the number of elements in the stack.

Experiment with these basic operations in the stack animation above.

Stacks can be implemented by using arrays or linked lists.

Stacks can be used to implement undo mechanisms, to revert to previous states, to create
algorithms for depth-first search in graphs, or for backtracking.

Stacks are often mentioned together with Queues, which is a similar data structure
described on the next page.

Stack Implementation using Arrays

To better understand the benefits with using arrays or linked lists to implement stacks, you
should check out this page that explains how arrays and linked lists are stored in memory.
This is how it looks like when we use an array as a stack:

3,

2,

4,

Result:

push()pop()peek()isEmpty()size()

Reasons to implement stacks using arrays:

 Memory Efficient: Array elements do not hold the next elements address like linked
list nodes do.

 Easier to implement and understand: Using arrays to implement stacks require less
code than using linked lists, and for this reason it is typically easier to understand as
well.

A reason for not using arrays to implement stacks:

 Fixed size: An array occupies a fixed part of the memory. This means that it could
take up more memory than needed, or if the array fills up, it cannot hold more
elements.

Note: When using arrays in Python for this tutorial, we are really using the Python 'list' data
type, but for the scope of this tutorial the 'list' data type can be used in the same way as an
array. Learn more about Python lists here.

Since Python lists has good support for functionality needed to implement stacks, we start
with creating a stack and do stack operations with just a few lines like this:

Example

Python:

stack = []

# Push

[Link]('A')

[Link]('B')
[Link]('C')

print("Stack: ", stack)

# Pop

element = [Link]()

print("Pop: ", element)

# Peek

topElement = stack[-1]

print("Peek: ", topElement)

# isEmpty

isEmpty = not bool(stack)

print("isEmpty: ", isEmpty)

# Size

print("Size: ",len(stack))

But to explicitly create a data structure for stacks, with basic operations, we should create a
stack class instead. This way of creating stacks in Python is also more similar to how stacks
can be created in other programming languages like C and Java.

Example

Python:

class Stack:

def __init__(self):

[Link] = []

def push(self, element):

[Link](element)
 def pop(self):

if [Link]():

return "Stack is empty"

return [Link]()

def peek(self):

if [Link]():

return "Stack is empty"

return [Link][-1]

def isEmpty(self):

return len([Link]) == 0

def size(self):

return len([Link])

# Create a stack

myStack = Stack()

[Link]('A')

[Link]('B')

[Link]('C')

print("Stack: ", [Link])

print("Pop: ", [Link]())

print("Peek: ", [Link]())

print("isEmpty: ", [Link]())

print("Size: ", [Link]())

Stack Implementation using Linked Lists

A reason for using linked lists to implement stacks:

 Dynamic size: The stack can grow and shrink dynamically, unlike with arrays.

Reasons for not using linked lists to implement stacks:

 Extra memory: Each stack element must contain the address to the next element
(the next linked list node).

 Readability: The code might be harder to read and write for some because it is
longer and more complex.

This is how a stack can be implemented using a linked list.

Example

Python:

class Node:

def __init__(self, value):

[Link] = value

[Link] = None

class Stack:

def __init__(self):

[Link] = None

[Link] = 0

def push(self, value):

new_node = Node(value)

if [Link]:

new_node.next = [Link]
 [Link] = new_node

[Link] += 1

def pop(self):

if [Link]():

return "Stack is empty"

popped_node = [Link]

[Link] = [Link]

[Link] -= 1

return popped_node.value

def peek(self):

if [Link]():

return "Stack is empty"

return [Link]

def isEmpty(self):

return [Link] == 0

def stackSize(self):

return [Link]

myStack = Stack()

[Link]('A')

[Link]('B')

[Link]('C')

print("Pop: ", [Link]())

print("Peek: ", [Link]())

print("isEmpty: ", [Link]())

print("Size: ", [Link]())

Stacks with Python

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle.

Think of it like a stack of pancakes - you can only add or remove pancakes from the top.

Stacks

A stack is a data structure that can hold many elements, and the last element added is the
first one to be removed.

Like a pile of pancakes, the pancakes are both added and removed from the top. So when
removing a pancake, it will always be the last pancake you added. This way of organizing
elements is called LIFO: Last In First Out.

Basic operations we can do on a stack are:

 Push: Adds a new element on the stack.

 Pop: Removes and returns the top element from the stack.

 Peek: Returns the top (last) element on the stack.

 isEmpty: Checks if the stack is empty.

 Size: Finds the number of elements in the stack.

Stacks can be implemented by using arrays or linked lists.

Stacks can be used to implement undo mechanisms, to revert to previous states, to create
algorithms for depth-first search in graphs, or for backtracking.

Stacks are often mentioned together with Queues, which is a similar data structure
described on the next page.

Stack Implementation using Python Lists

For Python lists (and arrays), a stack can look and behave like this:
x = [5, 6, 2, 9, 3, 8, 4, 2]

Add: Remove:

Since Python lists has good support for functionality needed to implement stacks, we start
with creating a stack and do stack operations with just a few lines like this:

ExampleGet your own Python Server

Using a Python list as a stack:

stack = []

# Push
[Link]('A')
[Link]('B')
[Link]('C')
print("Stack: ", stack)

# Peek
topElement = stack[-1]
print("Peek: ", topElement)

# Pop
poppedElement = [Link]()
print("Pop: ", poppedElement)

# Stack after Pop

print("Stack after Pop: ", stack)

# isEmpty
isEmpty = not bool(stack)
print("isEmpty: ", isEmpty)

# Size
print("Size: ",len(stack))

While Python lists can be used as stacks, creating a dedicated Stack class provides better
encapsulation and additional functionality:

Example

Creating a stack using class:

class Stack:
def __init__(self):
 [Link] = []

def push(self, element):

[Link](element)

def pop(self):
if [Link]():
return "Stack is empty"
return [Link]()

def peek(self):
if [Link]():
return "Stack is empty"
return [Link][-1]

def isEmpty(self):
return len([Link]) == 0

def size(self):
return len([Link])

# Create a stack
myStack = Stack()

[Link]('A')
[Link]('B')
[Link]('C')

print("Stack: ", [Link])

print("Pop: ", [Link]())
print("Stack after Pop: ", [Link])
print("Peek: ", [Link]())
print("isEmpty: ", [Link]())
print("Size: ", [Link]())

Reasons to implement stacks using lists/arrays:

 Memory Efficient: Array elements do not hold the next elements address like linked
list nodes do.

 Easier to implement and understand: Using arrays to implement stacks require less
code than using linked lists, and for this reason it is typically easier to understand as
well.
A reason for not using arrays to implement stacks:

 Fixed size: An array occupies a fixed part of the memory. This means that it could
take up more memory than needed, or if the array fills up, it cannot hold more
elements.

Stack Implementation using Linked Lists

A linked list consists of nodes with some sort of data, and a pointer to the next node.

A big benefit with using linked lists is that nodes are stored wherever there is free space in
memory, the nodes do not have to be stored contiguously right after each other like
elements are stored in arrays. Another nice thing with linked lists is that when adding or
removing nodes, the rest of the nodes in the list do not have to be shifted.

To better understand the benefits with using arrays or linked lists to implement stacks, you
should check out this page that explains how arrays and linked lists are stored in memory.

This is how a stack can be implemented using a linked list.

Example

Creating a Stack using a Linked List:

class Node:
def __init__(self, value):
[Link] = value
[Link] = None

class Stack:
def __init__(self):
[Link] = None
[Link] = 0

def push(self, value):

new_node = Node(value)
if [Link]:
new_node.next = [Link]
[Link] = new_node
[Link] += 1

def pop(self):
 if [Link]():
return "Stack is empty"
popped_node = [Link]
[Link] = [Link]
[Link] -= 1
return popped_node.value

def peek(self):
if [Link]():
return "Stack is empty"
return [Link]

def isEmpty(self):
return [Link] == 0

def stackSize(self):
return [Link]

def traverseAndPrint(self):
currentNode = [Link]
while currentNode:
print([Link], end=" -> ")
currentNode = [Link]
print()

myStack = Stack()
[Link]('A')
[Link]('B')
[Link]('C')

print("LinkedList: ", end="")

[Link]()
print("Peek: ", [Link]())
print("Pop: ", [Link]())
print("LinkedList after Pop: ", end="")
[Link]()
print("isEmpty: ", [Link]())
print("Size: ", [Link]())

A reason for using linked lists to implement stacks:

 Dynamic size: The stack can grow and shrink dynamically, unlike with arrays.
Reasons for not using linked lists to implement stacks:

 Extra memory: Each stack element must contain the address to the next element
(the next linked list node).

 Readability: The code might be harder to read and write for some because it is
longer and more complex.

Common Stack Applications

Stacks are used in many real-world scenarios:

 Undo/Redo operations in text editors

 Browser history (back/forward)

 Function call stack in programming

 Expression evaluation

Stack Data Structure

A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This
means the last element inserted inside the stack is removed first.

You can think of the stack data structure as the pile of plates on top of another.
 Stack representation
similar to a pile of plate

Here, you can:

 Put a new plate on top

 Remove the top plate

And, if you want the plate at the bottom, you must first remove all the plates on top. This is
exactly how the stack data structure works.

LIFO Principle of Stack

In programming terms, putting an item on top of the stack is called push and removing an
item is called pop.
Stack Push and Pop Operations

In the above image, although item 3 was kept last, it was removed first. This is exactly how
the LIFO (Last In First Out) Principle works.

We can implement a stack in any programming language like C, C++, Java, Python or C#, but
the specification is pretty much the same.

Basic Operations of Stack

There are some basic operations that allow us to perform different actions on a stack.

 Push: Add an element to the top of a stack

 Pop: Remove an element from the top of a stack

 IsEmpty: Check if the stack is empty

 IsFull: Check if the stack is full

 Peek: Get the value of the top element without removing it

Working of Stack Data Structure

The operations work as follows:

1. A pointer called TOP is used to keep track of the top element in the stack.
 2. When initializing the stack, we set its value to -1 so that we can check if the stack is
empty by comparing TOP == -1.

3. On pushing an element, we increase the value of TOP and place the new element in
the position pointed to by TOP.

4. On popping an element, we return the element pointed to by TOP and reduce its
value.

5. Before pushing, we check if the stack is already full

6. Before popping, we check if the stack is already empty

Working of Stack Data Structure

Stack Implementations in Python, Java, C, and C++

Stack Visualization: Don't just read about stack, watch it happen live. See how each line of
the data structure works step-by-step with our new DSA visualizer. Try it yourself!

The most common stack implementation is using arrays, but it can also be implemented
using lists.

Python

Java

C++

# Stack implementation in python

# Creating a stack

def create_stack():

stack = []

return stack

# Creating an empty stack

def check_empty(stack):

return len(stack) == 0

# Adding items into the stack

def push(stack, item):

[Link](item)

print("pushed item: " + item)

# Removing an element from the stack

def pop(stack):

if (check_empty(stack)):

return "stack is empty"

return [Link]()

stack = create_stack()
push(stack, str(1))

push(stack, str(2))

push(stack, str(3))

push(stack, str(4))

print("popped item: " + pop(stack))

print("stack after popping an element: " + str(stack))

Stack Time Complexity

For the array-based implementation of a stack, the push and pop operations take constant
time, i.e. O(1).

Applications of Stack Data Structure

Although stack is a simple data structure to implement, it is very powerful. The most
common uses of a stack are:

 To reverse a word - Put all the letters in a stack and pop them out. Because of the
LIFO order of stack, you will get the letters in reverse order.

 In compilers - Compilers use the stack to calculate the value of expressions like 2 +
4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.

Stack - Linked List Implementation

Last Updated : 13 Sep, 2025

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It can be
implemented using a linked list, where each element of the stack is represented as a node.
The head of the linked list acts as the top of the stack.

Declaration of Stack using Linked List

A stack can be implemented using a linked list where we maintain:

  A Node structure/class that contains:
data → to store the element.
next → pointer/reference to the next node in the stack.

 A pointer/reference top that always points to the current top node of the stack.
Initially, top = null to represent an empty stack.

Try it on GfG Practice

# Node structure

class Node:

def __init__(self, x):

[Link] = x

[Link] = None

# Stack class

class myStack:

def __init__(self):

# initially stack is empty

[Link] = None

Operations on Stack using Linked List

Push Operation

Adds an item to the stack. Unlike array implementation, there is no fixed capacity in linked
list. Overflow occurs only when memory is exhausted.

 A new node is created with the given value.

 The new node’s next pointer is set to the current top.

 The top pointer is updated to point to this new node.

def push(self, x):

temp = Node(x)

[Link] = [Link]

[Link] = temp

Time Complexity: O(1)

Auxiliary Space: O(1)

Pop Operation

Removes the top item from the stack. If the stack is empty, it is said to be an Underflow
condition.

 Before deleting, we check if the stack is empty (top == NULL).

 If the stack is empty, underflow occurs and deletion is not possible.

 Otherwise, we store the current top node in a temporary pointer.

 Move the top pointer to the next node.

 Delete the temporary node to free memory.

def pop(self):

if [Link] is None:

print("Stack Underflow")

return -1

temp = [Link]

[Link] = [Link]

val = [Link]

del temp

return val

Time Complexity: O(1)

Auxiliary Space: O(1)

Peek (or Top) Operation

Returns the value of the top item without removing it from the stack.

 If the stack is empty (top == NULL), then no element exists.

 Otherwise, simply return the data of the node pointed by top.

def peek(self):

if [Link] is None:

print("Stack is Empty")

return -1

return [Link]

Time Complexity: O(1)

Auxiliary Space: O(1)

isEmpty Operation

Checks whether the stack has no elements.

 If the top pointer is NULL, it means the stack is empty and the function returns true.

 Otherwise, it returns false.

def isEmpty(self):

return [Link] is None

Time Complexity: O(1)

Auxiliary Space: O(1)

Stack Implementation using Linked List

# Node structure

class Node:

def __init__(self, x):

[Link] = x

[Link] = None

# Stack implementation using linked list

class myStack:
def __init__(self):

# initially stack is empty

[Link] = None

[Link] = 0

# push operation

def push(self, x):

temp = Node(x)

[Link] = [Link]

[Link] = temp

[Link] += 1

# pop operation

def pop(self):

if [Link] is None:

print("Stack Underflow")

return -1

temp = [Link]

[Link] = [Link]

val = [Link]

[Link] -= 1

return val

# peek operation

def peek(self):

if [Link] is None:
 print("Stack is Empty")

return -1

return [Link]

# check if stack is empty

def isEmpty(self):

return [Link] is None

# size of stack

def size(self):

return [Link]

if __name__ == "__main__":

st = myStack()

# pushing elements

[Link](1)

[Link](2)

[Link](3)

[Link](4)

# popping one element

print("Popped:", [Link]())

# checking top element

print("Top element:", [Link]())

 # checking if stack is empty

print("Is stack empty:", "Yes" if [Link]() else "No")

# checking current size

print("Current size:", [Link]())

Output

Popped: 4

Top element: 3

Is stack empty: No

Current size: 3