Flipping Stacks

We are now going to look at how to flip a stack. As was discussed previously, a stack is an ideal method for holding items in a queue such as an incoming call center.

Let’s say the following calls come into a call center. They are time-stamped for reference.

Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22
Call 1 – (972)828-1847 – 2017-02-13 / 08:01:13

In this case, the call that has been placed on hold the longest is “Call 1”, which came in at 8:01:13. However, recall that in a stack I can only interact with the item on the TOP of the stack. In this case, that is “Call 5”.

So, we are going to create a system that “flips” this stack over, pulls the new top item off and then returns to stack to its original order so additional calls can go in the place they should.

So, assuming that we have a stack already created for the numbers, we will need to create an empty temporary stack to hold the items. As we move the items over, the temporary stack will look like the following:

Call 1 – (972)828-1847 – 2017-02-13 / 08:01:13
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57

As you can now see, “Call 1” is at the top of the stack and could be routed to the next available individual. However, if another new call were to come in, the stack would look like the following:

Call 6 – (512)231-1933 – 2017-02-13 / 08:03:19
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57

To avoid our call queue getting mixed-up, immediately following the retrieval of the top item on the stack, we need to move the items from the temporary stack back to the original stack as follows:

Call 5 – (469)382-1285 – 2017-02-13 / 08:02:57
Call 4 – (682)552-3948 – 2017-02-13 / 08:02:45
Call 3 – (214)233-0495 – 2017-02-13 / 08:01:55
Call 2 – (817)927-3849 – 2017-02-13 / 08:01:22

Now, when “Call 6” comes in, it will go where it is supposed to go (following “Call 5”).

Let’s analyze the code for this problem.

//Program Name: Flipped Stacks
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2017
import java.util.*;
public class flippedstacks {
    public static void main(String args[]){
        int count, myStackSize, myTempStackSize;
        Stack myStack = new Stack();
        for (count = 1; count <=10; count++){
            myStack.push(count);
        }
        myStackSize = myStack.size();
        Stack myTempStack = new Stack();
        for (count = 1; count <=myStackSize; count++){
            myTempStack.push(myStack.pop());
        }
        System.out.println("Current Caller is " + myTempStack.pop());
        myTempStackSize = myTempStack.size();
        for (count = 1; count <=myTempStackSize; count++){
            myStack.push(myTempStack.pop());
        }
    }
}

Lines 1 – 4 are the general header information. Lines 5 – 7 are the imports and creation of the class and main object.

Line 8 creates 3 uninitialized integer variables: count, myStackSize, and myTempStackSize.

Line 9 creates a new empty stack named “myStack”.

Lines 10 – 12 push content into the “myStack” stack. It pushes numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, & 10 into the stack.

Line 13 initializes the value of the myStackSize variable as the size of “myStack” using the size function of stacks.

Line 14 is like line 9, but it creates an empty stack named “myTempStack”. This will be the stack that temporarily holds our stack of information so we can get the first record.

Lines 15 – 17 push the content into the “myTempStack” stack by popping each record in the “myStack” stack. The for loop know how many times to do this by using the myStackSize variable that was declared on line 8 and initialized on line 13.

Line 18 displays which caller is the current caller by popping it from the top of the “myTempStack” stack.

Line 19 is like line 13 in that it initializes the value of the myTempStackSize variable as the size of “myTempStack” using the size function of stacks.

Line 19 is also the beginning of the process of reverting the stack back to its original order with the first (oldest) entry removed.

Lines 20 – 22 are similar to lines 15 – 17 but the reverse process. They push content into the “myStack” stack by popping each record in the “myTempStack” stack. The for loop knows how many times to do this by using the myTempStackSize variable that was declared on line 8 and initialized on line 19.

Line 24 & 25 close out lines 7 & 6 respectively.

Tangible Introduction to Stacks

After we spend a day getting back into a coding mindset in Computer Science, we’ll be starting a new unit over data structures. The first structure we’ll be looking at are stacks.

I’m reflecting on something that Dr. Sabrina McCullough used to tell us when she was leading our elementary math training sessions about the importance of introducing a new skill or concept using concrete / real-world / tangible examples.

I applied this when I introduced iterative structures such as for loops, while loops, and do while loops. My students can tell you that I had them walking in circles for a while, but they understood the difference between the types of loops before we ever coded anything!

To start, I am going to have the students tear a sheet of paper into 8 semi-equal pieces. They are going to answer the following questions in this order recording an answer on each piece of paper and stacking them one on the other face-down as they record their answers.

  1. What is your favorite breakfast food?
  2. What is your favorite junk food?
  3. What is your favorite school holiday?
  4. How old are you?
  5. What grade are you in?
  6. What month is your birthday?
  7. What year is it now?
  8. What is your favorite color?

Once the last question is answered, I will have them look at their small stack and ask them the following questions:

  1. As you added a new item to your stack, where did you put it? (top, bottom, or middle)
  2. If you needed to search through your stack for something, where would you start? (top, bottom, or middle)

Next, I will give each student a stack of 8 index cards. The cards will be randomly numbered with the exception of the 3rd card in each stack, which will have the number 25.

Before the students are given their cards, they will be given the rules:

  • Do not do anything with the cards until you are told to do so.
  • You can only have one card face-up at a time.
  • You can only take from the top of the stack.
  • If you perform any sort of calculation beyond a search on a card, that card is removed from the stack and “discarded”.

I will then walk them through a series of exercises with their stack of cards:

  1. Write down the cards in the stack in order.
    Return stack to original.
  2. Search for the card with 25. How many cards were above it?
    Return stack to original.
  3. Take top card and multiply it by 10.
    Discard top card from stack.
  4. Search for the card with 25. How many cards were above it?
    Return stack.
  5. Take top card and multiply by 5.
    Discard top card from stack.
  6. Search for the card with 25. How many cards were above it?
    Return stack.
  7. Write down the cards in the stack in order.
    Return stack.

Once this information has been recorded, the following questions will be asked:

  1. How many cards can we interact with at a time?
    (Answer = 1)
  2. What was the pattern each time you searched for the card with 25 on it?
    (Answer = it was getting closer to the top)
  3. Can we do any calculations with cards below the current top of the stack?
    (Answer = No)
  4. When I place an item on a stack, where does it go?
    (Answer = On the top)
  5. When I take an item off of a stack, where does it come from?
    (Answer = On the top)
  6. How does the term LIFO (Last In – First Out) apply to a stack?
    (Answer = The last item added to the stack is the first item to be removed)

Once we go through this, we’ll then move into basic programming that was discussed in the post http://funmultiplies.com/starting-with-stacks

Hopefully, giving them a tangible example of how a stack works will assist them with the abstract reasoning of working with stacks as a Computer Science data structure.

Starting with Stacks

Our next unit in Computer Science is working with data structures. So far, all we have done is take keyboard input or hard-coded input and done immediate calculations with it. We’ve not actually stored or manipulated any data.

We’re going to start with stacks as those are arguably the easiest data structure to understand.

//Program Name: Starting with Stacks
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2017

import java.io.*;
import java.util.*;

public class stacks {
    public static void main(String args[]){
        Stack myStack = new Stack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        myStack.push(6);
        myStack.push(7);
        myStack.push(8);
        myStack.push(9);
        myStack.push(0);
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("First Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
    }
}

As you can see here, we created a new stack on line 11 named myStack and then pushed the integer 1, 2, 3, 4, 5, 6, 7, 8, 9, & 0 into that stack on lines 12 through 21.

Line 22 displays the content of the stack, which at this moment is the following:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

Line 23 uses the search method to display the current position of a searched item, in this case, the integer “1”. Remember, the search method of a stack returns the position relative to the top of the stack. At this point in the application, the integer “1” is located at position 10.

At Line 25, we use the pop method to return the value at the top of the stack. Since this object was handled, it has now been removed from the stack.

Line 26 is identical to line 22 in that it displays the content of the stack at that moment. However, since the top item has been removed from the stack, it now looks like the following:

[1,2,3,4,5,6,7,8,9]

Line 27 is identical to line 23 and provides the position of the searched item, in this case the integer “1” in relation to the top of the stack. Since the top item has been removed, the search item is now one position closer to the top of the stack.

Lines 29-31, 33-35, 37-39, and 41-43 all perform the same functions as lines 25-27. Each time, the top item from the stack is removed, the current stack is displayed, and the position of the searched item in relation to the top of the stack is provided.

Interactive Stacks

Additionally, we will look at adding interactivity to the process as opposed to hard-coding the data.

//Program Name: Starting with Stacks
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2017

import java.io.*;
import java.util.*;

public class stacks {
    public static void main(String args[]){
        Stack myStack = new Stack();
        Scanner myInput = new Scanner(System.in);
        System.out.print("Enter 10 Integers Separated by a Space and Press Enter: ");
        for(int myCounter=1; myCounter <11; myCounter++){
            myStack.push(myInput.nextInt());
        }
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("First Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        for(int myPopCounter=1; myPopCounter < 5; myPopCounter++){
            System.out.println("Next Removed Object is: " + myStack.pop());
            System.out.println("Current Stack: " + myStack);
            System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
            System.out.println("");
        }
    }
}

Here, you can see that we’ve streamlined the code considerably. What was lines 25 through 43 is now lines 24 through 29! We utilized a for loop to execute the segment of code through 5 iterations.

In addition, the keyboard inputs are being processed through a for loop located at lines 14-16. This loop runs 10 iterations of the nextInt() method of the scanner object myInput and using the push method of the stack object myStack places them into the stack.

This code runs identical to the code above but the user can enter their own data as opposed to having to utilize the hard-coded data.

Items to Discuss

Next class, we’ll be discussing how the search handles multiple occurrences of the same item. For example, let’s say that a user entered their data to create the following stack:

[1,2,3,4,5,1,2,3,4,5]

In this case, if we used the search method to locate the integer “1”, which integer “1” would be displayed?

We will also analyze the advantages and the disadvantages of stacks as a data structure. This will take us to the next data structure, 1-dimensional arrays.