### Data Structures Part 3

Data Structures Part 3

Stacks:

A stack is a homogeneous collection of items of any one type, arranged linearly with access at one end only called top. This means the data can be added or removed only from top. Formally this type of stack is called as Last in First out (LIFO). Data is added to the stack using push operation, and removed using pop operation. Different implementations are possible; although the concept of a stack is unique.

A stack is a dynamic structure. It changes as elements are added to and removed from it. A stack can be implemented as a constrained version of a linked list. A stack is referenced via a pointer to the top element of the stack. The link member in the last node of the stack is set to NULL to indicate the bottom of the stack.

Stacks and linked lists are represented identically. The difference is that insertions and deletions occur anywhere in a linked list, but only at the top of a stack.
•    Function push creates a new node and places it on top of the stack.
•    Function pop removes a node from the top of the stack, frees the memory that was allocated to the popped node, and returns the popped value.

Stack Operations:

Implementation of a simple stack of integers
struct stackNode
{
int data;
struct stackNode *nextPtr;
};
/* Insert a node at the top of the stack */
void push(struct stackNode **topPtr, int info)
{
struct stackNode *newPtr;
newPtr = (struct stackNode *)
malloc(sizeof (struct stackNode));
if (newPtr != NULL)
{
newPtr ->data = info;
newPtr->nextPtr = *topPtr;
*topPtr = newPtr;
}
else
printf (“%d not inserted. No memory”
“available.\n”, info);
}
/*Remove a node from the stack top */
int pop (struct stackNode **topPtr)
{
struct stackNode *tempPtr;
int popValue;
tempPtr = *topPtr;
popValue = (*topPtr) ->data;
*topPtr = (*topPtr) ->nextPtr;
free (tempPtr);
return popValue;
}
/*Is the stack empty? */
int isEmpty(struct stackNode *topPtr)
{
}

Evaluation of arithmetic expressions:
•    Notation can be infix, postfix or prefix.
Infix: operator is between operands
A + B
Postfix: operator follows operands
AB+
Prefix: operator precedes operands
+AB

•    Operators in a postfix expression are in correct evaluation order.

Postfix Expressions
Infix        Postfix
a + b * c    abc*+
(precedence of * is higher than of +)
a + b * c / d    abc*d/+
(precedence of * and / are same and they are left associative)
•    Parentheses override the precedence rules:
(a + b) * c
ab+c*
•    More examples

Infix    Postfix
(a + b) * (c – d)    ab+cd-*
a – b / (c + d * e)    abcde*+/-
((a + b) * c – (d – e))/ (f + g)    ab+c*de - - fg+/
Order of precedence for 5 binary operators:
power (^)
multiplication (*) and division (/)

The association is assumed to be left to right except in the case of power where the association is assumed from right to left.
I.e. a + b + c = (a+b) +c = ab+c+
a^b^c = a^ (b^c) = abc^^
Conversion of Infix expression to postfix notation

Suppose Q is an arithmetic expression in Infix notation. This algorithm finds the equivalent postfix expression P. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until Stack is empty.
•    If an operand is encountered, add it to P.
•    If a left parenthesis is encountered, push it onto the Stack.
•    If an operator is encountered, then repeatedly pop from Stack and add P each operator (on the top of Stack) which has the same precedence as or higher precedence than current symbol. i. Add the current symbol on to the stack.
•    If a right parenthesis is encountered, then i. repeatedly pop from Stack and add to P each operator (on the top of Stack. until a left parenthesis is encountered).
ii.     Remove the left parenthesis.
•    Exit

Evaluating postfix expression:

This algorithm evaluates postfix expression P using Stack.
•    Scan P from left to right and repeat step 3 and 4 for each element of P until the end of the string is encountered.
•    If an operand is encountered, put it on Stack.
•    If an operator (*) is encountered, then
i.    Remove the two top elements of Stack, where A is the top element and B is the next to the top element.
ii.    Evaluate B (*) A.
iii.    Place the result of (ii) back to Stack.
•    Set VALUE equal to the top element on Stack.
•    Exit C Programming & Data Struct.

Implementation of a stack as an array:

#define maxstack 100
struct stack {
int items[maxstack];
int top;
};
int isEmpty(struct stack s){
return (s.top < 0);
}
int isFull(struct stack s){
return (s.top >= maxstack-1);
}
void push (struct stack *s, int x){
if (s->top >= maxstack-1)
printf (“The stack is full.\n”);
else {
s->top = s->top +1;
s->items[s->top] = x;
}
}
int pop (struct stack *s){
int x;
if (s->top < 0)
printf (“Stack is empty.\n”);
else {
x = s->items[s->top];
s->top = s->top –1;
return x;    }
}
int main()
{
struct stack S;
int c, i;
S.top = -1;
while ((c=getchar() )!='\n')
push (&S, c);
while (!isEmpty(S))
printf ("%c", pop(&S));
printf ("\n");
}

Queues:

A queue is a list with the restriction that insertions only occur at the back, and deletions only occur at the front. A queue is FIFO data structure. The fundamental operations, in addition to size, clear, and empty, are enqueue (insert at back) and dequeue (delete and return the element at the front). This type of frequently used list is known as queue. We have two pointers to access the queue. They are
•    Front (used for deletion)
•    Rear (Used for insertion)

Insertion:

if rear>n queue overflow
else
increment the rear pointer and insert the value in the rear position.
Deletion:
if front =0 then queue underflow
else
increment the front pointer and return the front-1 value.

Some of the practical applications of a queue are:

•    An operating system always makes use of a queue (ready queue, waiting queue) for scheduling processes or jobs.
•    All the input output calls made by the disk to and from the memory are handled by a queue.
•    We have many processors like 80386 and queue plays an active part in there architecture.
•    Queues can be commercially used in online business applications for processing customer requests in first in first serve manner.
•    When a resource like CPU is shared between among multiple consumers, a queue solves the hatchet.
•    In all the basic algorithms for searching or sorting, every one of them makes use of queue.
•    Queues are very efficient when we want to take out elements in the same order we have put in inside.

Implementation of a queue as an array:
#include<stdio.h>
#include<conio.h>
#define SIZE 5
int i, rear, front, item, s[SIZE];
void insert(int item, int s[]);
void del(int s[]);
void display(int s[]);
void main()
{
int ch;
clrscr ();
front=0;
rear=-1;
do
{
printf ("\n\n 1.INSERTION \n 2.DELETION \n 3.EXIT \n");
printf ("\n ENTER YOUR CHOICE : ");
scanf ("%d", &ch);
switch (ch)
{
case 1:
printf ("\n\t INSERTION \n");
if (rear>=SIZE-1)
{
printf ("\t\n QUEUE IS FULL\n");
}
else
{
printf ("\nENTER AN ELEMENT : ");
scanf ("%d", &item);
insert (item, s);
}
display(s);
break;
case 2:
printf ("\n\t DELETION \n");
if (front>rear)
{
printf ("\t\n QUEUE IS EMPTY\n");
}
else
{
del(s);
}
display(s);
break;
}
}
while (ch!=3);
getch ();
}
void insert(int item, int s[])
{
if (rear<SIZE)
{
rear=rear+1;
s [rear]=item;
}
}
void del(int s[])
{
int i;
item=s [front];
for (i=0;i<=rear; i++)
s [i]=s[i+1];
rear--;
printf ("\n DELETED ELEMENT IS %d\n\n", item);
}
void display(int s[])
{
printf ("\n");
for (i=front; i<=rear; i++)
{
printf (" \t %d", s[i]);
}
}

Inserting a node in required position:

Inserting a node at the Rear end:
•    Allocate memory for the new node.
•    Assign the value to the data field of the new node.
•    Set the link field of the new node to NULL.
•    If the queue is empty, then set FRONT and REAR pointer points to the new node and exit.
•    Set the link field of the node pointed by REAR to new node. A
•    Adjust the REAR pointer points to the new node.

Deleting a node from required position:

Deleting a node at the Front end:
•    If queue is empty, then display message “Queue is empty – no deletion is possible” and exit.
•    Otherwise, move the FRONT pointer points to the second node.
•    Free the first node.