Question

In each plastic container of Pez candy, the colors are stored in random order. Your little brother likes only the yellow ones, so he painstakingly takes out all the candies, one by one, eats the yellow ones, and keeps the others in order, so that he can return them to the container in exactly the same order as before – minus the yellow candies, of course. Write a main function in a full C++ program to simulate this process. You may use any of the stack operations defined in the Stack ADT. Then pick a a linked list-based StackType ADT to include in your program.

Answer 1

Below algorithm solves the given problem:

Time Complexity of below code is O(n).
This algorithm preserves the order of candies using stack.

Declare a stack st and initialize it.
Lets say container c is the stack of candies.

//loop until the container isn't empty
while(!c.isEmpty()) {
   candy = c.pop();
   if (candy == 'yellow') {
       //eat candy
   }
   else {
       st.push(candy);
   }
}
//All yellow candies are now eaten up, so we'll add the remaining back to container
while(!st.isEmpty()) {
   candy = st.pop();
   c.push(candy);
}
return c;