Three Ways to Implement Stack in python

Stack is a linear data structure, which stores data in a first-in-last-out or last-in-first-out manner. The insertion and deletion operations of data in the stack are all carried out at the top of the stack. Common stack function operations include

empty () returns whether the stack is empty Time Complexity: O (1) size () Returns the length of the stack Time Complexity: O (1) top () View Stack Top Element Time Complexity: O (1) push (g) Adds elements Time Complexity: O (1) to the top of the stack pop () Delete top element Time Complexity: O (1)

The stack in python can be implemented in three ways:

1) list

2) collections. deque

3) queue. LifoQueue

Using a list to implement a stack

list, the built-in data structure of python, can be used to implement the stack. append () can be used to add elements to the top of the stack, and pop () can delete elements in a last-in-first-out order

But the list itself has one drawback, The main problem is that when the list keeps expanding, it will encounter a speed bottleneck. The list is a dynamic array, So when you add a new element to it and there is no room to hold the new element, it automatically reallocates the memory block and copies the values from the original memory to the new memory block. This causes some append () operations to consume more time

>>> stack = []
>>> #append() fuction to push
... #element in list
... 
>>> stack.append('hello')
>>> stack.append('world')
>>> stack.append('!')
>>> print('Initial stack')
Initial stack
>>> print(stack)
['hello', 'world', '!']
>>> #pop() function to pop element
... #from stack in LIFO order
... 
>>> print('\nElement poped from stack')

Element poped from stack

>>> print(stack.pop())
!
>>> print(stack.pop())
world
>>> print(stack.pop())
hello
>>> print('\nStack after all elements are poped')

Stack after all elements are poped
>>> print(stack)
[]

Implementation stack using collections. deque

The stack in python can also be implemented with the deque class, and deque is more appropriate than the list when we want to implement append and pop operations at both ends of the container more quickly. deque can provide append and pop operations at O (1) time, while the list requires O (n) time.

>>> from collections import deque
>>> stack = deque()
>>> # append() fuction to push
... #element in list
... 
>>> stack.append('hello')
>>> stack.append('world')
>>> stack.append('!')
>>> print('Initial stack')
Initial stack
>>> print(stack)
deque(['hello', 'world', '!'])
>>> #pop() function to pop element
... #from stack in LIFO order
... 
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.pop())
!
>>> print(stack.pop())
world
>>> print(stack.pop())
hello
>>> print('\nStack after all elements are poped')

Stack after all elements are poped
>>> print(stack)deque([])

Implementation stack using queue module

The Queue module has an LIFO queue, which is the stack structure. Use the put () and get () operations to add and obtain data from the Queue

>>> from queue import LifoQueue
>>> stack = LifoQueue(maxsize = 3)
>>> print(stack.qsize())
0
>>> stack.put('hello')
>>> stack.put('world')
>>> stack.put('!')
>>> print('\nElement poped from stack')

Element poped from stack
>>> print(stack.get())
!
>>> print(stack.get())
world
>>> print(stack.get())
hello
>>> print('\nEmpty:', stack.empty())

Empty: True

The above is the python implementation of the 3 methods of stack details, more about python implementation stack information please pay attention to other related articles on this site!