Unit - 2
Abstract Data Types (ADTs) Arrays
Q1) What is a Single dimensional array?
A1) A one-dimensional array, often known as a single-dimensional array, is one in which a single subscript specification is required to identify a specific array element. We can declare a one-dimensional array as follows:
Data_type array_name [Expression];
Where,
Data_type - The kind of element to be stored in the array is data type.
Array_name - array name specifies the array's name; it can be any type of name, much like other simple variables.
Expression - The number of values to be placed in the array is supplied; arrays are sometimes known as subscripted values; the subscript value must be an integer value, therefore the array's subscript begins at 0.
Example:
Int "a" [10]
Where int: data type
a: array name
10: expression
Output
Data values are dummy values, you can understand after seeing the output, indexing starts from “0”.
Q2) Write about Multidimensional Arrays?
A2) a 2D array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns.
However, 2D arrays are created to implement a relational database look alike data structure. It provides ease of holding bulk data at once which can be passed to any number of functions wherever required.
How to declare 2D Array
The syntax of declaring a two dimensional array is very much similar to that of a one dimensional array, given as follows.
Int arr[max_rows][max_columns];
However, It produces the data structure which looks like the following.
Fig 1: Example
Above image shows the two dimensional array, the elements are organized in the form of rows and columns. First element of the first row is represented by a[0][0] where the number shown in the first index is the number of that row while the number shown in the second index is the number of the column.
Q3) Write short notes on row major and column major ordering?
A3) Row Major ordering
In row major ordering, all the rows of the 2D array are stored into the memory contiguously. Considering the array shown in the above image, its memory allocation according to row major order is shown as follows.
First, the 1st row of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last row.
Fig 2: Row major ordering
Column Major ordering
According to the column major ordering, all the columns of the 2D array are stored into the memory contiguously. The memory allocation of the array which is shown in in the above image is given as follows.
First, the 1st column of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last column of the array.
Fig 3: Column major ordering
Q4) What are the applications of arrays?
A4) Applications of array
● Vectors and lists, which are fundamental parts of the C++ STL, are implemented using arrays.
● Stacks and queues are also implemented using arrays.
● Whenever possible, trees employ array implementation since arrays are easier to manage than pointers. Tress is then utilized to construct a variety of additional data structures.
● Arrays are used to implement matrices, which are an important aspect of every computer language's mathematics library.
● The graph's adjacency list is implemented using vectors, which are then implemented using arrays.
● Binary search trees and balanced binary trees, which can be built using arrays, are used in data structures such as a heap, map, and set.
● Multiple variables with the same name are stored in arrays.
● Arrays are used to develop CPU scheduling algorithms.
● Arrays are at the heart of all sorting algorithms.
Q5) Define stack?
A5) A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer (top pointer) pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.
Some key points related to stack
● It is called as stack because it behaves like a real-world stack, piles of books, etc.
● A Stack is an abstract data type with a predefined capacity, which means that it can store the elements of a limited size.
● It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.
Stack Representation
A stack and its operations are depicted in the diagram below.
Array, Structure, Pointer, and Linked List can all be used to create a stack. A stack can be either fixed in size or dynamically resized. We'll use arrays to implement stack here, making it a fixed-size stack implementation.
Q6) Explain push and pop operation of the stack?
A6) PUSH operation
The steps involved in the PUSH operation is given below:
● Before inserting an element in a stack, we check whether the stack is full.
● If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
● When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
● When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
● The elements will be inserted until we reach the max size of the stack.
Fig 4: Push Operation Example
POP operation
The steps involved in the POP operation is given below:
● Before deleting the element from the stack, we check whether the stack is empty.
● If we try to delete the element from the empty stack, then the underflow condition occurs.
● If the stack is not empty, we first access the element which is pointed by the top
● Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Fig 5: Pop Operation example
Q7) What is queue?
A7) A queue is an ordered list that allows insert operations to be done at one end (REAR) and delete operations to be performed at the other end (FRONT). The First In First Out list is referred to as a queue.
For example, create a queue, People in line for a train ticket.
Fig 6: Queue
Operation on queue
● Add (Enqueue) - The enqueue action is used to add the element to the queue's backend. It gives a void result.
● Delete (Dequeue) - The dequeue operation is used to remove items from the queue's front end. It also returns the front-end element that has been removed. It gives you an integer value as a result. It's also possible to make the dequeue operation void.
● Full (queue overflow) - When the Queue is totally full, the overflow condition appears.
● Empty (queue underflow) - The underflow condition is thrown when the Queue is empty, that is, when there are no elements in the Queue.
Q8) Write the application of queue?
A8) Applications of Queue
Because the queue conducts operations on a first-in-first-out basis, the ordering of actions is relatively fair. Queues are used in a variety of ways, as seen below.
● Queues are commonly used as queues for a single shared resource such as a printer, disc, or CPU.
● Pipes, file IO, and sockets all employ queues for asynchronous data transfer (when data is not transferred at the same pace between two processes).
● Most programmes, such as MP3 media players and CD players, use queues as buffers.
● Queues are used to manage the play list in media players, allowing users to add and remove music.
● In operating systems, queues are used to handle interrupts.
Q9) Why was the concept of the circular queue introduced?
A9) There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the Queue then there might be the possibility that some vacant spaces are left in the beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular queue was introduced.
Fig 7: Circular queue
As we can see in the above image, the rear is at the last position of the Queue and the front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and the other three positions are empty. The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.
Q10) Write short notes on Circular Queue?
A10) A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular queue:
● Front: It is used to get the front element from the Queue.
● Rear: It is used to get the rear element from the Queue.
● enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
● deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Q11) Write the application of circular queue?
A11) Applications of Circular Queue
The circular Queue can be used in the following scenarios:
● Memory management: The circular queue provides memory management. As we have already seen in the linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic lights are one of the best examples of the circular queue. Each traffic light gets ON one by one after every interval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After the green light, the red light gets ON.
Q12) What is a priority queue?
A12) A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the values from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.
Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q13) Evaluated postfix expression?
A13) The compiler prefers to evaluate an expression in its postfix form in Infix To Postfix Conversion Using Stack. The advantages of the postfix form include the deletion of parentheses, which indicate evaluation priority, as well as the elimination of the requirement to follow hierarchy, precedence, and associativity rules when evaluating the expression.
Because Postfix expressions have no parenthesis and may be evaluated as two operands and an operator at a time, the compiler and computer can handle them more easily.
A Postfix Expression's evaluation rule is as follows:
- While reading the expression from left to right, push the element in the stack if it is an operand.
- Pop the two operands from the stack, if the element is an operator and then evaluate it.
- Push back the result of the evaluation. Repeat it till the end of the expression.
Algorithm
1) Add ) to postfix expression.
2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
Ii) B-> Next to Top element
Iii) Evaluate B operator A
Push B operator A onto Stack
5) Set result = pop
6) END
Example
Expression: 456*+
Result: 34
Q14) Explain prefix and postfix expression?
A14) If we wish to execute a computation, frame a condition, or do anything else in a programming language, we employ a set of symbols to do it. An expression is made up of these symbols.
The following is an example of a phrase...
A value is represented by an expression, which is made up of operators and operands.
An operator, as defined above, is a symbol that performs a certain task, such as an arithmetic operation, a logical operation, or a conditional operation.
The operands are the values that the operators can use to complete the task. The operand can be a direct value, a variable, or a memory address.
Postfix expression
The operator is used after the operands in a postfix expression. "Operator follows the Operands," as the saying goes.
The following is the general structure of a Postfix expression...
Operand1 Operand2 Operator
Example
Prefix expression
Operator comes before operands in a prefix expression. "Operands follow the Operator," as the saying goes.
The following is the general structure of a Prefix expression...
Operator Operand1 Operand2
Example
Q15) Write the characteristics of priority queue?
A15) Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q16) Implement linked list of queues in c?
A16) The array method cannot be used for large scale applications when queues are established due to the limitations. The linked list version of queue is one of the alternatives to array implementation.
Each node of a linked queue is made up of two parts: the data part and the link part.
In the memory of the linked queue, there are two pointers: front pointer and rear pointer. The front pointer contains the location of the queue's first element, while the back pointer contains the address of the queue's last member.
The linked depiction of the queue is depicted in the diagram below.
Fig 8: Linked queue
Insertion operation
By adding an element to the end of the queue, the insert operation appends it. The new element will be the queue's last element.
To begin, use the following line to allocate memory for the new node ptr.
Ptr = (struct node *) malloc (sizeof(struct node));
There are two possible scenarios for adding this new node ptr to the connected queue.
We inject an element into an empty queue in the first scenario. The condition front = NULL gets true in this scenario.
The queue in the second scenario has more than one element. The condition front = NULL is no longer true. We need to change the end pointer rear in this case such that the next pointer of rear points to the new node ptr. Because this is a linked queue, the rear pointer must also point to the newly inserted node ptr. We must additionally set the rear pointer's next pointer to NULL.
Algorithm
● Step 1: Allocate the space for the new node PTR
● Step 2: SET PTR -> DATA = VAL
● Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
● Step 4: END
C function
Void insert(struct node *ptr, int item; )
{
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
Deletion
The deletion action removes the initial inserted element from all queue elements. To begin, we must determine whether the list is empty or not. If the list is empty, the condition front == NULL becomes true; in this case, we simply write underflow on the console and quit.
Otherwise, the element pointed by the pointer front will be deleted. Copy the node pointed by the front pointer into the pointer ptr for this purpose. Shift the front pointer to the next node and release the node referenced by node ptr. The following statements are used to do this.
Algorithm
● Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
● Step 2: SET PTR = FRONT
● Step 3: SET FRONT = FRONT -> NEXT
● Step 4: FREE PTR
● Step 5: END
C function
Void delete (struct node *ptr)
{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
Q17) How to array implement a queue in c?
A17) Using linear arrays, we can easily describe a queue. In the case of every queue, there are two variables to consider: front and back. In a queue, the front and back variables indicate the location from which insertions and deletions are made. The initial value of front and queue is -1, which indicates that the queue is empty. The next figure shows an array representation of a queue with 5 elements and their respective front and rear values.
Fig 9: Queue
The line of characters that make up the English word "HELLO" is depicted in the diagram above. Because no deletions have been made in the queue to date, the value of front remains -1. When an insertion is performed in the queue, however, the value of rear increases by one. After entering one element into the queue depicted in the above picture, the queue will appear as follows. The value of the rear will increase to 5, while the value of the front will remain unchanged.
Fig 10: Queue after inserting element
The value of front will grow from -1 to 0 if an element is deleted. The queue, on the other hand, will resemble the following.
Fig 11: Queue after deleting element
Algorithm to insert any element in a queue
Compare rear to max - 1 to see if the queue is already full. If this is the case, an overflow error will be returned.
If the item is to be inserted as the first element in the list, set the front and back values to 0 and insert the item at the back end.
Otherwise, keep increasing the value of rear and inserting each element with rear as the index one by one.
Algorithm
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT
C function
Void insert (int queue[], int max, int front, int rear, int item)
{
if (rear + 1 == max)
{
printf("overflow");
}
else
{
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear + 1;
}
queue[rear]=item;
}
}
Algorithm to delete an element from the queue
Write an underflow message and leave if the value of front is -1 or greater than the value of rear.
Otherwise, keep increasing the front's value and returning the item at the front of the queue each time.
Algorithm
● Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
● Step 2: EXIT
C function
Int delete (int queue[], int max, int front, int rear)
{
int y;
if (front == -1 || front > rear)
{
printf("underflow");
}
else
{
y = queue[front];
if(front == rear)
{
front = rear = -1;
else
front = front + 1;
}
return y;
}
}
Unit - 2
Abstract Data Types (ADTs) Arrays
Q1) What is a Single dimensional array?
A1) A one-dimensional array, often known as a single-dimensional array, is one in which a single subscript specification is required to identify a specific array element. We can declare a one-dimensional array as follows:
Data_type array_name [Expression];
Where,
Data_type - The kind of element to be stored in the array is data type.
Array_name - array name specifies the array's name; it can be any type of name, much like other simple variables.
Expression - The number of values to be placed in the array is supplied; arrays are sometimes known as subscripted values; the subscript value must be an integer value, therefore the array's subscript begins at 0.
Example:
Int "a" [10]
Where int: data type
a: array name
10: expression
Output
Data values are dummy values, you can understand after seeing the output, indexing starts from “0”.
Q2) Write about Multidimensional Arrays?
A2) a 2D array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns.
However, 2D arrays are created to implement a relational database look alike data structure. It provides ease of holding bulk data at once which can be passed to any number of functions wherever required.
How to declare 2D Array
The syntax of declaring a two dimensional array is very much similar to that of a one dimensional array, given as follows.
Int arr[max_rows][max_columns];
However, It produces the data structure which looks like the following.
Fig 1: Example
Above image shows the two dimensional array, the elements are organized in the form of rows and columns. First element of the first row is represented by a[0][0] where the number shown in the first index is the number of that row while the number shown in the second index is the number of the column.
Q3) Write short notes on row major and column major ordering?
A3) Row Major ordering
In row major ordering, all the rows of the 2D array are stored into the memory contiguously. Considering the array shown in the above image, its memory allocation according to row major order is shown as follows.
First, the 1st row of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last row.
Fig 2: Row major ordering
Column Major ordering
According to the column major ordering, all the columns of the 2D array are stored into the memory contiguously. The memory allocation of the array which is shown in in the above image is given as follows.
First, the 1st column of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last column of the array.
Fig 3: Column major ordering
Q4) What are the applications of arrays?
A4) Applications of array
● Vectors and lists, which are fundamental parts of the C++ STL, are implemented using arrays.
● Stacks and queues are also implemented using arrays.
● Whenever possible, trees employ array implementation since arrays are easier to manage than pointers. Tress is then utilized to construct a variety of additional data structures.
● Arrays are used to implement matrices, which are an important aspect of every computer language's mathematics library.
● The graph's adjacency list is implemented using vectors, which are then implemented using arrays.
● Binary search trees and balanced binary trees, which can be built using arrays, are used in data structures such as a heap, map, and set.
● Multiple variables with the same name are stored in arrays.
● Arrays are used to develop CPU scheduling algorithms.
● Arrays are at the heart of all sorting algorithms.
Q5) Define stack?
A5) A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer (top pointer) pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.
Some key points related to stack
● It is called as stack because it behaves like a real-world stack, piles of books, etc.
● A Stack is an abstract data type with a predefined capacity, which means that it can store the elements of a limited size.
● It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.
Stack Representation
A stack and its operations are depicted in the diagram below.
Array, Structure, Pointer, and Linked List can all be used to create a stack. A stack can be either fixed in size or dynamically resized. We'll use arrays to implement stack here, making it a fixed-size stack implementation.
Q6) Explain push and pop operation of the stack?
A6) PUSH operation
The steps involved in the PUSH operation is given below:
● Before inserting an element in a stack, we check whether the stack is full.
● If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
● When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
● When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
● The elements will be inserted until we reach the max size of the stack.
Fig 4: Push Operation Example
POP operation
The steps involved in the POP operation is given below:
● Before deleting the element from the stack, we check whether the stack is empty.
● If we try to delete the element from the empty stack, then the underflow condition occurs.
● If the stack is not empty, we first access the element which is pointed by the top
● Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Fig 5: Pop Operation example
Q7) What is queue?
A7) A queue is an ordered list that allows insert operations to be done at one end (REAR) and delete operations to be performed at the other end (FRONT). The First In First Out list is referred to as a queue.
For example, create a queue, People in line for a train ticket.
Fig 6: Queue
Operation on queue
● Add (Enqueue) - The enqueue action is used to add the element to the queue's backend. It gives a void result.
● Delete (Dequeue) - The dequeue operation is used to remove items from the queue's front end. It also returns the front-end element that has been removed. It gives you an integer value as a result. It's also possible to make the dequeue operation void.
● Full (queue overflow) - When the Queue is totally full, the overflow condition appears.
● Empty (queue underflow) - The underflow condition is thrown when the Queue is empty, that is, when there are no elements in the Queue.
Q8) Write the application of queue?
A8) Applications of Queue
Because the queue conducts operations on a first-in-first-out basis, the ordering of actions is relatively fair. Queues are used in a variety of ways, as seen below.
● Queues are commonly used as queues for a single shared resource such as a printer, disc, or CPU.
● Pipes, file IO, and sockets all employ queues for asynchronous data transfer (when data is not transferred at the same pace between two processes).
● Most programmes, such as MP3 media players and CD players, use queues as buffers.
● Queues are used to manage the play list in media players, allowing users to add and remove music.
● In operating systems, queues are used to handle interrupts.
Q9) Why was the concept of the circular queue introduced?
A9) There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the Queue then there might be the possibility that some vacant spaces are left in the beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular queue was introduced.
Fig 7: Circular queue
As we can see in the above image, the rear is at the last position of the Queue and the front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and the other three positions are empty. The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.
Q10) Write short notes on Circular Queue?
A10) A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular queue:
● Front: It is used to get the front element from the Queue.
● Rear: It is used to get the rear element from the Queue.
● enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
● deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Q11) Write the application of circular queue?
A11) Applications of Circular Queue
The circular Queue can be used in the following scenarios:
● Memory management: The circular queue provides memory management. As we have already seen in the linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic lights are one of the best examples of the circular queue. Each traffic light gets ON one by one after every interval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After the green light, the red light gets ON.
Q12) What is a priority queue?
A12) A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the values from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.
Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q13) Evaluated postfix expression?
A13) The compiler prefers to evaluate an expression in its postfix form in Infix To Postfix Conversion Using Stack. The advantages of the postfix form include the deletion of parentheses, which indicate evaluation priority, as well as the elimination of the requirement to follow hierarchy, precedence, and associativity rules when evaluating the expression.
Because Postfix expressions have no parenthesis and may be evaluated as two operands and an operator at a time, the compiler and computer can handle them more easily.
A Postfix Expression's evaluation rule is as follows:
- While reading the expression from left to right, push the element in the stack if it is an operand.
- Pop the two operands from the stack, if the element is an operator and then evaluate it.
- Push back the result of the evaluation. Repeat it till the end of the expression.
Algorithm
1) Add ) to postfix expression.
2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
Ii) B-> Next to Top element
Iii) Evaluate B operator A
Push B operator A onto Stack
5) Set result = pop
6) END
Example
Expression: 456*+
Result: 34
Q14) Explain prefix and postfix expression?
A14) If we wish to execute a computation, frame a condition, or do anything else in a programming language, we employ a set of symbols to do it. An expression is made up of these symbols.
The following is an example of a phrase...
A value is represented by an expression, which is made up of operators and operands.
An operator, as defined above, is a symbol that performs a certain task, such as an arithmetic operation, a logical operation, or a conditional operation.
The operands are the values that the operators can use to complete the task. The operand can be a direct value, a variable, or a memory address.
Postfix expression
The operator is used after the operands in a postfix expression. "Operator follows the Operands," as the saying goes.
The following is the general structure of a Postfix expression...
Operand1 Operand2 Operator
Example
Prefix expression
Operator comes before operands in a prefix expression. "Operands follow the Operator," as the saying goes.
The following is the general structure of a Prefix expression...
Operator Operand1 Operand2
Example
Q15) Write the characteristics of priority queue?
A15) Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q16) Implement linked list of queues in c?
A16) The array method cannot be used for large scale applications when queues are established due to the limitations. The linked list version of queue is one of the alternatives to array implementation.
Each node of a linked queue is made up of two parts: the data part and the link part.
In the memory of the linked queue, there are two pointers: front pointer and rear pointer. The front pointer contains the location of the queue's first element, while the back pointer contains the address of the queue's last member.
The linked depiction of the queue is depicted in the diagram below.
Fig 8: Linked queue
Insertion operation
By adding an element to the end of the queue, the insert operation appends it. The new element will be the queue's last element.
To begin, use the following line to allocate memory for the new node ptr.
Ptr = (struct node *) malloc (sizeof(struct node));
There are two possible scenarios for adding this new node ptr to the connected queue.
We inject an element into an empty queue in the first scenario. The condition front = NULL gets true in this scenario.
The queue in the second scenario has more than one element. The condition front = NULL is no longer true. We need to change the end pointer rear in this case such that the next pointer of rear points to the new node ptr. Because this is a linked queue, the rear pointer must also point to the newly inserted node ptr. We must additionally set the rear pointer's next pointer to NULL.
Algorithm
● Step 1: Allocate the space for the new node PTR
● Step 2: SET PTR -> DATA = VAL
● Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
● Step 4: END
C function
Void insert(struct node *ptr, int item; )
{
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
Deletion
The deletion action removes the initial inserted element from all queue elements. To begin, we must determine whether the list is empty or not. If the list is empty, the condition front == NULL becomes true; in this case, we simply write underflow on the console and quit.
Otherwise, the element pointed by the pointer front will be deleted. Copy the node pointed by the front pointer into the pointer ptr for this purpose. Shift the front pointer to the next node and release the node referenced by node ptr. The following statements are used to do this.
Algorithm
● Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
● Step 2: SET PTR = FRONT
● Step 3: SET FRONT = FRONT -> NEXT
● Step 4: FREE PTR
● Step 5: END
C function
Void delete (struct node *ptr)
{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
Q17) How to array implement a queue in c?
A17) Using linear arrays, we can easily describe a queue. In the case of every queue, there are two variables to consider: front and back. In a queue, the front and back variables indicate the location from which insertions and deletions are made. The initial value of front and queue is -1, which indicates that the queue is empty. The next figure shows an array representation of a queue with 5 elements and their respective front and rear values.
Fig 9: Queue
The line of characters that make up the English word "HELLO" is depicted in the diagram above. Because no deletions have been made in the queue to date, the value of front remains -1. When an insertion is performed in the queue, however, the value of rear increases by one. After entering one element into the queue depicted in the above picture, the queue will appear as follows. The value of the rear will increase to 5, while the value of the front will remain unchanged.
Fig 10: Queue after inserting element
The value of front will grow from -1 to 0 if an element is deleted. The queue, on the other hand, will resemble the following.
Fig 11: Queue after deleting element
Algorithm to insert any element in a queue
Compare rear to max - 1 to see if the queue is already full. If this is the case, an overflow error will be returned.
If the item is to be inserted as the first element in the list, set the front and back values to 0 and insert the item at the back end.
Otherwise, keep increasing the value of rear and inserting each element with rear as the index one by one.
Algorithm
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT
C function
Void insert (int queue[], int max, int front, int rear, int item)
{
if (rear + 1 == max)
{
printf("overflow");
}
else
{
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear + 1;
}
queue[rear]=item;
}
}
Algorithm to delete an element from the queue
Write an underflow message and leave if the value of front is -1 or greater than the value of rear.
Otherwise, keep increasing the front's value and returning the item at the front of the queue each time.
Algorithm
● Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
● Step 2: EXIT
C function
Int delete (int queue[], int max, int front, int rear)
{
int y;
if (front == -1 || front > rear)
{
printf("underflow");
}
else
{
y = queue[front];
if(front == rear)
{
front = rear = -1;
else
front = front + 1;
}
return y;
}
}
Unit - 2
Abstract Data Types (ADTs) Arrays
Q1) What is a Single dimensional array?
A1) A one-dimensional array, often known as a single-dimensional array, is one in which a single subscript specification is required to identify a specific array element. We can declare a one-dimensional array as follows:
Data_type array_name [Expression];
Where,
Data_type - The kind of element to be stored in the array is data type.
Array_name - array name specifies the array's name; it can be any type of name, much like other simple variables.
Expression - The number of values to be placed in the array is supplied; arrays are sometimes known as subscripted values; the subscript value must be an integer value, therefore the array's subscript begins at 0.
Example:
Int "a" [10]
Where int: data type
a: array name
10: expression
Output
Data values are dummy values, you can understand after seeing the output, indexing starts from “0”.
Q2) Write about Multidimensional Arrays?
A2) a 2D array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns.
However, 2D arrays are created to implement a relational database look alike data structure. It provides ease of holding bulk data at once which can be passed to any number of functions wherever required.
How to declare 2D Array
The syntax of declaring a two dimensional array is very much similar to that of a one dimensional array, given as follows.
Int arr[max_rows][max_columns];
However, It produces the data structure which looks like the following.
Fig 1: Example
Above image shows the two dimensional array, the elements are organized in the form of rows and columns. First element of the first row is represented by a[0][0] where the number shown in the first index is the number of that row while the number shown in the second index is the number of the column.
Q3) Write short notes on row major and column major ordering?
A3) Row Major ordering
In row major ordering, all the rows of the 2D array are stored into the memory contiguously. Considering the array shown in the above image, its memory allocation according to row major order is shown as follows.
First, the 1st row of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last row.
Fig 2: Row major ordering
Column Major ordering
According to the column major ordering, all the columns of the 2D array are stored into the memory contiguously. The memory allocation of the array which is shown in in the above image is given as follows.
First, the 1st column of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last column of the array.
Fig 3: Column major ordering
Q4) What are the applications of arrays?
A4) Applications of array
● Vectors and lists, which are fundamental parts of the C++ STL, are implemented using arrays.
● Stacks and queues are also implemented using arrays.
● Whenever possible, trees employ array implementation since arrays are easier to manage than pointers. Tress is then utilized to construct a variety of additional data structures.
● Arrays are used to implement matrices, which are an important aspect of every computer language's mathematics library.
● The graph's adjacency list is implemented using vectors, which are then implemented using arrays.
● Binary search trees and balanced binary trees, which can be built using arrays, are used in data structures such as a heap, map, and set.
● Multiple variables with the same name are stored in arrays.
● Arrays are used to develop CPU scheduling algorithms.
● Arrays are at the heart of all sorting algorithms.
Q5) Define stack?
A5) A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer (top pointer) pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.
Some key points related to stack
● It is called as stack because it behaves like a real-world stack, piles of books, etc.
● A Stack is an abstract data type with a predefined capacity, which means that it can store the elements of a limited size.
● It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.
Stack Representation
A stack and its operations are depicted in the diagram below.
Array, Structure, Pointer, and Linked List can all be used to create a stack. A stack can be either fixed in size or dynamically resized. We'll use arrays to implement stack here, making it a fixed-size stack implementation.
Q6) Explain push and pop operation of the stack?
A6) PUSH operation
The steps involved in the PUSH operation is given below:
● Before inserting an element in a stack, we check whether the stack is full.
● If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
● When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
● When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
● The elements will be inserted until we reach the max size of the stack.
Fig 4: Push Operation Example
POP operation
The steps involved in the POP operation is given below:
● Before deleting the element from the stack, we check whether the stack is empty.
● If we try to delete the element from the empty stack, then the underflow condition occurs.
● If the stack is not empty, we first access the element which is pointed by the top
● Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Fig 5: Pop Operation example
Q7) What is queue?
A7) A queue is an ordered list that allows insert operations to be done at one end (REAR) and delete operations to be performed at the other end (FRONT). The First In First Out list is referred to as a queue.
For example, create a queue, People in line for a train ticket.
Fig 6: Queue
Operation on queue
● Add (Enqueue) - The enqueue action is used to add the element to the queue's backend. It gives a void result.
● Delete (Dequeue) - The dequeue operation is used to remove items from the queue's front end. It also returns the front-end element that has been removed. It gives you an integer value as a result. It's also possible to make the dequeue operation void.
● Full (queue overflow) - When the Queue is totally full, the overflow condition appears.
● Empty (queue underflow) - The underflow condition is thrown when the Queue is empty, that is, when there are no elements in the Queue.
Q8) Write the application of queue?
A8) Applications of Queue
Because the queue conducts operations on a first-in-first-out basis, the ordering of actions is relatively fair. Queues are used in a variety of ways, as seen below.
● Queues are commonly used as queues for a single shared resource such as a printer, disc, or CPU.
● Pipes, file IO, and sockets all employ queues for asynchronous data transfer (when data is not transferred at the same pace between two processes).
● Most programmes, such as MP3 media players and CD players, use queues as buffers.
● Queues are used to manage the play list in media players, allowing users to add and remove music.
● In operating systems, queues are used to handle interrupts.
Q9) Why was the concept of the circular queue introduced?
A9) There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the Queue then there might be the possibility that some vacant spaces are left in the beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular queue was introduced.
Fig 7: Circular queue
As we can see in the above image, the rear is at the last position of the Queue and the front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and the other three positions are empty. The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.
Q10) Write short notes on Circular Queue?
A10) A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular queue:
● Front: It is used to get the front element from the Queue.
● Rear: It is used to get the rear element from the Queue.
● enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
● deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Q11) Write the application of circular queue?
A11) Applications of Circular Queue
The circular Queue can be used in the following scenarios:
● Memory management: The circular queue provides memory management. As we have already seen in the linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic lights are one of the best examples of the circular queue. Each traffic light gets ON one by one after every interval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After the green light, the red light gets ON.
Q12) What is a priority queue?
A12) A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the values from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.
Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q13) Evaluated postfix expression?
A13) The compiler prefers to evaluate an expression in its postfix form in Infix To Postfix Conversion Using Stack. The advantages of the postfix form include the deletion of parentheses, which indicate evaluation priority, as well as the elimination of the requirement to follow hierarchy, precedence, and associativity rules when evaluating the expression.
Because Postfix expressions have no parenthesis and may be evaluated as two operands and an operator at a time, the compiler and computer can handle them more easily.
A Postfix Expression's evaluation rule is as follows:
- While reading the expression from left to right, push the element in the stack if it is an operand.
- Pop the two operands from the stack, if the element is an operator and then evaluate it.
- Push back the result of the evaluation. Repeat it till the end of the expression.
Algorithm
1) Add ) to postfix expression.
2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
Ii) B-> Next to Top element
Iii) Evaluate B operator A
Push B operator A onto Stack
5) Set result = pop
6) END
Example
Expression: 456*+
Result: 34
Q14) Explain prefix and postfix expression?
A14) If we wish to execute a computation, frame a condition, or do anything else in a programming language, we employ a set of symbols to do it. An expression is made up of these symbols.
The following is an example of a phrase...
A value is represented by an expression, which is made up of operators and operands.
An operator, as defined above, is a symbol that performs a certain task, such as an arithmetic operation, a logical operation, or a conditional operation.
The operands are the values that the operators can use to complete the task. The operand can be a direct value, a variable, or a memory address.
Postfix expression
The operator is used after the operands in a postfix expression. "Operator follows the Operands," as the saying goes.
The following is the general structure of a Postfix expression...
Operand1 Operand2 Operator
Example
Prefix expression
Operator comes before operands in a prefix expression. "Operands follow the Operator," as the saying goes.
The following is the general structure of a Prefix expression...
Operator Operand1 Operand2
Example
Q15) Write the characteristics of priority queue?
A15) Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q16) Implement linked list of queues in c?
A16) The array method cannot be used for large scale applications when queues are established due to the limitations. The linked list version of queue is one of the alternatives to array implementation.
Each node of a linked queue is made up of two parts: the data part and the link part.
In the memory of the linked queue, there are two pointers: front pointer and rear pointer. The front pointer contains the location of the queue's first element, while the back pointer contains the address of the queue's last member.
The linked depiction of the queue is depicted in the diagram below.
Fig 8: Linked queue
Insertion operation
By adding an element to the end of the queue, the insert operation appends it. The new element will be the queue's last element.
To begin, use the following line to allocate memory for the new node ptr.
Ptr = (struct node *) malloc (sizeof(struct node));
There are two possible scenarios for adding this new node ptr to the connected queue.
We inject an element into an empty queue in the first scenario. The condition front = NULL gets true in this scenario.
The queue in the second scenario has more than one element. The condition front = NULL is no longer true. We need to change the end pointer rear in this case such that the next pointer of rear points to the new node ptr. Because this is a linked queue, the rear pointer must also point to the newly inserted node ptr. We must additionally set the rear pointer's next pointer to NULL.
Algorithm
● Step 1: Allocate the space for the new node PTR
● Step 2: SET PTR -> DATA = VAL
● Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
● Step 4: END
C function
Void insert(struct node *ptr, int item; )
{
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
Deletion
The deletion action removes the initial inserted element from all queue elements. To begin, we must determine whether the list is empty or not. If the list is empty, the condition front == NULL becomes true; in this case, we simply write underflow on the console and quit.
Otherwise, the element pointed by the pointer front will be deleted. Copy the node pointed by the front pointer into the pointer ptr for this purpose. Shift the front pointer to the next node and release the node referenced by node ptr. The following statements are used to do this.
Algorithm
● Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
● Step 2: SET PTR = FRONT
● Step 3: SET FRONT = FRONT -> NEXT
● Step 4: FREE PTR
● Step 5: END
C function
Void delete (struct node *ptr)
{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
Q17) How to array implement a queue in c?
A17) Using linear arrays, we can easily describe a queue. In the case of every queue, there are two variables to consider: front and back. In a queue, the front and back variables indicate the location from which insertions and deletions are made. The initial value of front and queue is -1, which indicates that the queue is empty. The next figure shows an array representation of a queue with 5 elements and their respective front and rear values.
Fig 9: Queue
The line of characters that make up the English word "HELLO" is depicted in the diagram above. Because no deletions have been made in the queue to date, the value of front remains -1. When an insertion is performed in the queue, however, the value of rear increases by one. After entering one element into the queue depicted in the above picture, the queue will appear as follows. The value of the rear will increase to 5, while the value of the front will remain unchanged.
Fig 10: Queue after inserting element
The value of front will grow from -1 to 0 if an element is deleted. The queue, on the other hand, will resemble the following.
Fig 11: Queue after deleting element
Algorithm to insert any element in a queue
Compare rear to max - 1 to see if the queue is already full. If this is the case, an overflow error will be returned.
If the item is to be inserted as the first element in the list, set the front and back values to 0 and insert the item at the back end.
Otherwise, keep increasing the value of rear and inserting each element with rear as the index one by one.
Algorithm
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT
C function
Void insert (int queue[], int max, int front, int rear, int item)
{
if (rear + 1 == max)
{
printf("overflow");
}
else
{
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear + 1;
}
queue[rear]=item;
}
}
Algorithm to delete an element from the queue
Write an underflow message and leave if the value of front is -1 or greater than the value of rear.
Otherwise, keep increasing the front's value and returning the item at the front of the queue each time.
Algorithm
● Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
● Step 2: EXIT
C function
Int delete (int queue[], int max, int front, int rear)
{
int y;
if (front == -1 || front > rear)
{
printf("underflow");
}
else
{
y = queue[front];
if(front == rear)
{
front = rear = -1;
else
front = front + 1;
}
return y;
}
}
Unit - 2
Abstract Data Types (ADTs) Arrays
Q1) What is a Single dimensional array?
A1) A one-dimensional array, often known as a single-dimensional array, is one in which a single subscript specification is required to identify a specific array element. We can declare a one-dimensional array as follows:
Data_type array_name [Expression];
Where,
Data_type - The kind of element to be stored in the array is data type.
Array_name - array name specifies the array's name; it can be any type of name, much like other simple variables.
Expression - The number of values to be placed in the array is supplied; arrays are sometimes known as subscripted values; the subscript value must be an integer value, therefore the array's subscript begins at 0.
Example:
Int "a" [10]
Where int: data type
a: array name
10: expression
Output
Data values are dummy values, you can understand after seeing the output, indexing starts from “0”.
Q2) Write about Multidimensional Arrays?
A2) a 2D array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns.
However, 2D arrays are created to implement a relational database look alike data structure. It provides ease of holding bulk data at once which can be passed to any number of functions wherever required.
How to declare 2D Array
The syntax of declaring a two dimensional array is very much similar to that of a one dimensional array, given as follows.
Int arr[max_rows][max_columns];
However, It produces the data structure which looks like the following.
Fig 1: Example
Above image shows the two dimensional array, the elements are organized in the form of rows and columns. First element of the first row is represented by a[0][0] where the number shown in the first index is the number of that row while the number shown in the second index is the number of the column.
Q3) Write short notes on row major and column major ordering?
A3) Row Major ordering
In row major ordering, all the rows of the 2D array are stored into the memory contiguously. Considering the array shown in the above image, its memory allocation according to row major order is shown as follows.
First, the 1st row of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last row.
Fig 2: Row major ordering
Column Major ordering
According to the column major ordering, all the columns of the 2D array are stored into the memory contiguously. The memory allocation of the array which is shown in in the above image is given as follows.
First, the 1st column of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last column of the array.
Fig 3: Column major ordering
Q4) What are the applications of arrays?
A4) Applications of array
● Vectors and lists, which are fundamental parts of the C++ STL, are implemented using arrays.
● Stacks and queues are also implemented using arrays.
● Whenever possible, trees employ array implementation since arrays are easier to manage than pointers. Tress is then utilized to construct a variety of additional data structures.
● Arrays are used to implement matrices, which are an important aspect of every computer language's mathematics library.
● The graph's adjacency list is implemented using vectors, which are then implemented using arrays.
● Binary search trees and balanced binary trees, which can be built using arrays, are used in data structures such as a heap, map, and set.
● Multiple variables with the same name are stored in arrays.
● Arrays are used to develop CPU scheduling algorithms.
● Arrays are at the heart of all sorting algorithms.
Q5) Define stack?
A5) A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer (top pointer) pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.
Some key points related to stack
● It is called as stack because it behaves like a real-world stack, piles of books, etc.
● A Stack is an abstract data type with a predefined capacity, which means that it can store the elements of a limited size.
● It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.
Stack Representation
A stack and its operations are depicted in the diagram below.
Array, Structure, Pointer, and Linked List can all be used to create a stack. A stack can be either fixed in size or dynamically resized. We'll use arrays to implement stack here, making it a fixed-size stack implementation.
Q6) Explain push and pop operation of the stack?
A6) PUSH operation
The steps involved in the PUSH operation is given below:
● Before inserting an element in a stack, we check whether the stack is full.
● If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
● When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
● When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
● The elements will be inserted until we reach the max size of the stack.
Fig 4: Push Operation Example
POP operation
The steps involved in the POP operation is given below:
● Before deleting the element from the stack, we check whether the stack is empty.
● If we try to delete the element from the empty stack, then the underflow condition occurs.
● If the stack is not empty, we first access the element which is pointed by the top
● Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Fig 5: Pop Operation example
Q7) What is queue?
A7) A queue is an ordered list that allows insert operations to be done at one end (REAR) and delete operations to be performed at the other end (FRONT). The First In First Out list is referred to as a queue.
For example, create a queue, People in line for a train ticket.
Fig 6: Queue
Operation on queue
● Add (Enqueue) - The enqueue action is used to add the element to the queue's backend. It gives a void result.
● Delete (Dequeue) - The dequeue operation is used to remove items from the queue's front end. It also returns the front-end element that has been removed. It gives you an integer value as a result. It's also possible to make the dequeue operation void.
● Full (queue overflow) - When the Queue is totally full, the overflow condition appears.
● Empty (queue underflow) - The underflow condition is thrown when the Queue is empty, that is, when there are no elements in the Queue.
Q8) Write the application of queue?
A8) Applications of Queue
Because the queue conducts operations on a first-in-first-out basis, the ordering of actions is relatively fair. Queues are used in a variety of ways, as seen below.
● Queues are commonly used as queues for a single shared resource such as a printer, disc, or CPU.
● Pipes, file IO, and sockets all employ queues for asynchronous data transfer (when data is not transferred at the same pace between two processes).
● Most programmes, such as MP3 media players and CD players, use queues as buffers.
● Queues are used to manage the play list in media players, allowing users to add and remove music.
● In operating systems, queues are used to handle interrupts.
Q9) Why was the concept of the circular queue introduced?
A9) There was one limitation in the array implementation of Queue. If the rear reaches to the end position of the Queue then there might be the possibility that some vacant spaces are left in the beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular queue was introduced.
Fig 7: Circular queue
As we can see in the above image, the rear is at the last position of the Queue and the front is pointing somewhere rather than the 0th position. In the above array, there are only two elements and the other three positions are empty. The rear is at the last position of the Queue; if we try to insert the element then it will show that there are no empty spaces in the Queue. There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly. It is not a practically good approach because shifting all the elements will consume lots of time. The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.
Q10) Write short notes on Circular Queue?
A10) A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out) principle except that the last position is connected to the first position in a circular queue that forms a circle. It is also known as a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular queue:
● Front: It is used to get the front element from the Queue.
● Rear: It is used to get the rear element from the Queue.
● enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
● deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Q11) Write the application of circular queue?
A11) Applications of Circular Queue
The circular Queue can be used in the following scenarios:
● Memory management: The circular queue provides memory management. As we have already seen in the linear queue, the memory is not managed very efficiently. But in case of a circular queue, the memory is managed efficiently by placing the elements in a location which is unused.
● CPU Scheduling: The operating system also uses the circular queue to insert the processes and then execute them.
● Traffic system: In a computer-control traffic system, traffic lights are one of the best examples of the circular queue. Each traffic light gets ON one by one after every interval of time. Like red light gets ON for one minute then yellow light for one minute and then green light. After the green light, the red light gets ON.
Q12) What is a priority queue?
A12) A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an ordering imposed on the values from least to the greatest. Therefore, the 1 number would be having the highest priority while 22 will be having the lowest priority.
Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q13) Evaluated postfix expression?
A13) The compiler prefers to evaluate an expression in its postfix form in Infix To Postfix Conversion Using Stack. The advantages of the postfix form include the deletion of parentheses, which indicate evaluation priority, as well as the elimination of the requirement to follow hierarchy, precedence, and associativity rules when evaluating the expression.
Because Postfix expressions have no parenthesis and may be evaluated as two operands and an operator at a time, the compiler and computer can handle them more easily.
A Postfix Expression's evaluation rule is as follows:
- While reading the expression from left to right, push the element in the stack if it is an operand.
- Pop the two operands from the stack, if the element is an operator and then evaluate it.
- Push back the result of the evaluation. Repeat it till the end of the expression.
Algorithm
1) Add ) to postfix expression.
2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
Ii) B-> Next to Top element
Iii) Evaluate B operator A
Push B operator A onto Stack
5) Set result = pop
6) END
Example
Expression: 456*+
Result: 34
Q14) Explain prefix and postfix expression?
A14) If we wish to execute a computation, frame a condition, or do anything else in a programming language, we employ a set of symbols to do it. An expression is made up of these symbols.
The following is an example of a phrase...
A value is represented by an expression, which is made up of operators and operands.
An operator, as defined above, is a symbol that performs a certain task, such as an arithmetic operation, a logical operation, or a conditional operation.
The operands are the values that the operators can use to complete the task. The operand can be a direct value, a variable, or a memory address.
Postfix expression
The operator is used after the operands in a postfix expression. "Operator follows the Operands," as the saying goes.
The following is the general structure of a Postfix expression...
Operand1 Operand2 Operator
Example
Prefix expression
Operator comes before operands in a prefix expression. "Operands follow the Operator," as the saying goes.
The following is the general structure of a Prefix expression...
Operator Operand1 Operand2
Example
Q15) Write the characteristics of priority queue?
A15) Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
● Every element in a priority queue has some priority associated with it.
● An element with the higher priority will be deleted before the deletion of the lesser priority.
● If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Q16) Implement linked list of queues in c?
A16) The array method cannot be used for large scale applications when queues are established due to the limitations. The linked list version of queue is one of the alternatives to array implementation.
Each node of a linked queue is made up of two parts: the data part and the link part.
In the memory of the linked queue, there are two pointers: front pointer and rear pointer. The front pointer contains the location of the queue's first element, while the back pointer contains the address of the queue's last member.
The linked depiction of the queue is depicted in the diagram below.
Fig 8: Linked queue
Insertion operation
By adding an element to the end of the queue, the insert operation appends it. The new element will be the queue's last element.
To begin, use the following line to allocate memory for the new node ptr.
Ptr = (struct node *) malloc (sizeof(struct node));
There are two possible scenarios for adding this new node ptr to the connected queue.
We inject an element into an empty queue in the first scenario. The condition front = NULL gets true in this scenario.
The queue in the second scenario has more than one element. The condition front = NULL is no longer true. We need to change the end pointer rear in this case such that the next pointer of rear points to the new node ptr. Because this is a linked queue, the rear pointer must also point to the newly inserted node ptr. We must additionally set the rear pointer's next pointer to NULL.
Algorithm
● Step 1: Allocate the space for the new node PTR
● Step 2: SET PTR -> DATA = VAL
● Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
● Step 4: END
C function
Void insert(struct node *ptr, int item; )
{
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
Deletion
The deletion action removes the initial inserted element from all queue elements. To begin, we must determine whether the list is empty or not. If the list is empty, the condition front == NULL becomes true; in this case, we simply write underflow on the console and quit.
Otherwise, the element pointed by the pointer front will be deleted. Copy the node pointed by the front pointer into the pointer ptr for this purpose. Shift the front pointer to the next node and release the node referenced by node ptr. The following statements are used to do this.
Algorithm
● Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
● Step 2: SET PTR = FRONT
● Step 3: SET FRONT = FRONT -> NEXT
● Step 4: FREE PTR
● Step 5: END
C function
Void delete (struct node *ptr)
{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
Q17) How to array implement a queue in c?
A17) Using linear arrays, we can easily describe a queue. In the case of every queue, there are two variables to consider: front and back. In a queue, the front and back variables indicate the location from which insertions and deletions are made. The initial value of front and queue is -1, which indicates that the queue is empty. The next figure shows an array representation of a queue with 5 elements and their respective front and rear values.
Fig 9: Queue
The line of characters that make up the English word "HELLO" is depicted in the diagram above. Because no deletions have been made in the queue to date, the value of front remains -1. When an insertion is performed in the queue, however, the value of rear increases by one. After entering one element into the queue depicted in the above picture, the queue will appear as follows. The value of the rear will increase to 5, while the value of the front will remain unchanged.
Fig 10: Queue after inserting element
The value of front will grow from -1 to 0 if an element is deleted. The queue, on the other hand, will resemble the following.
Fig 11: Queue after deleting element
Algorithm to insert any element in a queue
Compare rear to max - 1 to see if the queue is already full. If this is the case, an overflow error will be returned.
If the item is to be inserted as the first element in the list, set the front and back values to 0 and insert the item at the back end.
Otherwise, keep increasing the value of rear and inserting each element with rear as the index one by one.
Algorithm
Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT
C function
Void insert (int queue[], int max, int front, int rear, int item)
{
if (rear + 1 == max)
{
printf("overflow");
}
else
{
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear + 1;
}
queue[rear]=item;
}
}
Algorithm to delete an element from the queue
Write an underflow message and leave if the value of front is -1 or greater than the value of rear.
Otherwise, keep increasing the front's value and returning the item at the front of the queue each time.
Algorithm
● Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
● Step 2: EXIT
C function
Int delete (int queue[], int max, int front, int rear)
{
int y;
if (front == -1 || front > rear)
{
printf("underflow");
}
else
{
y = queue[front];
if(front == rear)
{
front = rear = -1;
else
front = front + 1;
}
return y;
}
}