Stack in Python (LIFO Queue)

Implementation of the Standard Stack Functions

empty( )

This method is used to check if the stack is empty. 

 

While creating a stack in Python with lists, we will use the bool( ) method, which takes a list as a parameter. This method returns a boolean value depending on whether the list is empty. 
 

For example, 

stack = [1,2,3,4,5]
print(bool(stack))

Output:

 

True

Here the output is True since the stack contains data. 

stack = []
print(bool(stack))

 

Output:

False

 

Here the output is false since the stack is empty.

size( )

The size of a list can be found by using the len( ) method. 

Similarly, the stack size in Python can be found using the same method since our stack here is a list.

stack = [1,2,3,4,5]
print(len(stack))

 

Output:

5

top( )

To print the last element in the stack, we will use its index as shown below:

Remember: List supports two-way indexing as shown below.

 

stack = [1,2,3,4,5]
print(stack[-1])#using backward indexing
print(stack[len(stack)-1])

 

Both print statements will give the same output:

5

 

Here, len(stack) gives us the length of the stack, i.e., 5. So the element present in the index 5 - 1 = 4 in the list will be printed. That element is the last, as seen below. 

push( )

To add an element to a stack in Python, we will have to add it to the end of our list. To do that, there is a predefined method in Python - append( ). 

stack = [1,2,3,4,5]
print(stack)
stack.append(6)
print(stack)

 

Output:

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

 

pop( )

In Python, a pop( ) method takes an index as a parameter and removes the element in that index from the list. 

In a stack in Python, we want to remove only the last element. So, to do that, we won’t give any parameter to the function, and the last element in the list will be popped as it happens in a stack.  

stack = [1,2,3,4,5]
print(stack)
stack.pop()
print(stack)

 

Output:

[1, 2, 3, 4, 5]
[1, 2, 3, 4]

 

Implementing a stack in Python with a list may seem easy, but it has a big disadvantage. 

Like arrays, lists store the data in contiguous memory locations. So, if a lot of data is added to the stack, it may grow bigger than its memory block. Due to this reason, the working of the stack may slow down. 

 

To overcome this problem, there is a faster alternative. 

Let us see what it is next!

 

You can also practice with the help of Online Python Compiler

Stack in Python Using the Deque Class

Python provides a container class used to store collections of data - the collection module. There is a deque class in the collection module that we can use to implement stacks in Python. The general syntax for that is:

from collections import deque
stack = deque( )

 

After creating the stack, we will want to add elements to it. The method to push elements into a stack is the same as that in lists.

from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
print(list(stack))

 

The rest of the standard methods in a stack using deque are the same as a list! Let’s see it for ourselves in the code below:

from collections import deque
stack = deque()

#pushing elements to stack
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
print("Stack:",list(stack))

#to check if stack is empty
print("Does stack have elements? T/F",bool(stack))

#to find the size of the stack
print("Size is",len(stack))

#to print the topmost element
print("Top is",stack[-1])

#to pop an element
print(stack[-1],"is popped")
stack.pop()
print("Stack:",list(stack))

 

Output:

Stack: [1, 2, 3, 4, 5]
Does stack have elements? T/F True
Size is 5
Top is 5
5 is popped
Stack: [1, 2, 3, 4]

 

With this, we finish learning how to use a list and the deque class as a stack in Python, but are these the only way?

Let us learn the next method then!

 

Stack in Python Using the Queue Module

There is another module available in Python called Queue. This can also be used to implement a stack in Python. 

The queue model provides an additional feature of providing bounds to the stack. 

• We can specify the size by passing a parameter maxsize to the LifoQueue( ) method. maxsize is an integer that sets the upperbound limit on the number of items that can be placed in the queue. Insertion will block once this size has been reached, until queue items are consumed. If maxsize is less than or equal to zero, the queue size is infinite.

 

The general syntax to create a stack using the queue module is as follows:

from queue import LifoQueue
stack = LifoQueue(maxsize=0)

 

Let’s see how the standard methods in a stack are used here next.
Must Read Python List Operations

Implementation of the Standard Stack Functions

empty( )

The empty( ) function can check if the stack is empty, as shown below. Unlike the bool( ) method we used previously, this method returns True if the stack is empty and False if it isn’t. 

from queue import LifoQueue
stack = LifoQueue()
print(stack.empty())

 

Output:

True

size( )

Here, the qsize( ) method returns the number of elements present in the stack.

from queue import LifoQueue
stack = LifoQueue(maxsize=5)
print(stack.qsize())

 

Output:

0

 

Note: Here, the stack size is 0 even though we set the max size as 5 because there are no elements in the stack. Once we push elements to the stack, the qsize( ) method returns the number of elements present.
 

put( )

Here, the method to push elements to the stack is put( ). Here, if the stack has reached its maximum capacity, it will wait for space to push the element. It is used as shown below: 

from queue import LifoQueue
stack = LifoQueue(maxsize=5)
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
#task_done shows a message after the operations on the stack are completed
stack.task_done  

 

Output:

<bound method Queue.task_done of <queue.LifoQueue object at 0x7f9d3848ad50>>

 

Another method that can be used here is put_nowait( ). This method pushes an element into the stack if there is space, and if there isn’t space, it raises an error and terminates execution. 

from queue import LifoQueue
stack = LifoQueue(maxsize=5)
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
stack.put_nowait(6)

 

Output:

---------------------------------------------------------------------------

Full                                      Traceback (most recent call last)

<ipython-input-34-0dad904af3c6> in <module>()

      6 stack.put(4)

      7 stack.put(5)

----> 8 stack.put_nowait(6)

 

get( )

The get( ) method pops and returns the topmost element in the stack. This method will also wait until an element is available if it is called when the stack is empty.

from queue import LifoQueue
stack = LifoQueue(maxsize=5)
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
print(stack.get())

 

Output:

5

 

A get_nowait( ) method also exists, which gives an error message while popping from an empty stack.

from queue import LifoQueue
stack = LifoQueue(maxsize=5)
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
print(stack.get())
print(stack.get())
print(stack.get())
print(stack.get())
print(stack.get())
print(stack.get_nowait())

 

Output:

5
4
3
2
1

---------------------------------------------------------------------------

Empty                                     Traceback (most recent call last)

<ipython-input-35-93e8ac25c7ea> in <module>()

     11 print(stack.get())

     12 print(stack.get())

---> 13 print(stack.get_nowait())

 

Note: Try using the put( ) and pop( ) methods after the size of the stack has exceeded, or the stack is empty, respectively. 

full( )

An additional method exists for stacks in Python using the queue module - the full( ) function. This function checks whether the stack has reached its maximum capacity or, in other words, whether there is a maxsize number of elements in the stack.  

from queue import LifoQueue
stack = LifoQueue(maxsize=5)
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
print(stack.full())

 

Output:

True

 

Must Read Stack Operations

Complexity Analysis

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(ele) – Adds the element ‘ele’ at the top of the stack – Time Complexity : O(1) 

pop() – Deletes the top most element of the stack – Time Complexity : O(1) 
 

This brings us to the end of our Python stacks discussion. But, before we move on, did you know that Linked List can also be used to implement stacks?

Without further ado, see how to Implement Stack with Linked List and solve this frequently asked question in Amazon on Coding Ninjas Studio.
 

Let us now see some commonly asked questions to go through what we just learned.

Read about Application of Queue in Data Structure here.

Check out Escape Sequence in Python

Frequently Asked Questions

What is a stack?

A stack is a data structure that works on the Last In First Out (LIFO) principle.

What are the standard methods for a stack?

The standard methods for a stack are:
(i)empty( )
(ii)size( )
(iii)top( )
(iv)push( )
(v)pop( )

What are the different methods to implement a stack in Python?

The different methods to implement stack in Python are:
(i)Using lists
(ii)Using the Deque class
(iii)Using the Queue module
(iv)Using Linked List

Is a stack in Python different from that in other programming languages?

No, a stack in Python is the same as in any other programming language.

How is a stack different from a queue?

A stack works on the Last In First Out (LIFO) principle, while a queue works on the First In First Out (FIFO) principle.

Conclusion

In this article, we learned how to use a stack in Python, but what next?

Stack is used in many common competitive programming questions like:

• Infix to postfix
• Postfix to prefix
• Prefix to infix
• Mergeable Stack
• Expression Evaluation Using Stack
• Next greater/smaller element using a monotonic queue
• Advantages of Circular Queue
• Simplifying a directory

More problems with stacks can be found here.

Other than just stacks, we can find common coding questions and the interview experience of professionals all in one place - Coding Ninjas Studio.

You can also consider our Mern Stack Course to give your career an edge over others.

Happy Learning!