|
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 2nd 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.
