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.isempty()||len(L) == 0||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()
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