Python Stacked List
Stack is a linear collection of objects which stores the objects in the Last-in, First-out (LIFO) format. It is used for insertion and deletion. These insert and delete operations are also called as push and pop actions. In stack, an element is removed at the end where it has been added previously at the same end.
Stack is an array or list of function calls and parameters which are used in CPU architecture and modern computer programming. Stack does not support random access unlike lists or arrays. An example for use case of stack is undo option in editor. As we all know, undo option is used for deleting last made changes, simply it just follows LIFO format.
There are two types of operations in Stack, push and pop.
- Push is used to add or insert the data into the stack.
- Pop is used to remove or delete the recent data in the stack.
There are also different functions associated with Stack.
- empty() – This function returns whether the stack is empty or not.
- size() – This function displays the size of the stack.
- top() – Top function returns a reference of the top most element of the stack.
- push() – Push inserts or adds the element at the top of the stack.
- pop() – Pop deletes or removes the top most element or recently added element of the stack.
There are three basic implementations of Stack in Python.
- List
- collections.deque
- queue.Lifoqueue
Implementing Python Stack using list.
When we are using list to create a Python Stack, append()
function is used to insert or push an element into the stack. pop() function is
used to pop or remove the elements in the stack in the LIFO order. The
disadvantage using list to create a stack is that, if the elements or items in
the stack are more in number than the capability of memory storage of list,
then this leads to the memory allocations which can lead to some append() calls taking much longer than other ones. Because elements in list are stored beside
each other.
Python Code:
#Creating a empty list for Stack
stack = []
# append() function to push or insert element in the stack
stack.append('root')
stack.append('branch')
stack.append('stem')
stack.append('leaves')
stack.append('flowers')
print("stack after appending elements:",stack)
# pop() fucntion to remove element from stack in LIFO order
print('\nElements poped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are poped:')
print(stack)
Output:
stack after appending elements: [‘root’, ‘branch’, ‘stem’, ‘leaves’, ‘flowers’]
Elements poped from stack:
flowers
leaves
stem
Stack after elements are poped:
[‘root’, ‘branch’]
Implementing Python Stack using collection.deque
Stack can also be created by using deque class from collection module. Deque means double ended queue. It is better than list implementation as it is quicker in the append and pop operations than list. It provides O(1) time complexity for the insert and delete operations, whereas list consumes O(n) time.
Python Code:
from collections import deque
stack = deque()
# append() function to push or insert element in the stack
stack.append('root')
stack.append('branch')
stack.append('stem')
stack.append('leaves')
stack.append('flowers')
print("stack after appending elements:",stack)
# pop() fucntion to remove element from stack in LIFO order
print('\nElements poped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are poped:')
print(stack)
Output:
stack after appending elements: deque([‘root’, ‘branch’, ‘stem’, ‘leaves’, ‘flowers’])
Elements poped from stack:
flowers
leaves
stem
Stack after elements are poped:
deque([‘root’, ‘branch’])
Implementation of Stack using queue.Lifoqueue
It is one of the modules in Python which has LIFO queue, which is generally a stack. It uses put() function in order to insert or push an element into the stack. get() function is used to pop or delete the recently added element from the stack.
Python Code:
from queue import LifoQueue
stack = LifoQueue()
stack.put('root')
stack.put('branch')
stack.put('stem')
stack.put('leaves')
stack.put('flowers')
print("stack after appending elements:",stack)
# pop() fucntion to remove element from stack in LIFO order
print('\nElements poped from stack:')
print(stack.get())
print(stack.get())
print(stack.get())
print('\nStack after elements are poped:')
print(stack)
Output:
stack after appending elements: <queue.LifoQueue object at 0x000001D464BAB668>
Elements poped from stack:
flowers
leaves
stem
Stack after elements are poped:
<queue.LifoQueue object at 0x000001D464BAB668>
