STACKS

Stack is a collection of homogenous data items where insertion and deletion operations take

place at one end in a LIFO fission and that end is termed as top of the stack.

 

stack can be implemented in two ways.

1. Using Arrays.

2. Using Linked list.

Operations on stack:

1. push- operation

2. pop-operation

3. display- operation

4. is empty-operation

5. is full – operation

6. peak- operation

 

1. push-operation:

Push operation is used for inserting elements in to a stack is called push operation.

Algorithm

Step 1: if(top==size-1)

Then write “stack is full”

Else

Step 2: read data (or)item

Step 3: top=top+1

Step 4: stack[top]=item

Step 5: stop.

C - implementation of push operation:

push ()

{

if (top==(maxstk-1))

printf (“stack overflow\n”)

else

printf (“enter the item to be pushed in stack:”);

scanf (“%d”, &item);

top=top+1;(or) s[++top] =item

s[top]=item;

}

}

Stack overflow: When the stack is full then the insertion operation takes place, it is known as

stack overflow.

POP- operation: Pop operation is used for removing an element (or)deleting an element from

the stack is called pop operation.

Algorithm:

Step 1: if (top== -1)

Then write (“stack is empty”)

(“stack underflow”)

else

Step 2: item =start(top)

Step 3: Top =Top -1

Step 4: stop.

C - implementation of pop operation:

pop ()

{

if (top==-1)

printf (“stack underflow in pop\n”);

else

{

printf (“popped element is:%d\n’’s[top]);

top= top -1;

}

}

Display – operation:

• • Display operation is used to display the contents of the stacks. If the stacks contain 5

elements and the top is pointing to top element s (4) the following code is used to display all the

5 elements in the stack.

• • Generally, the contents of the stack are displayed from the top of the stage to the bottom

of the stack is finished.

C – implementation of display operation:

display ()

{

int i;

if (top == -1)

printf (“the stack is empty\n”);

else

{

printf (“the stack contents from top to bottom are \n”);

for (i=top; i>=0; i--)

printf (“the element %d is %d\n”, i+1, s[i]);

}

}

 

is empty operation:

• • This operation is used to find whether the stack contains any elements (or) not.

If stack is empty then it returns true else if stack is not empty it returns false.

• • This function is mainly used to test underflow operation.

C – implementation of is empty operation:

int is empty ()

{

if (top == -1)

return (true);

else

return (false);

}

 

is – full operation: In the elements in the stack is full it returns true else stack is false.

C - implementation of is -full operation:

int is full ()

{

if (top == size -1)

return (true);

else

return (false);

}

Peak operation: It is used to get the top element of the stack.

C – implementation of peak operation:

int peak ()

{

if (top == -1)

printf (“stack underflow”);

else

return (stack [top])

}

 

Application of stack:

1. recursion.

2. reversal of a string.

3. checking the parantasis matching.

4. Infix notation. (conversion)

5. postfix notation. (conversion)

6. pre – fix notation. (conversion)

Polish notation of Arthematic expression:

Expressions involved operators on operands.

There are three notations of Arthematic expressions using stack they are

Infix – notation.

2. Postfix – notation.

3. Prefix – notation.

 

Infix notation:

The conventional way of writing an expression is called Infix i.e. if the operator is placed

between its two operands then we called the notation as Infix notation.

Syntax:

<operand> operator <operand >

a+b

(a=operand, b=operand,” +” = operator)

Prefix notation:

If the operator symbol is placed before its two operands then we call that notation as pre-fix

notation.

Syntax:

<operator><operand><operand>

++a

*-ab/cd

Postfix notation: If the operator symbol is placed after its two operands then we call that

notation as postfix notation.

Syntax:

<operand><operand><operator>

b++

abc*

Conversion of infix to postfix using stack:

Rule 1: priorities of operators.

Rule 2: No two operators of same priority can stay together in stack column.

Rule 3: Lowest priority cannot be placed before the highest priority

Rule 4: Any operator placed between open & closed parantasis then just immediately pop that

operator.

Algorithm for transforming infix expression in to postfix expression:

Step 1: PUSH the left parenthesis (“on to STACK and add right paraptosis”) at the end of Q.

Step 2: Scan Q from left to right and repeat step 3 to 6 for each element of Q until the stack is

empty.

Step 3: if an operand is encountered, add it to p.

Step 4: if” (“is encountered, push it onto STACK and this “(“can be removed popped only

when”)” is encountered.

Step 5: if an operator is encountered.

a. Repeatedly pop from stack and add to p each operator which has the same precedence.

b. push to stack if”)” is encountered.

6: If “)” is encountered.

a. Repeatedly pop from the stack, add top each operator until the left parenthesis is encountered.

b. Remove the left paraptosis “(“

[Do not add left parenthesis to p]

Step 7: EXIT

 

Example: -

(A+B/C*(D+E)-F) using stack.

Operand postfix.

Operator  stack.

           

                   

Evaluation of postfix expression:

 

1. while reading expression from left to right PUSH the element in the stack. If it is an operand.

2. if the operator is encountered pop two elements Atop element Bnext to top element and

evaluates B operator A and push the result on to the stack.

3. After the expression is finished then return element of stack top.

Algorithm:

Step 1: Add) to postfix expression.

Step 2: Read postfix expression left to right until) encountered

Step 3: if operand is encountered, push in onto stack [END IF]

Step 4: if operator is encountered, pop two elements.

A→ Top element

B→ Next to Top element

Push B operator A on to stack.

Step 5: set result =pop

Step 6: END

Example:

QUEUES

Queues:

Queue is defined as an ordered collection of items from which the item will be deleted at one end

called FRONT END, and in which items may be inserted at another end is called REAR END.

Array representation of queues:

Array representation of queues

Example: int Q [4];

 

Q(0) Q(1) Q(2) Q(3)

• We have 4 elements 10,20,30,40 now first we insert element in Q (0)

Q (0) Q (1) Q (2) Q (3)

10

• Second element is 20, we insert 20 in Q (1) =20

Q (0) Q (1) Q (2) Q (3)

10

20

• Third element is 30, we insert 30 in Q (2) =30

Q (0) Q (1) Q (2) Q (3)

10

20

30

And the last element is 40, we insert last element in Q (3) =40

Q (0) Q (1) Q (2) Q (3)

10

20

30

40

• The queue is full, that queue is displayed

Q (0) Q (1) Q (2) Q (3)

10

20

30

40

Operations on queues:

Based on the actions performed in queues there are 5 operations.

1. queue insert(or)enqueue

2. Qdelete(or)dequeue

3. Qempty

4. Qfull

5. Display

1. Qinsert Or enqueue: -Inserting the element into queue through the rear end is called as

Qinsert or Enqueue

Ex: -int Q [3];

Q (0) Q (1) Q (3)

20

Rear = 0

Front = 0 Enqueue 20 at Q [0]

Q (0) Q (1) Q (2)

20

30

Rear =1

Front =0 Enqueue 30 at Q [1]

Q (0) Q (1) Q (2)

20

30

40

 

20 30 40

Rear =2

Front =0 Enqueue 40 at Q [2]

Algorithm for Enqueue operation: -

Step1: [Overflow check]

if REAR=N-1

then write(“OVERFLOW”)

return

Step2: [Increment rear pointer]

REAR=REAR+1

Step3: [Insert the item]

Q[REAR]=ITEM

Step4: Return

C Implementation of Insertion OR Enqueue

void Qinsert ()

{

if (REAR==N-1)

printf (“\nQueue overflow”);

else

{

printf (“\nEnter the Item:”);

scanf(“%d”, &ITEM);

REAR++;

Queue [REAR]=ITEM;

}

}

2.QDELETE OR dequeue: It is defined as the process of deleting an element in queue through

its front end is called dequeue OR Qdelete

Ex: int Q [4];

Q (0) Q (1) Q (2) Q (3)

10

20

30

40

dequeue (10) = front + 1

Rear=3

Front=0

 

Q (0) Q (1) Q (2) Q (3)

20

30

40

dequeue (20) =front+1 Rear=3

Front=1

Q (0) Q (1) Q (2) Q (3)

30

40

Rear=3

Front=2

Algorithm for dequeue operations:

Qdelete (Q, Front, Rear, N, Item)

Step1: [Underflow check]

if REAR=FRONT-1

then write(“underflow”)

return (0)

Step2: [Delete the item]

ITEM=Q[FRONT]

Step3: if FRONT=REAR [When there is only one item]

FRONT=0, REAR=-1

Else

FRONT=FRONT+1

Step4: return

 

C - Implementation of Qdelete is:

void Qdelete ()

{

if (REAR==FRONT-1)

printf (“\nQueue underflow”);

else if (REAR==FRONT)

{

printf (“\n Deleted item is %d”, QUEUE[FRONT]);

FRONT++;

}

}

 

3.Queue Empty: Qempty is defined as when the rear and front are at -1 position then we state

that as Qempty

Ex: int Q [5];

Q (0) Q (1) Q (2) Q (3) Q (4)

Hence, Front= -1

Rear= -1

Algorithm for Queue Empty:

Step1: if (FRONT==REAR==-1)

then “QUEUE IS EMPTY”

Step2: Stop

C Implementation of Queue Empty

int Empty ()

{

if (REAR==FRONT-1)

return 1;

else

return 0;

}

4. Queue Full: Qfull is defined as when REAR and FRONT are at n-1 position then we state that

as Qfull

Ex: int Q [4];

Q (0) Q (1) Q (2) Q (3)

10

20

30

40

In this case REAR=MAX

i.e., REAR=SIZE-1

Algorithm for Queue full operation:

Step1: if (REAR==SIZE-1)

then “QUEUE IS FULL”

Step2: STOP

 

C - Implementation of Qfull:

int Qfull ()

{

if (REAR==N-1)

return 1;

else

return 0;

}

 

5.Queue Display (): It is the operation which displays the items present in the Queue

C Implementation of queue display ()

void Qdisplay ()

{

int I;

if (REAR==FRONT -1)

printf (“\n\t Number of Elements in Queue”);

else

{

printf (“\n QUEUE:”);

for (i=FRONT; i<= REAR; i++)

printf (“%d\t”, QUEUE[i]);

printf (“\FRONT Element of the Queue id %d”, QUEUE[FRONT]);

printf (“\n REAR element of the Queue is %d”, QUEUE[REAR]);

}

}

Types Of Queues:

Queues are broadly classified into 4 types, they are: -

1.                      Linear/single Circular Priority Double ended

Queue Queue Queue Queue

Ascending Descending Input Output

Priority Priority restricted restricted

Queue Queue dequeue dequeue

1. Linear /Single Queue: It is defined as an ordered linear collection of items from which the

items from the items deleted at one end called frontend and in which item may be Quested at

another end called Rear end.

Example:

Q (0) Q (1) Q (2) Q (3)

10

20

30

40

10=front

40= rear

Circular Queue (Ring Buffer):

A circular queue is similar to a linear queue as it is also based on the FIFO principle except that

the last position is connected to the first position in a circular queue that form a circle.

Circular queue is also known as ring buffer.

Priority Queue:

A priority is a Queue such that each element of the Queue has been assigned with a priority and

such that the order in the element is inserted and deleted using the following rules

1. An element of higher priority is processed before any element of lower priority.

2. If two elements have same priority then the element which comes first will be processed

first.

There are two types of priority Queues.

1. Ascending priority queue: it is a collection of elements in to which items can be inserted in

an order but deletion is possible but deletion is possible only for the smallest element.

2. Descending priority order: it is a collection of elements in to which items can be inserted in

order but deletion is possible but deletion is possible only for the largest element.

 

Double Ended Queue:

A double ended queue is a list in which the element is inserted (or) deleted at either end.

It is a queue data structure in which the insertion and deletion operations are performed at both

ends called front and rear.

There are two types of double ended queue

1. Input restricted dequeue

2. Output restricted dequeue

 

1. Input Restricted dequeue: Input restricted dequeue is the one which allows the insertion only

one end. but allows at both ends deletion.

2. Output Restricted dequeue: Output restricted dequeue is the one which allows deletions at

one end and insertion at both ends and those deletions are possible only at front end.

Some common applications of Queue data structure:

1. Task Scheduling: Queues can be used to schedule tasks based on priority or the order in

which they were received.

2. Resource Allocation: Queues can be used to manage and allocate resources, such as

printers or CPU processing time.

3. Batch Processing: Queues can be used to handle batch processing jobs, such as data

analysis or image rendering.

4. Message Buffering: Queues can be used to buffer messages in communication systems,

such as message queues in messaging systems or buffers in computer networks.

5. Event Handling: Queues can be used to handle events in event-driven systems, such as

GUI applications or simulation systems.

6. Traffic Management: Queues can be used to manage traffic flow in transportation

systems, such as airport control systems or road networks.

7. Operating systems: Operating systems often use queues to manage processes and

resources. For example, a process scheduler might use a queue to manage the order in

which processes are executed.

8. Network protocols: Network protocols like TCP and UDP use queues to manage packets

that are transmitted over the network. Queues can help to ensure that packets are delivered

in the correct order and at the appropriate rate.

9. Printer queues: In printing systems, queues are used to manage the order in which print

jobs are processed. Jobs are added to the queue as they are submitted, and the printer

processes them in the order they were received.

10. Web servers: Web servers use queues to manage incoming requests from clients. Requests

are added to the queue as they are received, and they are processed by the server in the

order they were received.