Question

Implementation of stacks in python explain

Answer 1

A stack is a collection of objects that supports fast last-in, first-out (LIFO)semantics for inserts and deletes. Unlike lists or arrays, stacks typically don’t allow for random access to the objects they contain. The insert and delete operations are also often called push and pop.

Stacks and queues are similar. They’re both linear collections of items and the difference lies in the order that items are accessed in:

With a queue you remove the item least recently added (first-in, first-out or FIFO); and with a stack you remove the item most recently added (last-in, first-out or LIFO).

Performance-wise, a proper stack implementation is expected to take O(1)time for insert and delete operations.

Stacks have a wide range of uses in algorithms, for example in language parsing and runtime memory management (“call stack”). A short and beautiful algorithm using a stack is depth-first search (DFS) on a tree or graph data structure.

Python ships with several stack implementations that each have slightly different characteristics. Let’s take a look at them:

Python’s built-in list type makes a decent stack data structure as it supports push and pop operations in amortized O(1) time.

Python’s lists are implemented as dynamic arrays internally which means they occasional need to resize the storage space for elements stored in them when elements are added or removed. The list over-allocates its backing storage so that not every push or pop requires resizing and you get an amortized O(1) time complexity for these operations.

The downside is that this makes their performance less consistent than the stable O(1) inserts and deletes provided by a linked list based implementation (like collections.deque, see below). On the other hand lists do provide fast O(1) time random access to elements on the stack which can be an added benefit.

Here’s an important performance caveat when using lists as stacks:

To get the amortized O(1) performance for inserts and deletes new items must be added to the end of the list with the append() method and removed again from the end using pop(). Stacks based on Python lists grow to the right and shrink to the left.

Adding and removing from the front is much slower and takes O(n) time, as the existing elements must be shifted around to make room for the new element.