0% found this document useful (0 votes)
35 views12 pagesStack and Queue
The document outlines the implementation of stack and queue data structures using arrays and linked lists. It explains the operations of push and pop for stacks, and enqueue and dequeue for queues, along with pseudocode and C code examples. Additionally, it covers circular queues and their operations, emphasizing the FIFO principle of queues.
Uploaded by
WafaCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
35 views12 pagesStack and Queue
The document outlines the implementation of stack and queue data structures using arrays and linked lists. It explains the operations of push and pop for stacks, and enqueue and dequeue for queues, along with pseudocode and C code examples. Additionally, it covers circular queues and their operations, emphasizing the FIFO principle of queues.
Uploaded by
WafaCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 12
Lab Task 7: Stack
Objectives:
© To be able to implement stack as an array
© Tobe able to implement stack as Linked Lists
© Tobe able to evaluate postfix expressions using a stack
Theory:
A stack is one of the most important and useful linear data structure in computer science. It is an
ordered collection of items into which new data items may be added/inserted and from which items
may be deleted at only one end, called the top of the stack. As all the addition and deletion in a
stack is done from the top of the stack, the last added element will be first removed from the stack
That is why the stack is also called Las t-out (LIFO).
Note that the most frequently accessible element in the stack is the top most elements, whereas the
least accessible element is the bottom of the stack. The operation of the stack can be illustrated as
ig. 13.
30 f+— Top
20|<«— Top [20 oO eee
10 | +—Top [10 20 10
109
Stack is empty Push(10) Push(20) Push(30) Pop(30),
Fig. 13. Stack Operations
The insertion (or addition) operation is referred to as push and the deletion (or remove) operation
as pop. A stack is said to be Empty or underflow, if the stack contains no elements. At this point
the top of the stack is present at the bottom of the stack. And it is overflow when the stack
becomes full, ic., no other elements can be pushed onto the stack. At this point the top pointer is
at the highest location of the stack.
OPERATIONS PERFORMED ON STACK
‘The primitive operations performed on the stack are as follows:
PUSH:
The process of adding (or inserting) a new element to the top of the stack iscalled PUSH
operation, Pushing an element to a stack will add the new element at the top. After every push
operation the top is incremented by one. If the array is full and no new element can be
accommodated, then the stack overflow condition occurs.
31 PoP:
The process of deleting (or removing) an element from the top of stack is called POP operation.
After every pop operation the stack is decremented by one. If there is no element in the stack and
the pop operation is performed then the stack underflow condition occurs.
STACK I MPLEMENTATION
Stack can be implemented in two ways:
1, Static implementation (using arrays)
2. Dynamic implementation (using linked lists)
Pseudocode for PUSH operation in STACK
LIf TOP = SIZE ~ 1, then:
(a) Display “The stack is in overflow condition”
(b) Exit
2.TOP = TOP +1
3. STACK [TOP] = ITEM
4. Exit
Pseudocode for POP operation in STACK
1. If TOP <0, then
(a) Display “The Stack is empty”
(b) Exit
2. Else remove the Top most element
3. DATA = STACK[TOP]
4, TOP =TOP-1
5. Exit
C code for implementing Stack using arrays
#include
int top =-1;
define MAX 10
int ar{MAX];
void push(int element) {
if top = MAX-1)
printf("Stack is full
}
elsef
top;
arr[top] = element;
/Iprintf("%d Added value in the stack: \n", element);
}
}
void pop(){
int element;
ifftop=-1)§
printf("Stack is empty: ");
}
32 else{
element = arr{top];
top-
printf("Popped value: %d", element);
}
}
void display(){
printf("Elements in the stack:");
for(int i-top;i>=0; i-){
printf("%d ", arrfi]);
}
}
int main)
{
push(10);
push(20);,
push(30);,
push(40);,
display():
printf"
Pop();
printf("\n");
pop);
printf("\n");
display;
return 0;
}
C code for implementing Stack using Linked List
#include
#include
struct node
{
int data;
struct node *next;
hy
struct node *head = NULL;
;
void push(int val)
{
struct node *newNode = malloc(sizeof{struct node));
newNode->data = val;
newNode->next = head;
head = newNode;
33 void pop)
{
struct node *temp;
if(head = NULL)
printf("Stack is Empty\n");
else
{
printf("Poped element = %d\n", head->data);
temp = head;
head = head->next;
free(temp);
’ }
void display()
{
struct node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
int main()
{
push(100);
push(200);
push(300);
printi("Elements in the Linked List:
display():
printf("\n");
pop();
printf("Showing the new linked list after the pop:");,
display);
printf("\n");
pop();
printf{"Showing the new linked list after the pop: ");
display);
return 0; Lab Task 8: Queue
Objectives
© Tobe able to implement basic operations on normal queue
© Tobe able to implement basic operations on circular queue
© Tobe able to implement queue as an array
© To be able to implement a queue using Linked Lists
Theory:
A queue is logically a first in first out (FIFO or first come first serve) linear data structure. The
concept of queue can be understood by our real life problems. For example a customer come and
join in a queue to take the train ticket at the end (rear) and the ticket is issued from the front end
oof queue. That is, the customer who arrived first will receive the ticket first, It means the customers
are serviced in the order in which they arrive at the service centre.
Itis a homogeneous collection of elements in which new elements are added at one end called rear,
and the existing elements are deleted from other end called front.
The basic operations that can be performed on queue are:
© Insert (or add) an element to the queue (enqueue)
¢ Delete (or remove) an element from a queue (dequeue)
Enqueue operation will insert (or add) an element to queue, at the rear end, by incrementing the
array index. Dequeue operation will delete (or remove) from the front end by decrementing the
array index and will assign the deleted value to a variable. Total number of elements present in the
queue is front-rear+1, when implemented using arrays. Following figure will illustrate the basic
operations on queue.
35 10
front
Queue is empty
10
WA Enqueue(10)
front
10 | 20
rear Enqueue(20)
front
40 | 20 | 30
front rear Enqueue(30)
20 | 30
rae Dequeue(20)
Pseudocode for enqueuing an element into the queue
1. Initialize front=-1 rear
2. Input the value to be inserted and assign to variable “data”
Fig. 9. Basic Operations on Queue
1
3. If (rear = SIZE-1)
(a) Display “Queue overflow”
(b) Exit
4. Else
(a) rear
5. Qfrear]
6. Exit
Pseudocode for dequeuing an element from queue
rear +1
data
1. If (rear== front)
(a) Display “The queue is empty”
(b) Exit
2. Else
(@) Data = QU
front]
36
front--1
front=0
rear=1
front-0
reat -2
front=1
rear=2 3. front = front + 1
4. Exit
C code for implementing Queue using arrays
include
i#define SIZE 5
int front =-1;
int rear = -1;
int queue[SIZ:
void enqueue(int n){
ifltear — SIZE - 1)f
printf("Sorry, the queue is full at the moment!");
}
else{
reart+;
queue[rear] = n;
}
}
void dequeue(){
int value;
if(front == rear) {
printf("The queue is empty at now!");
value=queue[ front];
printf("Dequeued value is: %din", value);
}
}
void printQueue(){
printf{"Elements in the queue: ");
for(int i=front+1;i<=rear;i++){
printf("%d ", queuefi);
}
}
int main()
{
int ch;
printf("1: Enqueueing an element to queue\n");
printf("2: Dequeueing an element from queue\n");
print{("3: Display all the elements of queue\n");
printf("4: Exitin");
do{
37 printf("Enter your choice : ");
scanf("%d", &ch);
switch (ch) {
case 1: {
printf("Enter element to be enqueued:");
int item;
seanf("%d", &item);
enqueue(item);
break;
}
case 2: dequeue();
break;
case 3: printQueue();
break;
case 4: printf("Exit");
break;
default: printf("Invalid choice");
}
} while(ch!=4);
retum 0;
}
‘There are three major variations in a simple queue. They are:
1. Circular queue
2. Double ended queue (de-queue)
3. Priority queue
Circular Queue
In circular queues, the elements Q[0],Q[1],Q[2] ... Q[n ~ 1] is represented in a circular fashion
with Q[1] following Q[n]. A circular queue is one in which the insertion of a new element is done
at the very first location of the queue if the last location at the queue is full. Suppose Q is a queue
array of 6 elements. Push and pop operation can be performed on circular. The following figures
will illustrate the same.
38 me
Fig. 12, A circular queue after enqueueing 30, 47, 14
Front
Fig. 10. A circular queue after enqueuing 18, 7, 42, 67.
Fig. 11. A circular queue after dequeuing 18, 7.
Fig. 12. A circular queue after enqueueing 30, 47, 14.
‘At any time the position of the element to be enqueued will be calculated by the relation Rear =
(Rear + 1) % SIZE. After dequeuing an element from circular queue the position of the front end
is calculated by the relation Front= (Front + 1) % SIZE. After locating the position of the new
clement to be inserted,
rear, compare it with front. If (rear = front), the queue is full and cannot be inserted anymore,
39 Pseudocode for enqueuing an clement to the circular queue
1. Initialize FRONT =- 1; REAR =-1
2. If (REAR + 1) % SIZE—=FRONT)
(a) Display “Queue is full”
(b) Exit
3. Else
(a) Input the value to be inserted and assign to variable “DATA”
4. If (FRONT is equal to ~ 1)
(a) FRONT=0
5, REAR = (REAR + 1) % SIZE
6. Q[REAR] = DATA
7, Repeat steps 2 to 4 if we want to insert more elements
8. Exit
Deleting an element from a circular queue
1. If FRONT ==~ 1)
(a) Display “Queue is empty”
(@) DATA = Q[FRONT]
3. If (REAR is equal to FRONT)
(a) FRONT =-1
(b) REAR
4. Else
(a) FRONT = (FRONT +1) % SIZE
5, Repeat the steps 1, 2 and 3 if we want to delete more elements
6. Exit
C code for implementing a Circular queue
Hinclude
define SIZE 5
int front
int rear = -1
int queue[SIZE];
void enqueue(int number) {
if{(vear+1)%SIZE—front){
printf("Queue is fullin");
}
else{
if{front—-1) {
front=0;
}
rear(rear+1)%SIZE;
queue[rear]-number;
}
40 void dequeue(){
int element;
if{front=-1){
printf("Queue is empty's
}
else {
element = queue[front];
if (front = rear) {
front = -1
rear=
}
else
front=(front+1)%SIZE;
3
printi("\n Deleted element -> %d \n’, element);
}
}
void printQueue(){
inti;
if{front<=rear){
for(imfrontsi
printi("%d
}
}
else{
infront;
while(i
