[SOLVED] CS2094D Assignment 0

1

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 i8 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 [−106,106].

   • 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.

2

• 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 i8 i 10 d
i 12 d
d
d
e
i 18 f i1 i5 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.

3

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

4