Description
QUESTIONS
1. Write a program to implement a Stack S using an array A of size n. The stack must support the functions: isEmpty, Push, Pop and isFull. Modify the isFull and/or PUSH functions to support the following functionality: If S is full when the PUSH function is called, allocate a new array B of size 2n, copy all the elements of A into B, make A point to the array B, deallocate the old array A, and finally perform the PUSH operation on the new array A.
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’, 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 deleted element from 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’, if A is full, then print 1.
• For option ‘d’, print the deleted element. If A is empty, then print −1.
Sample Input :
4 d i 8 i 10 i 11 i 12 i 13 d d
t
Sample Output:
-1
1
13
12
2. Write a program to implement a Queue Q using an array A of size n. The queue must support the functions: isEmpty, enQueue, deQueue and isFull.
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’, ‘f’, or ‘t’ followed by zero or one integer. The integer, if given, is in the range [
• Character ‘i’ is followed by an integer separated by a space. In this operation, the integer is inserted to the tail of Q. If the Q is full, then print 1.
• Character ‘d’ is to delete and print the first element of Q.
• Character ‘e’ is to check whether the Q is empty or not.
• Character ‘f’ is to check whether the Q is full 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 Q is empty, then print 1.
• For option ‘e’, if Q is not empty, then print −1. 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.
Sample Input :
5 i 8 i 10 d i 12 d d d e i 18
f
i 1 i 5 e t
Sample Output:
8
10
12
1
1
-1 1
-1
3. Assume that you are given the head pointer of an unsorted singly linked list L that contains n nodes, for some unknown integer n. Note that n is not part of the input. Write a program that implements the following function:
kLast: Takes as input the head pointer of a singly linked list L and an integer k, such that k ≤ n, where n is the length of L and returns the (n − k + 1)th node in the list.
(Hint:You should create the Singly linked list L with the elements that is read from the console.) Input format:
• The input should be read from the console.
• The first line contains the elements of L which are separated by a space.
• Second line is the integer k.
Output format:
• If k ≤ n, print the (n − k + 1)th node in the list. Otherwise print -1.
Sample Input:
12 35 50 59 60 73 90
3
Sample Output:
60
Sample Input:
12 35 50 59 60 73 90
10
Sample Output:
-1
