1. A stack is an Abstract Data Type (ADT) with a FIFO (first in, first out) structure
2. The following list shows a list of basic stack operations. Which one has an incorrect definition?
3. It is useful to maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the ____ of the stack, it is often just called ____
4. Which algorithm is the following code for?
5. Which algorithm is the following code for?
6. Which algorithm is the following code for?
7. Which algorithm is the following code for?
8. Take the time to read through the following interesting 'find the celebrity' question. Fill in the blanks for the missing pseudocode in step 2
In a party of N people, only one person is known to everyone.
Such a person may be present in the party, and if so, (s)he doesn’t know anyone in the party.
We can only ask questions like “does A know B? “.
Find the stranger (celebrity) in minimum number of questions.
This can be solved using a stack implementation.
The graph construction takes O(N2) time, it is similar to brute force search.
In case of recursion, we reduce the problem instance by not more than one,
and also combine step may examine M-1 persons (M – instance size).
We have following observation based on elimination technique (Refer Polya’s How to Solve It book).
If A knows B, then A can’t be celebrity. Discard A, and B may be celebrity.
If A doesn’t know B, then B can’t be celebrity. Discard B, and A may be celebrity.
Repeat above two steps till we left with only one person.
Ensure the remained person is celebrity. (Why do we need this step?)
We can use stack to verity celebrity.
PSEUDOCODE
===========
1 - Push all the celebrities into a stack.
2 - Pop off top two persons from the stack, and _________________________________________________
3 - Push the remained person onto stack.
4 - Repeat step 2 and 3 until only one person remains in the stack.
5 - Check the remained person in stack doesn’t have acquaintance with anyone else.
put both people back on to the stack based on if the return status of HaveAquaintance(A,B) returns '1'
put both people back on to the stack based on if the return status of HaveAquaintance(A,B) returns '0'
discard one person based on return status of HaveAcquaintance(A, B).
discard both people from the stack based on return status of CallStack(B)
9. Look at the code for the following class based stack implementation (Python). What will the output be for the following two commands: print(myStack.size()) and
print(myStack.pop())
10. In the following code that reverses a string using a stack, what is happening here: for i in range(0,n,1): (next line) string+=pop(stack)