The Stack and Queue

Questions And Solutions

2079 Ashwin

Q.N. 11 For circular queue, write algorithm to implement enqueue () and dequeue () opeartion with all the required conditions and appropirate daigrams. Convert the following infix to postfix expression with required status of stack.
((a+((b*c)/(d-e))))

Solution Algorithm for the implementation of circular enqueue and dequeue opeartion

1. Declare and initilize necessary variables front =0, rear = -1, maxsize, item, queue[maxsize].
   
2. For enqueue operation
     If front = (rear+1)% maxsize
     print "queue is full"
     else
     read item from user
     queue[rear]=item
     rear = (rear+1) % maxsize
   
3. For next enqueue operation repeat step 2
   
4. For dequeue operation
     If front == rear
     print "queue is empty"
     else
     item = queue[front]
     front= (front+1) % maxsize
     display item
   
5. For next dequeue operation repeat step 4
   

Infix Expression: ((A+((B*C)/(D-E))))

Conversion Table:

Final Postfix Expression: A B C * D E - / +

2078 Chaitra

Define stack. Convert following infix expression to postfix expression showing stack status in each step; A*(B+C) -(B^D)*A + E / F.

Answer:

Stack is an ordered collection of items in to which new items may be inserted and from which items may be delete at one end, called tope of the stack.
Two operations are possible on stack:-

1. push:- Add item in to stack.
2. Pop :- delete the item from stack.

Infix Expression: A*(B + C) - (B^D)*A + E / F

Conversion Table:

Final Postfix Expression: A B C + x B D ^ A x - E F / +

Q.N. 2: Convert the following infix expression postfix expression showing stack status in each step: A + (B * C - (D / E ^ F) * G) * H.

Solution:

Infix Expression: A + (B * C - (D / E ^ F) * G) * H

Conversion Table:

Final Postfix Expression: A B C * D E F ^ / G * - H * +

Q.N. 3 What is a queue? Explain circular queue as an ADT.

Solution:

A queue is an ordered collection of the items from which the items may be inserted at one end and also can be deleted form the other end. Queue, one of the important parts of the data structure has two parts: Front and Rear.The items that are newly c related are inserted from the rear side of the queue and the items to be removed are deleted from the front side of the queue.A queue is also called as a FIFO (first-in-first-out) list because the items that are inserted first are deleted or removed from the queue first.

2074 Bhadra

Define queue. Explain enqueue and dequeue operation with example.

Solution:

Queue is the collection of elements where insertion occurs at the rear and deletion occurs at the front. Queue is called a FIFO (first-in-first-out) list because the elements inserted first are deleted or removed from the queue first.

Enqueue Operation: The enqueue operation is used to insert an element at the end of the queue. It adds the element at the end of the queue and moves the rear pointer to the next position.

Dequeue Operation: The dequeue operation is used to delete an element from the front of the queue. It deletes the element from the front of the queue and moves the front pointer to the next position.

Visualization of Enqueue Operation:

2073 Bhadra

Explain how a circular queue differs from linear queue with suitable example. Show status of stack while converting following infix expression to postfix expression: A+B-(CD/E+F)-GH.

Solution:

A circular queue is an ordered list in which insertion are done at one end (rear) and deletion are done from the other end (front). It is based on First In First Out (FIFO).

A linear queue is one where elements can be inserted until it becomes full, but once the queue is full, no new elements can be inserted until all existing elements are deleted.

Example of linear queue:

Example of circular queue:

Here, after the first two spots open up, new element can be added immediately. This is how circular queue differs from linear queue.

Infix Expression: A + B - ( C * D / E + F ) - G * H

Conversion Table:

Final Postfix Expression: A B + C D * E / F + - G H * -

2072 Ashwin(Stack)

What is a stack? Write an algorithm to convert infix expression into postfix expression using stack.

Solution

Stack is an ordered collection of items in to which new items may be inserted and from which items may be delete at one end, called tope of the stack.

Algorithm to convert infix to postfix expression

Step 1 : Scan one character at a time from left to right.
Step 2 : Repeat while there is data
  a. if "(" push it into the stack
  b. if operand, Append it into postfix string
  c. if operator
    i. if Stack is empty push it onto stack
    ii. if not repeat till precedence of top of stack (tos) >= Scan character
    iii. Pop tos and append into postfix
    iv. push Scan character into stack
  d. if ")" is found
   i. Pop and append to Postfix until matching "(" is found and ignore both.
Step 3 : Pop and append to Postfix until stack is empty.
Step 4 : Return

2072 Ashwin(Queue)

Define a queue. Explain enqueue and dequeue operation in circuit queue.

Solution

Queue is the collection of elements where insertion occurs at the rear and deletion occurs at the front. Queue is called a FIFO (first-in-first-out) list because the elements inserted first are deleted or removed from the queue first.

A circular queue is a type of queue in which the last position is connected to the first position, forming a circle. This structure helps efficiently utilize memory by reusing previously freed spaces. It is implemented using an array along with two pointers, front and rear, track the start and end of the queue.

Enqueue operation (Insertion) The enqueue operation adds an element to the rear of the circular queue. dequeue operation (Deletion) The dequeue operation removes an element from the front of the circular queue.

The following code demonstrates a circular queue implementation in C, including enqueue, dequeue, and display operations.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 4

typedef struct {
    int data[SIZE];
    int front;
    int rear;
} CircularQueue;

void initializeQueue(CircularQueue *q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(CircularQueue *q) {
    return (q->rear + 1) % SIZE == q->front;
}

int isEmpty(CircularQueue *q) {
    return q->front == -1;
}

void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow! Cannot insert %d\n", value);
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % SIZE;
    q->data[q->rear] = value;
    printf("Inserted %d into the queue\n", value);
}

int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue Underflow! Cannot remove an element.\n");
        return -1;
    }
    int removedValue = q->data[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % SIZE;
    }
    printf("Removed %d from the queue\n", removedValue);
    return removedValue;
}

void displayQueue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    int i = q->front;
    while (1) {
        printf("%d ", q->data[i]);
        if (i == q->rear) {
            break;
        }
        i = (i + 1) % SIZE;
    }
    printf("\n");
}

int main() {
    CircularQueue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    displayQueue(&q);

    dequeue(&q);
    displayQueue(&q);

    enqueue(&q, 70);
    displayQueue(&q);

    return 0;
}

Output

Inserted 10 into the queue
Inserted 20 into the queue
Inserted 30 into the queue
Inserted 40 into the queue
Queue elements: 10 20 30 40
Removed 10 from the queue
Queue elements: 20 30 40
Inserted 70 into the queue
Queue elements: 20 30 40 70

2066 Bhadra

Can you always insert an item into an empty queue? Explain with possible reasons and example? Explain the advantages of dynamic implementation of stack and queue over sequential storage to represent stack and queue.

Solution

Yes, we can always insert an item into an empty queue, provided there are no constraints or limitations on the queue's implementation, such as memory or capacity restrictions. For example:

Dynamic Queue (Linked List):

queue = [] //Empty queue
queue.append(10)
print(queue)

Static Queue(Fixed Queue):

queue = [None] * 5  //Empty queue with capacity 5
queue[0] = 10
print(queue)

Advantages of Dynamic Implementation:

1:Dynamic Size:
Dynamic Implementation: The size of a stack or queue can grow or shrink as needed, limited only by available memory.
Sequential Storage: Requires predefined array size. Resizing involves overhead, such as allocating a larger array and copying elements.

2:Efficient Memory Utilization:
  Dynamic Implementation: Allocates memory for elements as needed. No memory is wasted for unused slots..
Sequential Storage: May waste memory if the array size is overestimated or face overflow if underestimated.

3:Efficient Insertions and Deletions:
Dynamic Implementation: Insertions and deletions are O(1) for stacks and queues since only pointers need adjustment.
Sequential Storage: Insertions and deletions might take 𝑂(𝑛)due to the need to shift elements (e.g., in a queue)

4:No Overflow (Unless Memory is Full):
Dynamic Implementation: Does not encounter overflow unless the system runs out of memory.
Sequential Storage: Can lead to overflow if the array size is exceeded, even if sufficient memory is available in the system.

Q.N.9 Write an algorithm for converting infix expression to postfix expression. Convert a given infix expression: A + ( B _ C - ( D / E - F ) _ G ) * H into postfix expression showing stack status after every step in tabular form.

Solution

Algorithm to convert infix to postfix expression

Step 1 : Scan one character at a time from left to right.
Step 2 : Repeat while there is data
  a. if "(" push it into the stack
  b. if operand, Append it into postfix string
  c. if operator
    i. if Stack is empty push it onto stack
    ii. if not repeat till precedence of top of stack (tos) >= Scan character
    iii. Pop tos and append into postfix
    iv. push Scan character into stack
  d. if ")" is found
   i. Pop and append to Postfix until matching "(" is found and ignore both.
Step 3 : Pop and append to Postfix until stack is empty.
Step 4 : Return

Infix Expression: A + ( B * C - (D / E - F ) * G ) * H

Conversion Table:

Final Postfix Expression: A B C * D E / F - G * - H * +

2065 Shrawan(Queue)

What do you mean by abstract data type? Write an algorithm for enque and dequeue operations in a queue.

Solution

An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and behaviours for a data type, without specifying how these operations are implemented or how data is organized in memory.

Algorithm for enque and dequeue operation in linear queue

1. Declare and initilize necessary variables front =0, rear = -1, maxsize, item, queue[maxsize].
   
2. For enqueue operation
     If rear >= maxsize -1
     print "queue is full"
     else
     read item from user
     rear= rear+1
     queue[rear]=item
   
3. For next enqueue operation repeat step 2
   
4. For dequeue operation
     If front > rear
     print "queue is empty"
     else
     item = queue[front]
     front= front+1
     display item
   
5. For next dequeue operation repeat step 4
   

Algorithm for enque and dequeue operation in circular queue

1. Declare and initilize necessary variables front =0, rear = -1, maxsize, item, queue[maxsize].
   
2. For enqueue operation
     If front = (rear+1)% maxsize
     print "queue is full"
     else
     read item from user
     queue[rear]=item
     rear = (rear+1) % maxsize
   
3. For next enqueue operation repeat step 2
   
4. For dequeue operation
     If front == rear
     print "queue is empty"
     else
     item = queue[front]
     front= (front+1) % maxsize
     display item
   
5. For next dequeue operation repeat step 4
   

2065 Shrawan(Stack)

Define stack as an ADT? Convert the following infix expression onto prefix and postfix.
a) A+[B+C+(D+E)*F]/G
b) ((a+b) * c-(d- e) $ (f + g))

Solution

A stack is an ordered collection of items into which new items may be inserted and from which items may be removed at one end called the top of stack.

Infix Expression: A+[B+C+(D+E)*F]/G

For prefix expression first the reverse the infix expression we get,

** new Infix Expression:** G/]F*)E+D(+C+B[+A

Conversion Table:

Again, for prefix reversing the obtained expression : + A / + B + C * + D E F G

Final Prefix Expression: + A / + B + C * + D E F G

Infix Expression: A + [ B + C + ( D + E ) * F ] / G

Conversion Table:

Final Postfix Expression: A B C + D E + F * + G / +

Infix Expression: ((A+B) * C-(D - E) $ (F + G))

For prefix expression first the reverse the infix expression we get,

New Infix Expression: ) G + F $ ) E - D ( - C * ) B + A ( (

Conversion Table:

Again, for prefix reversing the obtained expression : - _ + A B C _ + D E F G

Final Prefix Expression: - * + A B C * + D E F G

Infix Expression: ((a+b) * c-(d- e) $ (f + g))

Conversion Table:

Final Postfix Expression: A B + c * D E - $ F G + -

Q.N. 11 Convert the infix expression; A+B-(CD/E+ F)-GH into postfix expression using stack. Evaluate the converted postfix expression using stack for A=10, B=5, C=4, D=6, E=3, F=8, G-2, and H=l.

Solution

Infix Expression: A+B-(C*D/E+ F)-G*H

Conversion Table:

Final Postfix Expression: A B + C D / F + G H * -

Given value A=10, B=5, C=4, D=6, E=3, F=8, G-2, and H=l. Replacing variables with value 10 5 + 4 6 * 3 / 8 + - 2 1 * -

Step-by-step evaluation using a stack:
  10 5 +: Push 10, 5. Pop 10, 5; push 15.
  4 6 *: Push 4, 6. Pop 4, 6; push 24.
  3 /: Push 3. Pop 24, 3; push 8.
  8 +: Push 8. Pop 8, 8; push 16.
  15 16 -: Push 15, 16. Pop 15, 16; push -1.
  2 1 *: Push 2, 1. Pop 2, 1; push 2.
  -1 2 -: Push -1, 2. Pop -1, 2; push -3.

Final Result: -3

Q.N. 12 What are the problems with linear queue. Explain different queue operations in circular queue.

Solution The problem with the linear queue is, if the last position of the queue is occupied, it is not possible to enqueuing any more elements even though some positions are vacant towards the front positions of the queue.

Different queue opeartion on circular queue are:

1. getFront: Get the front item from the queue.
   
2. getRear: Get the last item from the queue.
   
3. enqueue(value): To insert an element into the circular queue. In a circular queue, the new element is always inserted at the rear position.
   
4. dequeue(): To delete an element from the circular queue. In a circular queue, the element is always deleted from the front position.