# 03 - Stack Algorithms

1. A stack is an Abstract Data Type (ADT) with a FIFO (first in, first out) structure

TRUE

FALSE

2. The following list shows a list of basic stack operations. Which one has an incorrect definition?
```push() ? Pushing (storing) an element on the stack.
pop() ? Removing (accessing) an element from the stack.
peek() ? Remove the top most element in the stack and replace it with the last element
isFull() ? check if stack is full.
isEmpty() ? check if stack is empty.```

isFull() should be: check to see if the stack has a full stack + n elements, n being the length of the stack -1)

pop' should be: accessing an element from the top of the stack without removing it

push' should be: deleting an element that is pushed to the top of the stack

peek' should be: get the top data element of the stack, without removing it.

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 ____

right

top

bottom

left

4. Which algorithm is the following code for?
```begin procedure

if top equals to MAXSIZE
return true
else
return false
endif

end procedure```

isempty()

isfull()

push

pop

5. Which algorithm is the following code for?
```begin procedure : stack, data

if stack is full
return null
endif

top ? top + 1
stack[top] ? data

end procedure```

isempty()

push

pop

isfull()

6. Which algorithm is the following code for?
```begin procedure

if top less than 1
return true
else
return false
endif

end procedure```

push

isempty()

isfull()

pop

7. Which algorithm is the following code for?
```begin procedure : stack

if stack is empty
return null
endif

data ? stack[top]
top ? top - 1
return data

end procedure```

push

pop

isfull()

isempty()

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())
```class Stack:

#Constructor creates a list
def __init__(self):
self.stack = list()

def push(self,data):
#Checking to avoid duplicate entries
if data not in self.stack:
self.stack.append(data)
return True
return False

#Removing last element from the stack
def pop(self):
if len(self.stack)<=0:
return ("Stack Empty!")
return self.stack.pop()

#Getting the size of the stack
def size(self):
return len(self.stack)

myStack = Stack()
print(myStack.push(5)) #prints True
print(myStack.push(6)) #prints True
print(myStack.push(9)) #prints True
print(myStack.push(5)) #prints False since 5 is there
print(myStack.push(3)) #prints True
print(myStack.size())  #prints 4
print(myStack.pop())   #prints 3
print(myStack.pop())   #prints 9
print(myStack.pop())   #prints 6
print(myStack.pop())   #prints 5```

Error - in both cases. Nothing will be printed

print(myStack.size()) #prints 5 and print(myStack.pop()) #prints 5

print(myStack.size()) #prints 3 and print(myStack.pop()) #prints 4

print(myStack.size()) #prints 0 and print(myStack.pop()) #prints Stack Empty!

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)
```#A python program that uses a stack to reverse a string

# Here we initialise the size of the stack to 0
def createStack():
stack=[]
return stack

# Function to determine the size of the stack
def size(stack):
return len(stack)

# Stack is empty if the size is 0
def isEmpty(stack):
if size(stack) == 0:
return true

# Function to add an item to stack .
# It increases size by 1
def push(stack,item):
stack.append(item)

#Function to remove an item from stack.
# It decreases size by 1
def pop(stack):
if isEmpty(stack): return
return stack.pop()

# A stack based function to reverse a string
def reverse(string):
n = len(string)

# Create a empty stack
stack = createStack()

# Push all characters of string to stack
for i in range(0,n,1):
push(stack,string[i])

# Making the string empty since all
#characters are saved in stack
string=""

# WHAT IS HAPPENING HERE?
for i in range(0,n,1):
string+=pop(stack)

return string

# Driver program to test above functions
string=input("Enter string to reverse:")
string = reverse(string)
print("Reversed string is " + string) ```

We are 'popping' all the characters of the string and putting them back into the string

We are deleting the new list by 'pushing' the whole list onto another stack of lists, and then 'popping' each letter off the stack of lists

We are deleting the original string and 'popping' the characters from the new string into a second list

We are 'pushing' all the characters of the string onto a stack and then 'popping' them back out