Efficient Stack implementation in Python

Question

1st Implementation: The following stack implementation assumes that the end of the list will hold the top element of the stack. As the stack grows, new items will be added on the end of the list.

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

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

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

2nd Implementation : The second implementation assumes that the beginning of the list holds the top element of the stack and new items are added at the index 0.

 class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.insert(0,item)

     def pop(self):
         return self.items.pop(0)

     def peek(self):
         return self.items[0]

     def size(self):
         return len(self.items)

Being a beginner to Data Structures, I would like to know:
1. Which implementation is more efficient with respect to time or space, and why ?
2. Is the time complexity of the insert(0) in the 2nd implementation O(n). If yes, how ?

See wiki.python.org/moin/TimeComplexity. Note that self.items[-1] gives you the last element with less faff. — jonrsharpe
– jonrsharpe, Commented Jul 5, 2015 at 11:42
yes, rewrite you first peek method. And call it tos, maybe (Top Of Stack) — Pynchia
– Pynchia, Commented Jul 5, 2015 at 11:44

Daniel Roseman · Accepted Answer · 2015-07-05 11:43:27Z

12

Lists are optimized for appending and popping from the end. Inserting or removing an item from the beginning of a list is much more expensive, because all the items need to be moved.

Python does have a data structure, collections.deque, which is optimized for appending at both ends.

answered Jul 5, 2015 at 11:43

Daniel Roseman

602k68 gold badges910 silver badges923 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ben_frankly · Accepted Answer · 2015-07-05 12:05:24Z

3

In Python, lists are implemented with resizeable arrays of references to other objects.

See How are lists implemented?

Because of this, pushing/popping elements at the end of the list will be more efficient than pushing/popping at the start of the list.

Adding/removing elements to the start of an array is very expensive because you will have to shift all the other elements over one space. On the other hand, it is relatively cheap to add/remove elements to the end of an array assuming there is sufficient empty space at the end of the array.

When the array is full, Python will dynamically allocate more memory to the end of that array, which is expensive, but the amortized performance is still excellent.

answered Jul 5, 2015 at 12:05

ben_frankly

10.1k3 gold badges21 silver badges22 bronze badges

Comments

minitechi · Accepted Answer · 2018-02-02 06:31:47Z

0

def __init__(self):
  self.items=[]
def push(self,item):
  self.items.append(item)
def pop(self):
  return self.items.pop()
def isEmpty(self):
  return self.items==[]
def peek(self):
  return self.items[len(self.items)-1]
def size(self):
  return len(self.items)

`

answered Feb 2, 2018 at 6:31

minitechi

1441 silver badge8 bronze badges

Collectives™ on Stack Overflow

Efficient Stack implementation in Python

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related