CS2092D-ASSIGNMENT 5 Solved

QUESTIONS

 

3.    Write a menu driven program to implement a Stack S of at most n elements using an array A[0..n − 1]. Stack is to be declared as a struct with an attribute top and an array A[0..n − 1] as members. The attribute top indexes the most recently inserted element in the stack. The stack consists of elements A[0..S.top] where A[0] is the element at the bottom of the stack and A[S.top] is the element at the top. Your program must contain the following functions: (In function prototypes, S denotes a stack, and k denotes a character. All operations should run in O(1) time.)

•   Main() - repeatedly reads a character ‘i’, ‘d’, ‘p’ or ‘t’ from the terminal and calls the appropriate function until character ‘t’ is entered.

•   Stack-Empty(S) - checks whether the Stack S is empty or not. It returns −1 when S is empty, else returns 1.

•   Stack-Full(S) - checks whether the Stack S is full or not. It returns −1 when S is full, else returns 1.

•   Push(S,k) - inserts k to the top of S (check Stack-Full() inside this function).

•   Pop(S) - prints and deletes the most recently inserted element from S (check Stack-Empty() inside this function).

•   Peek(S) - returns the top element of S.

Input format:

•   The first line of the input contains an integer n ∈ [0,105], the capacity of stack S.

•   Upcoming lines starts with a character from ‘i’, ‘d’, ‘p’, or ‘t’ followed by zero or one upper case alphabet.

•   Character ‘i’ is followed by a character C ∈ [A..Z] separated by a space. In this operation, the character C is inserted to S by calling the function Push(S,k).

•   Character ‘d’ is to perform the Pop operation on S by calling the function Pop(S).

•   Character ‘p’ is to perform the Peek operation on S by calling the function Peek(S).

•   Character ‘t’ is to ‘terminate’ the program.

Output Format:

•   The output (if any) of each command should be printed on a separate line.

•   For option ‘i’:  Print -1 if S is full.

•   For option ‘p’and ‘d’: Print -1 if S is empty.

Sample Input :

5

i D i H d i A i D i Z i K i X d d d p i Y d

d d p d

t

Sample Output:

H

-1

K

Z

D A

Y

A D

-1

-1

4.    Write a menu driven program to implement a Queue Q using an array A[0..n − 1]. Queue is to be declared as a struct with three attributes:- head, tail and array A[0..n − 1]. The attribute Q.head indexes its head and Q.tail indexes the next location at which a newly arriving element will be inserted into the queue. The elements in the queue reside in locations Q.head, Q.head+1,...., Q.tail-1, where the location 0 immediately follows location n-1 in a circular order.Your program must contain the following functions: (in function prototypes, Q denotes a Queue and S denotes a string of characters. All operations should run in O(1) time.)

•   Main() - repeatedly reads a character ‘i’, ‘d’, ‘f’ or ‘e’ from terminal and calls the appropriate function until character ‘t’ is entered.

•   QueueFull(Q) - checks whether the Queue is full or not. It returns −1 when Q is full, else returns 1.

•   QueueEmpty(Q) - checks whether the Queue is empty or not. It returns −1 when Q is empty, else returns 1.

•   Enqueue(Q,S) - inserts the element S to the tail of Q (check QueueFull() inside this function).

•   Dequeue(Q) - prints and deletes the element from the head of Q (check QueueEmpty() inside this function).

Input format:

•   The first line of the input contains an integer n ∈ [0,105], the size of the array A.

•   Upcoming lines starts with a character from ‘i’, ‘d’, ‘f’ or ‘e’ followed by zero or one string of characters.

•   Character ‘i’ is followed by a string S ∈ [A−Z,a−z,0−9] of at most 20 characters separated by a space. In this operation, string S is inserted to the tail of Q by calling the function Enqueue(Q,S).

•   Character ‘d’ is to perform the Dequeue operation on Q by calling the function Dequeue(Q).

•   Character ‘f’ is to check whether the Queue is full or not by calling the function QueueFull(Q).

•   Character ‘e’ is to check whether the Queue is empty or not by calling the function QueueEmpty(Q).

•   Character ‘t’ is to ‘terminate’ the program.

Output Format:

•   The output (if any) of each command should be printed on a separate line.

•   For option ‘i’and ‘f’:       Print −1 if Q is full.

•   For option ‘d’and ‘e’:     Print −1 if Q is empty.

•   For option ‘f’: Print 1 if Q is not full.

•   For option ‘e’, Print 1 if Q is not empty.

Sample Input 5 i Abc20 i Xyz38 d d d e i Nit40 e i IIT35 i IIM42

f

i Fix33 i Calc27

f d

t

Sample Output

Abc20

Xyz38

-1

-1

1

1

-1

Nit40