Stack: - LIFO-Last In Last Out
A stack is a data structure in
which additional of new element or deletion of existing elements always takes
places at the same end. This end often known as top of the stack.
When an item is added to the
stack the operation is called Push and when item is removed from the
stack, the operation is called Pop. There are several application where
stack can be used. E.g. recursion, keeping track of fuction calls, evalution of
expression etc.
Since the last item added to the
stack is the first one to get removed. A stack is often called a Last In First
Out (LIFO)structure. When we push the element into the stack, increment the
stack pointer and push the element.
When we pop the element from the
stack, pop the element and decrement the stack pointer.
#include<iostream.h>
#define
MAX 10
#include<conio.h>
class
stack
{
int
top; // data member
int
arr[MAX]; // data member
public:
stack(
) // constructor declaration
{
top=-1;
}
void
push (int item)
{
if
(top==MAX-1)
{
cout<<
“\n Stack is full”;
return;
}
top++;
\\ increment of the stack pointer 2nd push the data
arr[top]=item;
}
int
pop() // member function
{
int
data; // local variable
if(top==-1)
{
cout<<
“ \n stack is empty”;
return
0;
}
data=arr[top];
// pop the element and decrement the stack pointer
top--;
return(data);
}
};
void
main( )
{
stack
s; // object
int
x, m,n,i;
cout<<
“ \n How many element do you want to push?:”;
cin>>m;
for(i=0;i<m;i++)
{
cout<<
“\n Enter the element”<<i+1;
cin>>x;
s.puch(x);
//calling the function
}
cout<<
“ How many elements do you want to pop?:”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<
“\n poped element=” <<s.pop( );
}
getch(
);
}
We
have defined a class called ‘stack’ containing member function ‘push( ); and ‘pop(
);. These function represent add and delete items from the top of the stack. The
actual storage is done in an array ‘arr’ and the data member ‘top’ is an index
into this array. It contains the value, where the addition or deletion is going
to take place in the array and thereby in the stack. To indicated that, to
begin with the stack. To indicate that to begin with the stack is set with the
value ‘-1’.
Queue( FIFO-First In First Out)
In a queue, the addition of new
element takes place at the end (called rear of the queue), whereas deletion
takes place at the other end (called front of the queue).
We can use an array to hold the
item in the queue.
For efficiency processing of
queue, we shall therefore need two indices so that we keep track of both the ‘front’
and ‘rear’ of the queue. We simply increase the ‘rear’ by ‘1’ and put the item
to that position. To remove an item, we take it from the position at the ‘front’
and then increase the front by ‘1’.
#include<iostream.h>
#define
MAX 10
#include<conio.h>
class
queue
{
int
arr[MAX]; // data member
int
front, rear; // data member
public:
queue // constructor declaration
{
front=-1;
rear=-1;
}
void
addq (int item)
{
if
(rear==MAX-1)
{
cout<<
“\n Queue is full”;
return;
}
rear++;
arr[rear]=item;
if(front==-1)
front=0;
}
int
delq() // member function
{
int
data; // local variable
if(front==-1)
{
cout<<
“ \n Queue is empty”;
return
0;
}
data=arr[front];
if(front=rear)
front=rear=-1;
else
front++;
return(data);
}
};
void
main( )
{
queue
q; // object
int
x, m,n,i;
cout<<
“ \n How many element do you want to insert?:”;
cin>>m;
for(i=0;i<m;i++)
{
cout<<
“\n Enter the element”<<i+1 “ the element”;
cin>>x;
q.add(x);
//calling the function
}
cout<<
“ How many elements do you want to delete?:”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<
“\n Deleted element=” <<q.delq( );
}
getch(
);
}
Since
addition of new element to the queue takes place at the rear end and deletion
of an element from the queue take place from the front end, in the class. We
have two data member i.e. front and the ‘rear’ to monitor the two ends. When
the queue is empty their values are set to -1. To carry out the addition and
deletion operation on the queue we have implemented two functions within the
queue class namely add( ) and del( ) function.
Limitation of queues
Suppose we go on adding elements
to the queue till the entire array get filled. At this stage the value of rear
would be MAX-1. Now, if we delete 5 elements from the queue, at the end of this
deletion the value of front will be 5. If we now attempt to add a new element
to the queue, then it would be reported as full even though in reality the
first 5 slots of the queue are empty. To overcome this situation we can implement
a queue as a circular queue i.e. during addition if we reach.
#include<iostream.h>
#define
MAX 10
#include<conio.h>
class
queue
{
int
arr[MAX]; // data member
int
front, rear; // data member
public:
queue // constructor declaration
{
front=-1;
rear=-1;
}
void
addq (int item)
{
if
(rear==MAX-1&&front==o)||(rear*1==front))
{
cout<<
“\n Queue is full”;
return;
}
if(rear==MAX-1)
rear=0;
else
rear=rear++;
arr[rear]=item;
if(front==-1)
front=0;
}
int
delq() // member function
{
int
data; // local variable
if(front==-1)
{
cout<<
“ \n Queue is empty”;
return
0;
}
else
{
data=arr[front];
// pop the element and decrement the stack pointer
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
if(front==Max-1);
front=0;
else
front=front+1;
}
return(data);
}
}
};
void
main( )
{
queue
q; // object
int
x, m,n,i;
cout<<
“ \n How many element do you want to insert?:”;
cin>>m;
for(i=0;i<m;i++)
{
cout<<
“\n Enter the element”<<i+1 “ the element”;
cin>>x;
q.add(x);
//calling the function
}
cout<<
“ How many elements do you want to delete?:”;
cin>>n;
for(i=0;i<n;i++)
{
cout<<
“\n Deleted element=” <<q.delq( );
}
getch(
);
}
Linked List:
- Array suffers from the necessity to declare the
size of array before running the program. If we are to overcome this limitation
we need to use a data structure called linked list.
A link list provides a more
flexible storage system in that it doesn’t use array at all. For every item in
the list it associates a pointer that could give the location of the next item
in the list.
Instead of allocation space for
each item during compilation in the linked list space for each item is obtained
as and when needed (during execution) and each item is connected or linked to
the next data item using a pointer.
Unlike the array elements, the
individual item of the link list doesn’t need to be located in adjacent memory
location. They may be scattered in anywhere in the memory.
Implementation
of stack using link list (dynamic memory allocation)
#include<iostream.h>
#include<conio.h>
struct node
{
int data;
node *link;
};
class struck
{
node *top;
public:
stack( );
{
top=NULL;
}
void push (int
item)
{
node *temp;
temp=new node;
temp->data=item;
temp->link=top;
top=temp;
}
int pop ( )
{
node *temp;
if(top==NULL)
{
cout<< “ Node
are not present in the list \n”;
return NULL;
}
int item;
temp=top;
item=temp->data;
top=top->link;
delete temp;
return item;
}
};
void main ( 0
{
stack a;
a.push(10);
a.push(11);
a.push(12);
cout<< “deleted
element=” << a.pop();
cout<< “deleted
element=” << a.pop();
cout<< “deleted
element=” << a.pop();
getch( );
}
No comments:
Post a Comment