Data Structures

Before going to learn DS, that is mandatory to answer the following questions: What are data structures and algorithms? What good will it do me to know about them? Why can't I just use arrays and for loops to handle my data?

In this section I am going to discuss about some frequently used data structures with their practical usage. For understanding and multi-language usage purpose, I thought to give a specified data structure in some different ways. Most of the cases I will discussed in following order.

·         What is and why?

•       In here I will discuss about the some general practical usages of a particular data structure (DS) in the ‘Beginner’s Eye’.

·         How to represent a data structure without depending a programming language

•       In here I present the data structure in more generic view. Hence you can grab the concept and you can implement this structure without worry about your preference language.

·         How to implement using Java (Only For JAVA Developers)

•       This section is optional .I include this section mainly because my preferred programming language is java. 

      There are several ways to implement a specified DS. I implemented a particular data structure in one or two ways .You can use in your own way without worry about others.

              

·         Practical Activities (IMPORTANT)

• In this section, I give some practical problems associated with that particular DS. You should try to implement that in your preferred programming language. I will only give java solution for that problem because my preferred language is java. If you have a trouble in your preferred language, please drop a comment or drop an email to me. I will help to solve that.\

STACKS and QUEUES

If we want to store 1 to 10 numbers, we can use array to this purpose. If we know the index, which want to access, then we can directly access it.BUT stacks and queues are not same as arrays. We give restricted access to the user. We cannot access data element in the middle of the stack. Only one item can be read or removed at a given time.

IN DEEPLY

Stacks, queues, and priority queues are more abstract entities than arrays. They are defined primarily by their interface. The underlying mechanism used to implement them is typically not visible to their user. For examples:

•  A Stack can be implement using either using an array or Linked List.
•   A Priority Queue can be implement using a array or heap.

STACK

      What is and why?

      A stack is “a pile of objects, typically one that is neatly arranged”.

     

     

   

     You can the real world examples of stacks. We can place or remove a card or plate from top of the stack only. I am not going to give deep details about general view point because you can find those details from the web. But I want to tell you how to construct a stack data structure in pro grammatically.

     

      The Stack Operations

           Push                    : pushing (storing) an element on the stack.

           Pop                      : get the top element from the stack and remove it from stack.

           Top/Peek             : get the top data element of the stack, without removing it.

           isEmpty              : check if stack is empty

           Size                     : return the size of the stack

    

      Stack Data Structure without Specifying a Programming Language

     

     Method 1: Stack interpretation using an array

Stack Class:                 fields{                                 top <- 0    //initially stack has no items. Then top returns 0                                 array s    //we use an array to stack implementation                                 capacity <- n   //since we use array implementation, we have to tell the array size in the initial stage                          }                 methods{                              push();                              pop();                              peek();                              isEmpty();                              size();                         }

Now we need to know how to implement those methods. Let’s go”STEP by STEP” processes for that task.

Our initial array looks like:

“isEmpty” Method

In the initial stage we assign our variable ‘top’ to value ‘0’.When checking value of the ‘top’,we can make conclusion as the stack is empty or not.

isEmpty(){         IF( top=0 )               Return TRUE;         ELSE               Return FALSE; }

“size()” Method

The stack size is different from the “Capacity” variable. Capacity variable tells the size of the array which does not tell the size of the stack. It uses for array implementation because when we define a array, we need to tell exactly, what the array size before insert data items into it.

“Top” variable keeps the current pointer of the array. When we push(add) the first element to the array ‘S’, then  the ‘top’ becomes its value as 1.Which means stack has only one element.

Similarly, when we push 2^nd element, then the value of ‘top’, becomes 2.

Therefore, if we return the value of the variable ‘top’, then that will be the exact value of the stack current size.

Size(){      Return top; }

“push(x)” Method

Now we are going to insert a new data item to our stack  where ‘x’ is the data item and ‘S’ is the name of the stack.

Now you know, variable ’top’ point to the current last inserted element in the stack.Therefore you can easily point the next place to insert the data item by:

Push(x){      top <- top+1      S[top] <- x }

Is that complete our work? What happens, if the stack is already filled?. Because this is array implementation. Therefore you may think, need one additional method called,”isFull()”.YES, you are correct. But we can do that requirement without bothering about additional methods. See the following implementation:

Push(x){       IF (capacity>size()){              top <-top+1              S[top] <- x        }ELSE               Error “Stack Overflow”;      }

“pop()” Method

When you call the pop(),then it will returns the top most element of the stack and delete that element from the stack. But actually we do not going to delete the top most element from the stack. In order to show that, we use some tricky way. We change the variable ‘top’, location to :

top <- top-1

This means, if user request for top element later, then it seems to delete the old top. But if you prefer, you can set it to “NULL”.

Pop(){         IF(isEmpty()){              Error “Stack Underflow”         }ELSE{               temp <- S[top]               S[top] <- NULL               top <- top-1               Return temp;         }     }

“peek()” Method

Hope you can do this by yourself.

If you having problem, please put a comment or drop a email.