Using Stacks to Manage the Handshake
The subroutines you wrote in the last few blog posts (Small Basic - The Triangle Area Calculator and Small Basic - Nesting Subroutines ) used a handful of variables to pass information back to the main program. When your programs get larger and your subroutines become more complex, you might need a lot of variables to communicate with your subroutines. Stacks help you reduce the number of variables in your programs!
The concept of a stack isn’t new to you. You’ve seen a stack of trays in a cafeteria or a stack of books in a library (or a stack of clothes on your floor). But to explain it, we’ll start with the stack of boxes in the Figure (a), the one with two boxes. This stack gives you two operations: push and pop.Pushing a new item on the stack puts it at the top of the stack, like in the Figure (b and c). Pop an item off the stack to remove it from the top of the stack, like in the Figure (d and e). Look how the top item of the stack is the one that’s added last. Because a pop operation removes the top item, a stack’s also known as a last in, first out data structure.
The Small Basic library provides the Stack object to help you manage stacks in your programs. The Stack object’s three methods are explained in the Table.
Table: The methods of the Stack object
Pushes a value to the top of a stack.
Pops and removes the top value from a stack.
Returns the count of items in a stack.
You can create as many stacks as you want. You give each stack a name (a string identifier), like "books", "Duplos", "myStack", "Jenga", or even "x". All the stacks you create are managed by the Stack object. You tell the Stack object which stack you want to work on by passing its name to one of the three methods in the Table.
To show you how to use stacks to pass parameters to subroutines (and retrieve results from them), write the program in the Listing. This program finds the average of three numbers entered by your user. Save your file as "Average".
Listing 9-23: Using stacks to find the average
1 ' Average.sb
2 ' Shows how to use stacks to communicate with subroutines
4 TextWindow.WriteLine("Enter three numbers: ")
5 Stack.PushValue("numStack", TextWindow.ReadNumber()) ' Pushes 1st
6 Stack.PushValue("numStack", TextWindow.ReadNumber()) ' Pushes 2nd
7 Stack.PushValue("numStack", TextWindow.ReadNumber()) ' Pushes 3rd
9 CalculateAverage() ' Calls the subroutine to calculate the avearge
11 avg = Stack.PopValue("numStack") ' Pops the result from the stack
12 TextWindow.WriteLine("Average = " + avg) ' Displays the result
14 Sub CalculateAverage
15 sum = Stack.PopValue("numStack") ' Gets the top (3rd) value
16 sum = sum + Stack.PopValue("numStack") ' Adds the 2nd value
17 sum = sum + Stack.PopValue("numStack") ' Adds the 1st value
18 Stack.PushValue("numStack", (sum / 3) ) ' Pushes the average onto the stack
Enter three numbers:
Average = 29
Here’s how this program works. The program starts by asking your user to enter three numbers (Line 4). It then reads the three numbers and pushes them, one by one, on a stack named numStack (Lines 5-7). Let’s take a closer look at how you called the PushValue() method:
The first argument is the stack’s name. The second argument is the return value from the ReadNumber() method. Small Basic waits for your user to enter a number and, when she presses Enter, it passes that number as the second argument to PushValue().You could also rewrite the line like this:
ans = TextWindow.ReadNumber()
The program then calls the CalculateAverage() subroutine (Line 9). The only thing this subroutine needs is the name of your stack.
The subroutine starts by popping the top value from the stack and saving that number in a variable named sum (Line 15). The variable sum is used as an accumulator. The subroutine then pops the second number from the stack and adds its value to the sum variable (Line 16). It then pops the third number from the stack and adds its value to sum (Line 17). At this point, the stack is empty because all three elements have been popped off. At Line 18, the subroutine finds the average and pushes it on the stack before returning to the caller.
When the main program continues at Line 11, it pops the answer from the stack and saves it in a variable named avg. After that, it shows your user the answer (Line 12), and the program ends.
If you implement this program without using stacks, you’d have to use three variables (such as num1, num2, and num3) to save the three numbers that your user enters. Using a stack lets you pass all the values using a single object. (Imagine 80 user inputs, and you’ll be glad you got to know how to use stacks!)
You can do a lot with stacks in computer programming!
TIP: The CalculateAverage() subroutine doesn’t need to know that the stack has three elements. It can use the GetCount() method to find out how many numbers are there and then use a For loop, which you can learn about at Small Basic Getting Started Guide: Chapter 5: Loops and Small Basic for Little Kids Series #02 – Loop), to accumulate the running sum. This way, you end up with a general averaging subroutine that works on any number of inputs.
Write a program that finds the distance between two points, P1(x1,y1) and P2(x2,y2). Have the program prompt your user for x- and y-coordinates of the two points, and then use a stack to pass the coordinates to the calculation routine. Have the calculation routine return the result in the same stack.
Leave a comment if you have any questions!
Learn more about Small Basic: http://blogs.msdn.com/b/smallbasic/
Small and Basically yours,
- Ninja Ed & Majed Marji