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 appro- priate 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 iD iH d iA iD iZ iK iX d d d p iY d
2
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’istocheckwhethertheQueueisfullornotbycallingthefunctionQueueFull(Q).
- Character‘e’istocheckwhethertheQueueisemptyornotbycallingthefunctionQueueEmpty(Q).
- Character ‘t’ is to ‘terminate’ the program.
Output Format:
• The output (if any) of each command should be printed on a separate line. 3
• 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
4
