CS2092D Assignment #7 Solution

QUESTIONS

1. 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 an integer. All operations should run in O(1) time.)
• Main() - repeatedly reads a character ‘i’, ‘d’, ‘e’ 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.
• Stack-Full(S) - checks whether the Stack S is full or not.
• Push(S,k) - inserts k to the top of S (check Stack-Full() inside this function).
• Pop(S) - deletes the most recently inserted element from S.
Input format:
• The first line of the input contains an integer n ∈ [0,105], the size of the array A.
• Upcoming lines contain a character from ‘i’, ‘d’, ‘e’, or ‘t’ followed by zero or one integer. The integer, if given, is in the range [−106,106].
• Character ‘i’ is followed by an integer separated by space. In this operation, the integer is inserted to the top of S.
• Character ‘d’ is to delete and print the most recently inserted element from S.
• Character ‘e’ is to check whether the Stack is empty or not.
• 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 ‘d’, print the deleted element. If S is empty, then print −1.
• For option ‘e’, if S is not empty, then print 1. If S is empty, then print −1.
Sample Input :
10 i 8 i 10 d i 12 d d d e i 18 e t
Sample Output:
10
12
8
-1
-1
1
2. Write a menu driven program to implement a Stack S using a singly linked list. Each node in the list has an integer attribute data and a pointer attribute next. Keep S.top point to the first node (node at the front end) of the list. Your program must contain the following functions: (in function prototypes, S denotes a Stack, k an integer value, and x a node in the list. All operations should run in O(1) time.)
• Main() - repeatedly reads a character ‘i’, ‘d’, ‘e’ or ‘t’ from the terminal and calls the appropriate function until character ‘t’ is entered.
• Create-Node(k) - creates a new node with data value k and returns a pointer to the created node. The attribute next of the new node should be set as NULL.
• Push(S,x) - inserts x as the new top node of S.
• Pop(S) - deletes the most recently inserted node from S.
• Stack-Empty(S) - checks whether the Stack is empty or not.
Note:- For every Push() operation, the node x is to be created by calling the Create-Node() function.
Input format:
• Each line contains a character from ‘i’, ‘d’, ‘e’, or ‘t’ followed by zero or one integer. The integer, if given, is in the range [−106,106].
• Character ‘i’ is followed by an integer separated by space. In this operation, the node with this integer as data is inserted to the front end of S.
• Character ‘d’ is to delete the most recently inserted node and the deleted node’s data value is printed.
• Character ‘e’ is to check whether the Stack is empty or not.
• 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 ‘d’ print the deleted element. If S is empty, then print −1.
• For option ‘s’ if S is not empty, then print 1. If S is empty, then print −1.
Sample Input :
i 10i 15 d i 12 d d d e i 20 e t
Sample Output:
15
12
10
-1
-1
1
3. Write a menu driven program to implement a Queue Q using an array A[0..n − 1]. The queue is to be declared as a struct with two attributes- head and tail. 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 k denotes an integer. 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.
• QueueEmpty(Q) - checks whether the Queue is empty or not.
• Enqueue(Q,k) - inserts the element k to the tail of Q (check QueueFull() inside this function).
• Dequeue(Q) - 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 contain a character from ‘i’, ‘d’, ‘f’ or ‘e’ followed by zero or one integer. The integer, if given, is in the range [−106,106].
• Character ‘i’ is followed by an integer separated by space. In this operation, this integer is inserted to the tail of Q.
• Character ‘d’ is to delete first element from Q and print the deleted element.
• Character ‘f’ is to check whether the Queue is full or not.
• Character ‘e’ is to check whether the Queue is empty or not.
• 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’ if Q is full, then print −1.
• For option ‘d’ delete the first node and print the deleted node’s key. If Q is empty, then print −1.
• For option ‘f’, if Q is not full, then print 1. If Q is full, then print −1.
• For option ‘e’, if Q is not empty, then print 1. If Q is empty, then print −1.
Sample Input
5 i 20 i 38 d d d e i 40 e i 35 i 42
f
i 33
i 27
f t
Sample Output
20
38
-1
-1
1
1
-1
4. Write a menu driven program to implement a Queue Q using a singly linked list. Queue is to be declared as a struct with two pointer attributes head and tail, pointing to the first node and the last node of the list respectively. Each node in the list is an object with an attribute data and a pointer attribute, next. Your program must contain the following functions: (in function prototypes, Q denotes a Queue, , k an integer (k need not be distinct) and , x a node. All operations should run in O(1) time.).
• Main() - repeatedly reads a character ‘i’, ‘d’, ‘f’ or ‘e’ from the terminal and calls the appropriate function until character ‘t’ is entered.
• Create-Node(k) - creates a new node with data value k and returns a pointer to the new node. The next field should be set as NULL.
• QueueEmpty(Q) - checks whether the Queue is empty or not.
• Enqueue(Q,x) - inserts x to the tail of Q.
• Dequeue(Q) - deletes the first node from Q (check QueueEmpty() inside this function).
Note:- For every Enqueue operation, the node x is to be created by calling Create-Node() function.
Input format:
• Each line contains a character from ‘i’, ‘d’, ‘e’ or ‘t’ followed by zero or one integer. The integer, if given, is in the range [−106,106].
• Character ‘i’ is followed by an integer separated by space. In this operation, the node with this integer as data is inserted to the tail of Q.
• Character ‘d’ is to delete the first node and the deleted node’s key is printed.
• Character ‘e’ is to check whether the Queue is empty or not.
• 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 ‘d’ delete the first node and print the deleted node’s key. If Q is empty, then print −1.
• For option ‘e’, if Q is not empty, then print 1. If Q is empty, then print −1.
Sample Input i 30
i 48d d d e i 50 e t
Sample Output
30
48
-1
-1
1
5. A palindrome is a nonempty string that reads the same forward and backward. Write a program that reads a string and checks whether the given string is palindrome or not using a Stack. Use the implementation of Stack in Question 1 with the exception that elements are of char type. Write a function IsPalindrome(str), that given a string str, returns 1 if str is a palindrome and 0 otherwise.
Input format:
• The first line of the input contains a string s.
Output format:
• If the string s is palindrome, print 1. Otherwise, print 0.
Sample Input 1: malayalam
Sample Output 1:
1
Sample Input 2: calicut
Sample Output 2:
0
6. In a computer science laboratory, all computer systems are connected to a single printer. All these systems can generate a print request for printing files. The printer can print only one file at a time. While the printer is printing a file, all other print requests need to be wait until the printer is free. Once the printer is free, the files are printed one by one in the order in which they come(i.e first in first out). The printer maintains a Queue, in which all these pending print requests are stored. For each print request, the system id, filename, numPages, and size (in KB) are stored in the queue. Use singly linked list for implementing the print queue Q. Write functions AddRequest() for adding a new request, ExtractNextRequest() for extracting the next request to be printed, and ListRequests() for listing the contents of the print queue (define the functions with appropriate arguments).
Input format:
• Each line contains a character from ‘a’, ‘e’ , ‘l’ or ‘t’ followed by the arguments required for the corresponding operation.
• Character ‘a’ is followed by two strings s1, s2, an integer n and a float value separated by space. In this operation, a new print request with the string s1 as system id, s2 as filename, n as numPages and the float value as size (in KB) is inserted to the tail of Q.
• Character ‘e’ is to delete the first print request in Q and the deleted print request’s system id is printed.
• Character ‘l’ is to list the contents of print queue 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 ‘e’ , delete the first print request in Q and print the system id of deleted print request. If Q is empty, then print −1.
• For option ‘l’ , list the contents of print queue Q. If Q is empty, then print −1.
Sample Input a f01898 abc 5 147.1 a f01897 xyz 7 190.2 e l e e
l t
Sample Output f01898 f01897 xyz 7 190.2 f01897 -1
-1