Description
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
