Implementing Stack using List in Python – Python Programming Essentials

- - Web

Intro

Stack is a collection of objects inserted and removed in a last-in first-out fashion (LIFO). Objects can be inserted onto stack at any time but only the object inserted last can be accessed or removed which coins the object to be top of the stack.

Realization of Stack Operations using List

 

Methods Realization using List Running Time
S.push(e) L.append(e) O(1)*
S.pop() L.pop() O(1)*
S.top() L[-1] O(1)
S.isempty() len(L) == 0 O(1)
len(S) len(L) O(1)

What is O(1)* ?

The running time for push and pop operations are given O(1)* in the above table. This is known as amortization. It is a principle used in complexity analysis of data structures and algorithms. It should be used carefully and for special cases only.

Why did we use amortized analysis for push/pop?

The list(our stack’s underlying data structure) is a series of objects which eventually are realized by arrays. The objects are stored in a continuous block of memory which offers indexing property for lists. As such, a list cannot occupy the entire memory but restricts to some specific size. When there is no more space for the objects to be added to the end of the list, a new memory series is allocated with the increased size, all the objects are copied to the new allocation and new object is added next to the last object of the current series. The previously held memory is then released free. Here, on every append, resizing of list is not required but true once in a while. Hence the running time of append in list (push on stack) for most elements is O(1) but as a whole in an amortized sense, it is O(1)* which accounts for the timely resizing and copying of elements.

Similarly for pop operations, shrinking of the underlying list is done once in a while therefore accounting for an amortized complexity of O(1)*

Implementation of Stack using List

 

class ListStack:
    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)


    def isempty(self):
        return len(self._data) == 0

    def top(self):
        return self._data[-1]

    def push(self, e):
        self._data.append(e)

    def pop(self):
        return self._data.pop()

Conclusion

Stack is an important data structure for realizing solutions to various programming problems. As such, it is even more essential to understand the running time evaluations and working mechanism of these data structures.

Follow me on github Github

Hire me for a project Fiverr

Post Tags:

bhishan

I am Bhishan Bhandari, a CS student and life hacker. I specialize in automation. I sell my services on fiverr. You can hire me for projects here Buy Services Follow me on github for code updates Github You can always communicate your thoughts/wishes/questions to me at bbhishan@gmail.com

There Are 3 Comments On This Article.

  1. Instead of `ismepty()` in python it’s common to use `__bool__()` (python3), or if it’s python2: `__nonzero__`.

    Instead of `len(self._data) == 0` PEP8 recommends to use `bool(self._data)` check
    https://www.python.org/dev/peps/pep-0008/
    “For sequences, (strings, lists, tuples), use the fact that empty sequences are false.”

    It’s also recommended to use `collectoins.deque()` instead of `list()` in your use case:
    https://wiki.python.org/moin/TimeComplexity

  2. Dan Stromberg

    When I was in school, we were taught to abstract away details like what you’ve done here. They said every major decision your code makes, should be abstracted so you can change it later if you need to.

    Today, in modern python, it’s not unheard of to blame performance problems on “too much abstraction”. It’s common to just use a list or collections.deque directly, even though they are capable of being used in inappropriate ways.

    I too wrote a (well abstracted) stack implementation in Python. You can find it here: http://stromberg.dnsalias.org/~strombrg/linked-list/
    It’s O(1) (not amortized) for common operations, because it uses a linked list.

    However, it should be quite slow compared to a collections.deque or even compared to a builtin list implementation – mostly because of memory latency and (the lack of) locality of reference I believe.

    It was fun to write, but today it mostly serves as an example of why you don’t generally use linked lists in Python.

Leave a Reply

Your email address will not be published. Required fields are marked *