Wednesday, January 20, 2010

Implementing a Queue: Data Structures in Programming

Implementing a Stack is a simpler task compared to a Queue. In this post, i will explain how to implement a Queue. One can imagine a queue as a Water Pipe where water (elements, integers/objects in terms of computer programmer like us) enters from one end and leaves the other end. It follows the concept of "First In First Out"........

Implementing a queue through a program in python is quite easy, and is quite similar (only in python) and is described as follows:

Now, we see that it is so simple to implement in python. Now we will do the same in JAVA. There is a way through which we can implement the same as above in JAVA too (by importing java.util.Queue)!!

But what fun is it, when we let JAVA take care of everything (like overflow/empty.... kind of situations).

I will implement a small Queue of Integers and insert integers.

The size of the queue is read dynamically at the console (command prompt or the Bash shell or whatever).

The above code can be implemented in a more precise, professional manner using the Queue class.

Why re-invent the wheel when the stuff is pre-coded in the API?

Its because, we need to know what is going on behind the scenes, what the logic is all about. Thinking from scratch helps us understand and see stuff. This helps us professionally.

Rahul Kavi.

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!!