CODEWITHSUNDEEP
pythonstack
Jack Daniel's
Jack Daniel's

Reputation: 2613

Implementing of Stack using other datastructures like lists

I have seen in many languages basically to implement stacks they take help of other data structure. Ex: If we need to implement stacks in python we cant take advantage of lists. A very simple example 

class Stack(object):


def __init__(self):
    self.stack = []

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

def push(self, element):
    self.stack.append(element)

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

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

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

Point is does it even make sense to do that? if yes then how?

Upvotes: 0

Views: 54

Answers (2)

javidcf
javidcf

Reputation: 59681

As with any other ADT, the main points of implementing a data structure like, for example, a stack are:

  • Provide a simple API with well-known operations.
  • Hide the implementation details of the structure.

A secondary consequence that sometimes you get from this is that the structure is easier to use; sure no one would like to manually manage the elements of an array-based binary heap every time it has to be accessed, but that is not the main point to provide the type. In the case of a stack, it's pretty trivial to implement, so in that sense you don't win anything. What is it that you are getting then?

Provide a simple API with well-known operations

This is, I think, still not the most important aspect, but if you want to use a stack it is clearer to use stack operations (push, pop) than list operations. Specifically, it is good to have a limited interface that does not allow you to call forbidden operations, and/or that provides better errors and corner-case behaviour than a more generic approach.

Hide the implementation details of the structure

This is the key point. The most important thing of all this is that you don't need to (and cannot) know how the data structure is implemented, allowing you to change the implementation later on. Say you now want your stack to be persisted to disk; you would need add file read and write operations each time you push or pop something. Say now you want this storage to be distributed among several computers. Say you want to log every access. Say you want it to reside on GPU for some accelerated computation. All of these possibilities should support basic stack operations, but maybe not all of them support every list operation (or maybe you don't want to implement them all for each of them). As long as you maintain the same original interface, you will only need to make the minimal necessary changes to the implementation and the rest of the code should work exactly the same.

In a language like Python, which is quite high-level, dynamically typed and with a comprehensive standard library, these benefits are not so evident initially, but they still apply all the same.

Upvotes: 0

randyjp
randyjp

Reputation: 1204

In python, unless you really want to practice, it doesn't make any sense to implement your own stack. You can either use a list, even without a wrapper class, or you can use the deque class from collections. Deque is a generic data structure of stacks and queues:

Collections deque

Upvotes: 1

Related Questions