Stack & Queue

Today’s discussion…

*Stack
* Basic principles
* Operation of stack
* Stack using Array
* Stack using Linked List
* Applications of stack
Basic Idea
• A stack is an Abstract Data Type (ADT), commonly used in most
programming languages. It is named stack as it behaves like a real-world
stack, for example – a deck of cards or a pile of plates, etc.
Stack Representation

• Can be implemented by means of Array, Structure, Pointers and Linked

List.
• Stack can either be a fixed size or dynamic.
push

pop

create
STACK
isempty

isfull
STACK: Last-In-First-Out (LIFO)
• void push (stack *s, int element);
/* Insert an element in the stack */
• int pop (stack *s);
/* Remove and return the top element */
• void create (stack *s);
/* Create a new stack */
• int isempty (stack *s);
/* Check if stack is empty */
• int isfull (stack *s);
/* Check if stack is full */

Assumption: stack contains integer elements!

Stack using Array
Push using Stack

PUSH

top
top
Pop using Stack

POP

top
top
Stack using Linked List
Push using Linked List

PUSH OPERATION

top
Pop using Linked List

POP OPERATION

top
Basic Idea
• In the array implementation, we would:
• Declare an array of fixed size (which determines the maximum
size of the stack).

• Keep a variable which always points to the “top” of the stack.

• Contains the array index of the “top” element.

• In the linked list implementation, we would:

• Maintain the stack as a linked list.
• A pointer variable top points to the start of the list.
• The first element of the linked list is considered as the stack top.
Declaration

#define MAXSIZE 100 struct lifo

{
struct lifo int value;
{ struct lifo *next;
int st[MAXSIZE]; };
int top; typedef struct lifo
}; stack;
typedef struct lifo
stack; stack *top;
stack s;

ARRAY LINKED LIST

Stack Creation

void create (stack *s) void create (stack **top)

{ {
s->top = -1; *top = NULL;
/* s->top points to /* top points to NULL,
last element indicating empty
pushed in; stack */
initially -1 */ }
}

ARRAY LINKED LIST

Pushing an element into stack

void push (stack *s, int element) void push (stack **top, int element)
{ {
stack *new;
if (s->top == (MAXSIZE-1))
{ new = (stack *)malloc (sizeof(stack));
printf (“\n Stack overflow”); if (new == NULL)
exit(-1); {
} printf (“\n Stack is full”);
exit(-1);
else
}
{
s->top++; new->value = element;
s->st[s->top] = element; new->next = *top;
} *top = new;
}
}

ARRAY LINKED LIST

Popping an element from stack
int pop (stack **top)
{
int pop (stack *s) int t;
{ stack *p;
if (s->top == -1) if (*top == NULL)
{ {
printf (“\n Stack underflow”); printf (“\n Stack is empty”);
exit(-1);
exit(-1); }
} else
else {
{ t = (*top)->value;
p = *top;
return (s->st[s->top--]); *top = (*top)->next;
} free (p);
} return t;
}
}

ARRAY LINKED LIST

Checking for stack empty

int isempty (stack *s) int isempty (stack *top)

{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

#include <stdio.h>
#define MAXSIZE 100
struct lifo
{
int st[MAXSIZE];
int top;
};
typedef struct lifo stack;
main() {
stack A, B;
create(&A);
create(&B);
push(&A,10);
push(&A,20);
push(&A,30);
push(&B,100);
push(&B,5);
printf (“%d %d”, pop(&A), pop(&B));
push (&A, pop(&B));
if (isempty(&B))
printf (“\n B is empty”);
return;

Example: A Stack using an Array

}
Example: A Stack using Linked List
#include <stdio.h>
struct lifo
{
int value;
struct lifo *next;
};
typedef struct lifo stack;
main() {
stack *A, *B;
create(&A);
create(&B);
push(&A,10);
push(&A,20);
push(&A,30);
push(&B,100);
push(&B,5);
printf (“%d %d”, pop(&A), pop(&B));
push (&A, pop(&B));
if (isempty(B))
printf (“\n B is empty”);
return;
}
Applications of Stacks
• Direct applications:
• Page-visited history in a Web browser
• Undo sequence in a text editor
• Chain of method calls in the Java Virtual Machine
• Validate XML

• Indirect applications:
• Auxiliary data structure for algorithms
• Component of other data structures
Infix and Postfix Notations
• Infix: operators placed between operands:
A+B*C
• Postfix: operands appear before their operators:-
ABC*+
• There are no precedence rules to learn in postfix notation, and parentheses
are never needed
Infix to Postfix
Infix Postfix
A+B AB+
A+B*C ABC*+
(A + B) * C AB+C*
A+B*C+D ABC*+D+
(A + B) * (C + D) AB+CD+*
A*B+C*D AB*CD*+

A+B* C  (A + (B * C))  (A + (B C *) )  A B C * +

A + B * C + D  ((A + (B * C)) + D )  ((A + (B C*) )+ D) 

((A B C *+) + D)  A B C * + D +
Infix to postfix conversion
• Use a stack for processing operators (push and pop operations).
• Scan the sequence of operators and operands from left to right and
perform one of the following:
• output the operand,
• push an operator of higher precedence,
• pop an operator and output, till the stack top contains operator of a lower
precedence and push the present operator.
The algorithm steps
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto
the stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until
you see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If
the association is left to right, pop and print the top of the stack and then push the
incoming operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop
the stack and print the top operator. Then test the incoming operator against the new top of
stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)
Infix to Postfix Conversion
Requires operator precedence information

Operands:
Add to postfix expression.

Close parenthesis:
pop stack symbols until an open parenthesis appears.

Operators:
Pop all stack symbols until a symbol of lower precedence appears. Then push the
operator.

End of input:
Pop all remaining stack symbols and add to the expression.
Infix to Postfix Rules
Current Operator Postfix string
Expression: symbol Stack
1 A A
A * (B + C * D) + E 2 * * A
3 ( *( A
becomes
4 B *( AB

ABC D * +* E+ 5 + *(+ AB
6 C *(+ ABC
7 * *(+* ABC
8 D *(+* ABCD
Postfix notation 9 ) * ABCD*+
is also called as
10 + + ABCD*+*
Reverse Polish
11 E + ABCD*+*E
Notation (RPN)
12 ABCD*+*E+
Queue
Basic Idea
• Queue is an abstract data structure, somewhat similar to Stacks. Unlike
stacks, a queue is open at both its ends. One end is always used to insert
data (enqueue) and the other is used to remove data (dequeue).
Queue Representation

• As in stacks, a queue can also be implemented using Arrays, Linked-lists,

Pointers and Structures.
enqueue

dequeue

create
QUEUE
isempty

size
QUEUE: First-In-First-Out (FIFO)
void enqueue (queue *q, int element);
/* Insert an element in the queue */
int dequeue (queue *q);
/* Remove an element from the queue */
queue *create();
/* Create a new queue */
int isempty (queue *q);
/* Check if queue is empty */
int size (queue *q);
/* Return the no. of elements in queue */

Assumption: queue contains integer elements!

Queue using Linked List
Basic Idea
• Basic idea:
• Create a linked list to which items would be added to one end and
deleted from the other end.
• Two pointers will be maintained:
• One pointing to the beginning of the list (point from where
elements will be deleted).
• Another pointing to the end of the list (point where new
elements will be inserted).
Rear

Front DELETION INSERTION

Queue: Linked List Structure

ENQUEUE

front rear
Queue: Linked List Structure

DEQUEUE

front rear
Example :Queue using Linked List
struct qnode
{
int val;
struct qnode *next;
};

struct queue
{
struct qnode *qfront, *qrear;
};
typedef struct queue QUEUE;

void enqueue (QUEUE *q,int element)

{
struct qnode *q1;
q1=(struct qnode *)malloc(sizeof(struct qnode));
q1->val= element;
q1->next=q->qfront;
q->qfront=q1;
}
Example :Queue using Linked List
int size (queue *q)
{
queue *q1;
int count=0;
q1=q;
while(q1!=NULL) int dequeue (queue *q)
{ {
q1=q1->next; int val;
count++; queue *q1,*prev;
} q1=q;
return count; while(q1->next!=NULL)
} {
prev=q1;
q1=q1->next;
}
val=q1->val;
int peek (queue *q) prev->next=NULL;
{ free(q1);
queue *q1; return (val);
q1=q; }
while(q1->next!=NULL)
q1=q1->next;
return (q1->val);
}
Problem With Array Implementation
• The size of the queue depends on the number and order of enqueue and
dequeue.
• It may be situation where memory is available but enqueue is not
possible.
ENQUEUE DEQUEUE
Effective queuing storage area of array gets reduced.
0 N

front
front rearrear

Use of circular array indexing

Applications of Queues
The applications are,
1. When jobs are submitted to a printer, they are
arranged in order of arrival. Then jobs sent to a line
printer are placed on a queue.
2. Lines at ticket counters are queues, because service is
first-come first-served.
3. Another example concerns computer networks. There
are many network setups of personal computers in which
the disk is attached to one machine, known as the file
server.
4. Users on other machines are given access to files on a
first-come first-served basis, so the data structure is a
queue.
Applications of Queues
• Direct applications:-
• Waiting lists
• Access to shared resources (e.g., printer)
• Multiprogramming

• Indirect applications:-
• Auxiliary data structure for algorithms
• Component of other data structures
What is a Circular Queue?

A Circular Queue is a special version of queue

where the last element of the queue is
connected to the first element of the queue
forming a circle.

The operations are performed based on FIFO (First

In First Out) principle. It is also called ‘Ring
Buffer’.
#include<stdio.h>
#include<stdlib.h>
struct circularQueue
{
int size;
int f;
int r;
int* arr; };
int isEmpty(struct circularQueue
*q)
{ if(q->r==q->f)
{ return 1;
} return 0;
}
int isFull(struct circularQueue *q)
{
if((q->r+1)%q->size == q->f)
{
return 1; }
return 0; }
void enqueue(struct circularQueue *q, int
val)
{ if(isFull(q))
{ printf("This Queue is full"); }
Else
{ q->r = (q->r +1)%q->size; q->arr[q->r] =
val;
printf("Enqued element: %d\n", val); } }
int dequeue(struct circularQueue *q)
{ int a = -1;
if(isEmpty(q))
{ printf("This Queue is empty");
}
Else
{
q->f = (q->f +1)%q->size; a = q->arr[q->f];
}
return a; }
int main()
{ struct circularQueue q;
q.size = 4;
q.f = q.r = 0;
q.arr = (int*) malloc(q.size*sizeof(int)); //
Enqueue few elements enqueue(&q, 12);
enqueue(&q, 15); enqueue(&q, 1);
printf("Dequeuing element %d\n", dequeue(&q));
printf("Dequeuing element %d\n", dequeue(&q));
printf("Dequeuing element %d\n", dequeue(&q));
enqueue(&q, 45);
enqueue(&q, 45);
enqueue(&q, 45);
if(isEmpty(&q)){ printf("Queue is empty\n"); }
if(isFull(&q)){ printf("Queue is full\n");
}
return 0; }
Operations on Circular Queue:
•Front: Get the front item from queue.
•Rear: Get the last item from queue.
•enQueue(value) This function is used to insert an
element into the circular queue. In a circular queue,
the new element is always inserted at Rear position.
• Check whether queue is Full – Check ((rear ==
SIZE-1 && front == 0) || (rear == front-1)).
• If it is full then display Queue is full.
• If queue is not full then, check if (rear == SIZE
– 1 && front != 0) if it is true then set rear=0
and insert element.
•deQueue()
•This function is used to delete an element from the
circular queue. In a circular queue, the element is
always deleted from front position.
• Check whether queue is Empty means check
(front==-1).
• If it is empty then display Queue is empty. If
queue is not empty then step 3
• Check if (front==rear) if it is true then set
front=rear= -1 else check if (front==size-1), if
it is true then set front=0 and return the
element.
Applications:
1.Memory Management: The unused memory locations
in the case of ordinary queues can be utilized in circular
queues.
2.Traffic system: In computer controlled traffic system,
circular queues are used to switch on the traffic lights one
by one repeatedly as per the time set.
3.CPU Scheduling: Operating systems often maintain a
queue of processes that are ready to execute or that are
waiting for a particular event to occur.
Double ended queue
Priority Queue

• It is an abstract data type that is similar to a queue,

and every element has some priority value associated
with it.
• The priority of the elements in a priority queue
determines the order in which elements are served
(i.e., the order in which they are removed).
• If in any case the elements have same priority, they are
served as per their ordering in the queue.
Properties of Priority Queue

a priority Queue is an extension of the

queue with the following properties.

•Every item has a priority associated with it.

•An element with high priority is dequeued
before an element with low priority.
•If two elements have the same priority, they
are served according to their order in the
queue.
How is Priority assigned to the elements in a Priority Queue?

In a priority queue, generally, the value of an element is

considered for assigning the priority.
For example, the element with the highest value is assigned the
highest priority and the element with the lowest value is
assigned the lowest priority. The reverse case can also be used
i.e., the element with the lowest value can be assigned the
highest priority. Also, the priority can be assigned according to
our needs.
1) Insertion in a Priority Queue
When a new element is inserted in a priority queue, it moves to the
empty slot from top to bottom and left to right. However, if the
element is not in the correct place then it will be compared with the
parent node. If the element is not in the correct order, the elements
are swapped. The swapping process continues until all the elements
are placed in the correct position.
2) Deletion in a Priority Queue
As you know that in a max heap, the maximum element is the root
node. And it will remove the element which has maximum priority
first. Thus, you remove the root node from the queue. This removal
creates an empty slot, which will be further filled with new insertion.
Then, it compares the newly inserted element with all the elements
inside the queue to maintain the heap invariant.
3) Peek in a Priority Queue
This operation helps to return the maximum element from Max Heap
or the minimum element from Min Heap without deleting the node
from the priority queue.
Difference between Priority Queue and
Normal Queue?
There is no priority attached to elements in a
queue, the rule of first-in-first-out(FIFO) is
implemented whereas, in a priority queue,
the elements have a priority. The elements
with higher priority are served first.
How to Implement Priority Queue?
Priority queue can be implemented using the following data
structures:
•Arrays
•Linked list
•Heap data structure
•Binary search tree
Let’s discuss all these in detail.
1) Implement Priority Queue Using Array:
A simple implementation is to use an array of the following
structure.
struct item {
int item;
int priority;
}
•enqueue(): This function is used to insert
new data into the queue.
•dequeue(): This function removes the
element with the highest priority from the
queue.
•peek()/top(): This function is used to get the
highest priority element in the queue without
removing it from the queue.
Circular Queue implementation in C #include
<stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// Check if the queue is full
int isFull()
{ if ((front == rear + 1) || (front == 0 && rear ==
SIZE - 1))
return 1;
return 0; }
// Check if the queue is empty
int isEmpty()
{ if (front == -1)
return 1;
return 0; }
// Adding an element
void enQueue(int element)
{ if (isFull())
printf("\n Queue is full!! \n");
else { if (front == -1)
front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element); } }
// Removing an element
int deQueue()
{ int element;
if (isEmpty())
{
printf("\n Queue is empty !! \n");
return (-1);
} else
{ element = items[front];
if (front == rear) { front = -1; rear = -1; }
// Q has only one element, so we reset the // queue
after dequeing it. ?
else
{ front = (front + 1) % SIZE; }
printf("\n Deleted element -> %d \n", element);
return (element); } }
// Display the queue
void display()
{
int i;
if (isEmpty())
printf(" \n Empty Queue\n");
else
{
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE)
{ printf("%d ", items[i]);
} printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear); } }
int main()
{ // Fails because front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Fails to enqueue because front == 0 && rear ==
SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Fails to enqueue because front == rear + 1
enQueue(8);
return 0; }