Preview

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.

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

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

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

  pop' should be: accessing an element from the top 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 ____

  top

  bottom

  right

  left

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

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

  pop

  isfull()

  isempty()

  push

 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

  isfull()

  isempty()

  pop

  push

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

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

  isempty()

  isfull()

  push

  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

  isfull()

  isempty()

  push

  pop

 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()

    #Adding elements to stack
    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 0 and print(myStack.pop()) #prints Stack Empty!

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

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

 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 deleting the original string and 'popping' the characters from the new string into a second list

  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 'pushing' all the characters of the string onto a stack and then 'popping' them back out

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