Implementing a Stack As an Array | Learn How to Program Using Any Web Browser

In the beginning of this chapter I defined an array as a series of variables with the same name such that individual values in the series are accessed using an index. This means that an array provides a structure for random access to stored values: It’s as easy to retrieve a value stored anywhere in the array as it is to retrieve a value stored anywhere else. All you need is the index.

Not every programming problem calls for a data structure that provides random access. For example, suppose you have no idea how many items you’ll need to store. But you’d like the data structure you use for this task to have the property that each new item added to it becomes the next item accessed from it. The data structure I’ve just described is called a stack.

By its very nature, a stack isn’t a random access structure in the way that an array is. You only have access to the top, or last in, item in a stack at any given time. This means that a stack functions in a first in, last out (or FILO) fashion. The first item in is the last item out.

Note

You may have heard of another data structure related to the stack, namely the queue. A queue works like a stack except that it’s first in, first out (or FIFO). Think of people waiting in an orderly line (or queue) and then boarding a bus to get a mental picture of how this data structure works.

In stack lingo, to push a stack means to add a new item to the “top” of the stack. To pop a stack means to remove the item at the “top” of the stack. When you pop the stack to remove the top item, at the same time you’re retrieving the value of the item.

It’s easy to make a JavaScript array behave like a stack using the Array object’s push and pop methods.

We’ll first walk through a simple example of using an array as a stack so that you get the hang of it. Then I’ll show you a more general program using a stack for your enjoyment.

The object of the simple stack example is just to give you a feeling for stacks as a data structure and to demonstrate that the push and pop methods work as advertised.

First, within a <SCRIPT> tag in the body of an HTML document, declare a new array named stack:

 var stack = new Array();

Next, push two values onto the stack (the text strings Me and Two):

 stack.push("Me", "Two");

Now, iterate through the stack array to display its contents, with a line break placed between each item:

 for (var i = 0; i < stack.length; i++){     document.write(stack[i] + "<br>");  }

If you open the HTML page as it stands so far in a Web browser, it should display the strings Me and Two on separate lines, as you can see at the top of Figure 6-5.

click to expand
Figure 6-5: The contents of the stack (the top two items) are displayed.

Next, pop an item off the stack and display it:

 document.write (stack.pop() + "<br>");

The item popped should be the most recent item added to the stack, also called the “top” item, which is the text string Two, as you can see on the third line of Figure 6-5.

The only item left on the stack should be the text string Me. But let’s prove it by iterating through the stack array again and displaying the contents:

 for (var i = 0; i < stack.length; i++){     document.write(stack[i] + "<br>");  }

This time only one item, Me, is displayed, as you can see in the fourth and final line of Figure 6-5.

Listing 6-4 shows the complete code for the simple stack example.

Listing 6.4: Simple Stack Example

 <HTML> <HEAD> <TITLE>  Simple Stack Example  </TITLE> </HEAD> <BODY> <H1> <SCRIPT>  var stack = new Array();  stack.push("Me", "Two");  for (var i = 0; i < stack.length; i++){     document.write(stack[i] + "<br>");  }  document.write (stack.pop() + "<br>");  for (var i = 0; i < stack.length; i++){     document.write(stack[i] + "<br>");  }  </SCRIPT> </H1> </BODY> </HTML>

Seeing a More General Stack in Action

Now that you have the gist of working with stacks, let’s see how a more general stack application stacks up!

Here’s how the general stack application will work: The user will be able to enter a text item and click the Push button to push an item onto the stack. When the user clicks the Pop button, the last-in item is popped off the stack and displayed in a text box. In addition, whenever the Push or Pop button is clicked—which means anytime the stack is changed—the current items on the stack are displayed in an HTML select list.

Figure 6-6 shows the user interface in a Web browser.

click to expand
Figure 6-6: The HTML page lets you push a text item onto the stack, displays the current state of the stack, and lets you pop the stack.

Using the HTML Form Tags

In case you’re wondering, and to get it out of the way, let’s look at HTML form tags that create the user interface shown in Figure 6-6. Listing 6-5 shows the HTML for the application.

Listing 6.5: The HTML for the Stack Application

 <HTML> <HEAD> <TITLE>Stacking up!</TITLE> <SCRIPT> </SCRIPT> </HEAD> <BODY> <FORM> <INPUT type=text name=txtPush> <INPUT type=button value="Push"> <SELECT name="theList" size=12> <OPTION>Displays the current state of the stack!  </SELECT> <INPUT type=text name=txtPop size=25> <INPUT type=button value="Pop"> </FORM> </BODY> </HTML>

There’s no program code in the HTML page shown in Listing 6-5. When code is added to the HTML page, it’ll mostly go in the <HEAD> section of the HTML (following the <SCRIPT> tag).

The <FORM> section of the HTML shown in Listing 6-5 creates a text box named txtPush, a Push button, a select list named theList, a text box named txtPop, and a Pop button. You should know that the options array of an HTML select list can be used to populate (and retrieve) the option items associated with the select list. In static HTML, each of these option items can be identified by its <OPTION> tag.

With the HTML out of the way, let’s move on to pushing an item onto the stack. But first, we need to create the stack.

Pushing the Stack

In the <HEAD> section of the HTML document, create a new Array object named stack:

 var stack = new Array();

Tip

Placing the Array constructor first in the <HEAD> section of the HTML page makes the stack array available to any code that comes after it, namely all the code in the HTML page.

Next, write a function, pushStack, that accepts input and pushes it onto the stack using the push method:

 function pushStack(newVal) {     stack.push(newVal);  }

Finally, in the HTML form, add an onClick event to the Push button that calls the pushStack function, passing the function the value of the txtPush text box:

 <INPUT type=button value="Push" onClick='pushStack(txtPush.value);'>

Tip

This line of HTML and code replaces the original line, < INPUT type=button value="Push" > .

Now, if you enter a text item in the txtPush text box and click Push, as shown in Figure 6-7, the item will be pushed onto the stack.

click to expand
Figure 6-7: Enter an item in the leftmost text box and click Push to push it onto the stack.

Displaying the Contents of the Stack

Next, let’s write a function, showStack, that displays the contents of the stack in an HTML select list at any given time. Once again, the showStack function should be placed in the <HEAD> section of the document.

Here’s the declaration for the showStack function, which assumes that a HTML select object will be passed to it as an argument:

 function showStack(theSelect){  }

Within the function, the first thing to do is to clear the list of options associated with the select list. To do this, set the length property of the select list’s options array to zero:

 theSelect.options.length = 0;

Next, create a loop that iterates through the stack array:

 for (var i = 0; i < stack.length; i++){  }

For each item in the stack array, use the new operator to construct a new Option item named theOption that has the value of the stack array item as text:

 var theOption = new Option(stack[i]);

Finally, assign theOption as the value of a new item in the select list’s options array. To do this, use as the index value for the options array its length property (theSelect.options.length), which will always be one greater than the highest index value for the array. Here’s the statement:

 theSelect.options[theSelect.options.length] = theOption;

I know this seems a little tricky, but it’s well worth your while to study it until you get the hang of it. If you understand the showStack function, shown in Listing 6-6, you’ll really understand how to work with arrays!

Listing 6.6: Showing the Stack

 function showStack(theSelect){     theSelect.options.length = 0;     for (var i = 0; i < stack.length; i++){        var theOption = new Option(stack[i]);        theSelect.options[theSelect.options.length] = theOption;     }  }

Oops! I almost forgot. If we’re going to show the contents of the stack every time an item is pushed on it, we need to add code calling the showStack function when a new item is pushed on the stack. This goes in the onClick event of the Push button. Here’s the modified Push button onClick event code, which resets the value of the txtPush text box and passes to the showStack function the select list object, using its name theList:

 <INPUT type=button value="Push" onClick='pushStack(txtPush.value);     txtPush.value=""; showStack(theList);'>

If you open the HTML page as it now stands and push successive items onto the stack, they’ll be displayed in the select list, as shown in Figure 6-8.

click to expand
Figure 6-8: The contents of the stack are displayed in the select list.

Popping the Stack

Never pop a stack in haste or anger, only with due deliberation. That said, to pop the stack, we need to add a function, popStack, to the <HEAD> section of the HTML page.

The code for the popStack function assigns to a variable named popVal the return value of the pop method when the function is applied to the stack array.

As you may recall, calling the pop method of an array both pops the stack and returns the popped value.

If popVal is undefined, the text string value Nothing left on the stack! is returned. Otherwise, if popVal has been assigned a value, the value is returned.

Listing 6-7 shows the popStack function.

Listing 6.7: Popping the Stack

 function popStack() {     var popVal = stack.pop();     if (popVal == undefined)        return "Nothing left on the stack!";     else     return popVal;  }

To keep the display of the stack synchronized when items are being popped, the onClick event handler for the Pop button needs to both assign the return value from the popStack function to the txtPop text box and also to call the showStack function:

 <INPUT type=button value="Pop" onClick="txtPop.value = popStack();     showStack(theList);">

Tip

These lines appear in the HTML form and replace the original line

 <INPUT type=button value="Pop">.

The stack program is now complete (and you can find the complete code in Listing 6-8).

Listing 6.8: Pushing, Popping, and Displaying the Contents of a Stack

 <HTML> <HEAD> <TITLE>Stacking up!</TITLE> <SCRIPT>  var stack = new Array();  function pushStack(newVal) {     stack.push(newVal);  }  function popStack() {     var popVal = stack.pop();     if (popVal == undefined)        return "Nothing left on the stack!";     else     return popVal;  }  function showStack(theSelect){     theSelect.options.length = 0;     for (var i = 0; i < stack.length; i++){        var theOption = new Option(stack[i]);        theSelect.options[theSelect.options.length] = theOption;     }  }  </SCRIPT> </HEAD> <BODY> <FORM> <INPUT type=text name=txtPush> <INPUT type=button value="Push" onClick='pushStack(txtPush.value);     txtPush.value=""; showStack(theList);'> <SELECT name="theList" size=12> <OPTION>Displays the current state of the stack!  </SELECT> <INPUT type=text name=txtPop size=25> <INPUT type=button value="Pop" onClick="txtPop.value = popStack();     showStack(theList);"> </FORM> </BODY> </HTML>

If you open the HTML page in a Web browser, push a bunch of items onto the stack, and then click Pop, then the most recently pushed item will be popped off the stack (see Figure 6-9).

click to expand
Figure 6-9: When the user pops an item from the stack by clicking the Pop button, the popped item is displayed in the rightmost text box.

If you keep on popping until the stack is gone, then the txtPop text box will tell you that there’s nothing left on the stack (see Figure 6-10).

click to expand
Figure 6-10: If you attempt to pop a stack with nothing on it, an appropriate message is displayed.