CS2094D-ASSIGNMENT 0 Solveed

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