Open In App

Stack in Python

Last Updated : 20 Jun, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.

Stack in python

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() / peek() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)
  • push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)
  • pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

Implementation:

There are various ways from which a stack can be implemented in Python. This article covers the implementation of a stack using data structures and modules from the Python library. 
Stack in Python can be implemented using the following ways: 

  • list
  • Collections.deque
  • queue.LifoQueue

Implementation using list:

Python’s built-in data structure list can be used as a stack. Instead of push(), append() is used to add elements to the top of the stack while pop() removes the element in LIFO order. 
Unfortunately, the list has a few shortcomings. The biggest issue is that it can run into speed issues as it grows. The items in the list are stored next to each other in memory, if the stack grows bigger than the block of memory that currently holds it, then Python needs to do some memory allocations. This can lead to some append() calls taking much longer than other ones.

Python
# Python program to
# demonstrate stack implementation
# using list

stack = []

# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack')
print(stack)

# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty

Output
Initial stack
['a', 'b', 'c']

Elements popped from stack:
c
b
a

Stack after elements are popped:
[]

Implementation using collections.deque:

Python stack can be implemented using the deque class from the collections module. Deque is preferred over the list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity. 

 

The same methods on deque as seen in the list are used, append() and pop().

Python
# Python program to
# demonstrate stack implementation
# using collections.deque

from collections import deque

stack = deque()

# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')

print('Initial stack:')
print(stack)

# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty

Output
Initial stack:
deque(['a', 'b', 'c'])

Elements popped from stack:
c
b
a

Stack after elements are popped:
deque([])

Implementation using queue module

Queue module also has a LIFO Queue, which is basically a Stack. Data is inserted into Queue using the put() function and get() takes data out from the Queue. 

There are various functions available in this module: 

  • maxsize – Number of items allowed in the queue.
  • empty() – Return True if the queue is empty, False otherwise.
  • full() – Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
  • get() – Remove and return an item from the queue. If the queue is empty, wait until an item is available.
  • get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
  • put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
  • put_nowait(item) – Put an item into the queue without blocking. If no free slot is immediately available, raise QueueFull.
  • qsize() – Return the number of items in the queue.
Python
# Python program to
# demonstrate stack implementation
# using queue module

from queue import LifoQueue

# Initializing a stack
stack = LifoQueue(maxsize=3)

# qsize() show the number of elements
# in the stack
print(stack.qsize())

# put() function to push
# element in the stack
stack.put('a')
stack.put('b')
stack.put('c')

print("Full: ", stack.full())
print("Size: ", stack.qsize())

# get() function to pop
# element from stack in
# LIFO order
print('\nElements popped from the stack')
print(stack.get())
print(stack.get())
print(stack.get())

print("\nEmpty: ", stack.empty())

Output
0
Full:  True
Size:  3

Elements popped from the stack
c
b
a

Empty:  True

Implementation using a singly linked list:

The linked list has two methods addHead(item) and removeHead() that run in constant time. These two methods are suitable to implement a stack. 

  • getSize()– Get the number of items in the stack.
  • isEmpty() – Return True if the stack is empty, False otherwise.
  • peek() – Return the top item in the stack. If the stack is empty, raise an exception.
  • push(value) – Push a value into the head of the stack.
  • pop() – Remove and return a value in the head of the stack. If the stack is empty, raise an exception.

Below is the implementation of the above approach:

Python
# Python program to demonstrate
# stack implementation using a linked list.
# node class

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:

    # Initializing a stack.
    # Use a dummy node, which is
    # easier for handling edge cases.
    def __init__(self):
        self.head = Node("head")
        self.size = 0

    # String representation of the stack
    def __str__(self):
        cur = self.head.next
        out = ""
        while cur:
            out += str(cur.value) + "->"
            cur = cur.next
        return out[:-2]

    # Get the current size of the stack
    def getSize(self):
        return self.size

    # Check if the stack is empty
    def isEmpty(self):
        return self.size == 0

    # Get the top item of the stack
    def peek(self):

        # Sanitary check to see if we
        # are peeking an empty stack.
        if self.isEmpty():
            return None

        return self.head.next.value

    # Push a value into the stack.
    def push(self, value):
        node = Node(value)
        node.next = self.head.next # Make the new node point to the current head
        self.head.next = node #!!! # Update the head to be the new node
        self.size += 1


    # Remove a value from the stack and return.
    def pop(self):
        if self.isEmpty():
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = remove.next #!!! changed
        self.size -= 1
        return remove.value


# Driver Code
if __name__ == "__main__":
    stack = Stack()
    for i in range(1, 11):
        stack.push(i)
    print(f"Stack: {stack}")

    for _ in range(1, 6):
        top_value = stack.pop()
        print(f"Pop: {top_value}") # variable name changed
    print(f"Stack: {stack}")

Output

Stack: 10->9->8->7->6->5->4->3->2->1
Pop: 10
Pop: 9
Pop: 8
Pop: 7
Pop: 6
Stack: 5->4->3->2->1

Advantages of Stack:

  • Stacks are simple data structures with a well-defined set of operations, which makes them easy to understand and use.
  • Stacks are efficient for adding and removing elements, as these operations have a time complexity of O(1).
  • In order to reverse the order of elements we use the stack data structure.
  • Stacks can be used to implement undo/redo functions in applications.

Drawbacks of Stack:

  • Restriction of size in Stack is a drawback and if they are full, you cannot add any more elements to the stack.
  • Stacks do not provide fast access to elements other than the top element.
  • Stacks do not support efficient searching, as you have to pop elements one by one until you find the element you are looking for.

Stack in Python – FAQs

How to create a stack in Python?

A stack can be created in Python using a list. You can use list methods like append() to push elements onto the stack and pop() to remove elements from the stack. Here’s a simple example:

stack = []
# Push elements onto the stack
stack.append(1)
stack.append(2)
stack.append(3)
print("Stack after pushes:", stack)
# Pop elements from the stack
print("Popped element:", stack.pop())
print("Stack after pop:", stack)

How to inspect a stack in Python?

To inspect a stack, you can simply look at its elements using standard list operations. You can access the top element without removing it using indexing. Here’s an example:

stack = [1, 2, 3]
# Inspect the top element
top_element = stack[-1] if stack else None
print("Top element:", top_element)
# Check if the stack is empty
is_empty = len(stack) == 0
print("Is the stack empty?", is_empty)
# View the entire stack
print("Current stack:", stack)

How to use a stack in Python?

To use a stack in Python, you typically perform push and pop operations using list methods. Here’s a more complete example showing these operations:

stack = []
# Push elements onto the stack
stack.append(10)
print("Stack after pushes:", stack)
# Inspect the top element
print("Top element:", stack[-1])
# Pop elements from the stack
while stack:
print("Popped element:", stack.pop())

Is a stack in Python implemented as a list?

Yes, in Python, a stack is commonly implemented using a list. The list’s append() method is used to push elements onto the stack, and the pop() method is used to remove elements from the stack. Lists in Python provide an efficient way to implement stack operations.

Does Python have a built-in stack type?

Python does not have a dedicated built-in stack type, but you can use lists or the collections.deque class from the collections module for stack operations. The deque class is optimized for fast append and pop operations from both ends of the deque.

Using deque can be more efficient for stack operations compared to using a list, especially when dealing with larger datasets.



Previous Article
Next Article

Similar Reads

Find maximum in stack in O(1) without using additional stack in Python
The task is to design a stack which can get the maximum value in the stack in O(1) time without using an additional stack in Python. Examples: Input: Consider the following SpecialStack 16 –> TOP29151918When getMax() is called it should return 29, which is the maximum element in the current stack. If we do pop two times on stack, the stack becom
3 min read
Stack and Queue in Python using queue Module
A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generally created in languages such as C/C++ and Java. 1.
3 min read
Python Program to Reverse the Content of a File using Stack
Given a file, the task is to change the content in reverse order using Stack, as well as store the lines of that file in reverse order in Python. Examples: Input: 1 2 3 4 5 Output: 5 4 3 2 1 Approach to Python Program to Reverse a Stack Using Recursion Create an empty stack. One by one push every line of the file to the stack. One by one pop each l
2 min read
numpy.stack() in Python
NumPy is a famous Python library used for working with arrays. One of the important functions of this library is stack(). Important points:stack() is used for joining multiple NumPy arrays. Unlike, concatenate(), it joins arrays along a new axis. It returns a NumPy array.to join 2 arrays, they must have the same shape and dimensions. (e.g. both (2,
5 min read
Python | Stack using Doubly Linked List
A stack is a collection of objects that are inserted and removed using Last in First out Principle(LIFO). User can insert elements into the stack, and can only access or remove the recently inserted object on top of the stack. The main advantage of using LinkedList over array for implementing stack is the dynamic allocation of data whereas in the a
4 min read
How are variables stored in Python - Stack or Heap?
Memory allocation can be defined as allocating a block of space in the computer memory to a program. In Python memory allocation and deallocation method is automatic as the Python developers created a garbage collector for Python so that the user does not have to do manual garbage collection. Garbage Collection Garbage collection is a process in wh
3 min read
Python - Stack and StackSwitcher in GTK+ 3
A Gtk.Stack is a container which allows visibility to one of its child at a time. Gtk.Stack does not provide any direct access for users to change the visible child. Instead, the Gtk.StackSwitcher widget can be used with Gtk.Stack to obtain this functionality. In Gtk.Stack transitions between pages can be done by means of slides or fades. This can
2 min read
How to print exception stack trace in Python?
Prerequisite: Python Traceback To print stack trace for an exception the suspicious code will be kept in the try block and except block will be employed to handle the exception generated. Here we will be printing the stack trace to handle the exception generated. The printing stack trace for an exception helps in understanding the error and what we
3 min read
Python program to reverse a stack
The stack is a linear data structure which works on the LIFO concept. LIFO stands for last in first out. In the stack, the insertion and deletion are possible at one end the end is called the top of the stack. In this article, we will see how to reverse a stack using Python. Algorithm: Define some basic function of the stack like push(), pop(), sho
3 min read
Python PyTorch stack() method
PyTorch torch.stack() method joins (concatenates) a sequence of tensors (two or more tensors) along a new dimension. It inserts new dimension and concatenates the tensors along that dimension. This method joins the tensors with the same dimensions and shape. We could also use torch.cat() to join tensors But here we discuss the torch.stack() method.
5 min read
Article Tags :
Practice Tags :