Tuesday, January 19, 2010

Implementing a Stack: Data Structures in Programming

I remember implementing a stack during one of programming assignments during my undergrad years. I have known that many of us have a phobia of implementing datastructures (especially using C). I believe that if we were taught implementing datastructures using simpler languages such as Python and Java (i.e. without use of pointers), we would been better off by now. Though i do not blame C language, it all requires some time to be spent with the language to understand it and implement the logic.

In this post, i am writing how to implement a stack using a simple language like Python.

Stack is a simple data structure which takes data elements at one end and pops the data elements at the same end.

Refer this wikipedia article for more clear explanation.

Steps in implementing a Stack:
  1. Initialize the Stack.
  2. Insert the elements.
  3. Pop the element.
  4. Follow steps 2 and 3 interchangeably as per the requirement (making sure that we are not inserting/popping the stack beyond its capacity.

If you can see, append method adds the element to the end of the list (similar to a Stack). Pop method returns the element at the end of the list and removes the same element from the list.

  • In python, the size of list is not fixed. So, there would be no overflow of data from the stack (as we are implementing the stack using the list).
  • But, the size of the list can be minimum at zero(not less than it, doesnt make sense if less than zero) and is quite obvious.
  • You do not have to take care of writing the logic to insert or delete the elements in the list, python takes care of it.
Now, lets try implementing the same in Java without making use of builting libraries or API. This helps us in understanding the same at the basic level.

Here, the difference in implementation is that the size of the array is fixed. We are using Array to implement the Stack (in simplest form). Though we can use the Stack class @ java.lang.Stack package.

  • While popping, we are just modifying the Top Of Stack element and reducing the index.
  • Also while popping, we are checking if the Stack is empty or not, if the stack is empty, we just display an message that we cannot pop further.
  • While inserting, we are making sure that index is within the range of maximum number of elements in the stack. This ensures, that we do not raise an Index Out of Bounds error.
  • We seperated the tasks into methods implemented in Stackx class.

Most of the code is self explanatory:


Contents of Array after pushing:1 at:1:

Contents of Array after pushing:2 at:2

Contents of Array after pushing:3 at:3

Contents of Array after popping: 3

Contents of Array after popping: 2

Contents of Array after popping: 1

you cannot pop

Array is empty

Contents of Array after pushing:1 at:1:

Contents of Array after pushing:2 at:2

Contents of Array after popping: 2


The output is self explanatory too!!

No comments:

Post a Comment