Stacks

Part I. Information Structures

On pages 228-229 of The Art of Computer Programming, Volume 1, 2nd edition (Addison Wesley, 1973), Donald Knuth introduces us to information structures.

Computer programs usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values; they involve important structural relationships between the data elements.

In its simplest form, a table might be a linear list of elements, when its relevant structural properties might include the answers to such questions as: which element is the first in the list? which is the last? which elements precede and follow a given one? how many elements are there in the list? There is a lot to be said about structures even in this apparently simple case (see Section 2.2).

In more complicated situations, the table might be a two-dimensional array (i.e., a matrix or grid, having both a row and a column structure), or it might be an n-dimensional array for higher values of n; it might be a tree structure, representing hierarchical or branching relationships; or it might be a complex multilinked structure with a great many interconnections, such as we might find in a human brain.

In order to use a computer properly, it is important to acquire a good understanding of the structural relationships present within data, and of the techniques for representing and manipulating such structure within a computer.

The present chapter summarizes the most important facts about information structures: the static and dynamic properties of different kinds of structure; means for storage allocation and representation of structured data; and efficient algorithms for creating, altering, accessing, and destroying structural information. In the course of this study, we will also work out several important examples, which illustrate the application of these methods to a wide variety of problems. The examples include topological sorting, polynomial arithmetic, discrete system simulation, operations on sparce matricies, algebraic formula manipulation, and applications to the writing of compilers and operating systems. Our concern will be almost entirely with structure as represented inside a computer; the conversion from external to internal representations is the subject of Chapters 9 and 10.

Much of the material we will discuss is often called “List processing,” since a number of programming systems (e.g. IPL-V, LISP, and SLIP) have been designed to facilitate working with certain general kinds of structures called Lists. (When the word “list” is capitalized in this chapter, it is being used in a technical sense to denote a particular type of structure that is studied in detail in Section 2.3.5.) Although List processing systems are useful in a large number of situations, they impose constraints on the programmer that are often unnecessary; it is usually better to use the methods of this chapter directly in one’s own programs, tailoring the data format and the processing algorithms to the particular application. Too many people unfortunately still feel that List processing techniques are quite complicated (so that it is necessary to use someone else’s carefully written interpretive system or set of subroutines), and that List processing must be done only in a certain fixed way. We will see that there is nothing magic, mysterious, or difficult about the methods for dealing with complex structures; these techniques are an important part of every programmer’s repertoire, and he can use them easily whether he is writing a program in assembly language or in a compiler language like FORTRAN or ALGOL.

We will illustrate methods of dealing with information structures in terms of the MIX computer. A reader who does not care to look through detailed MIX programs should at least study the ways in which structural information is represented in MIX’s memory.

It is important to define at this point several terms and notations which we will be using frequently from now on. The information table consists of a set of nodes (called “records,” “entities,” or “beads” by some authors); we will occasionally say “item” or “element” instead of “node” Each node consists of one or more consecutive words of the computer memory, divided into named parts called fields. In the simplest case, a node is just one word of memory, and it has just one field comprising that whole word.

Part II. Linear Lists: Stacks, Queues, and Deques

After explaining linear lists, Knuth defines stacks, queues, and deques on pages 234 and 235 (ibid.).
A linear list is a set of n ≥ 0 nodes X[1], X[2], . . . , X[n] whose structural properties essentially involve only the linear (one-dimensional) relative position of the nodes: the facts that, if n ≥ 0, X[1] is the first node; when 1 < k < n the kth node X[k] is prceded by X[k − 1] and followd by X[k + 1]; and X[n] is the last node.

The operations we might want to perform on linear lists include, for example, the following.

  1. Gain access to the kth node of the list to examine and/or to change the elements of its fields.
  2. Insert a new node just before the kth node.
  3. Delete the kth node.
  4. Combine two or more linear lists into a single list.
  5. Split a linear list into two or more lists.
  6. Make a copy of a linear list.
  7. Determine the number of nodes in a list.
  8. Sort the nodes of the list into ascending order based on certain fields of the nodes.
  9. Search the list for the occurrence of a node with a particular value in some field.

In operations (i), (ii), and (iii) the special cases of k − 1 and k − n are of principal importance since the first and last items of a linear list may be easier to get at than a general element is. We will not discuss operations (viii) and (ix) in t his chapter, since these topics are the subjects of Chapters 5 and 6 respectively.

A computer application rarely calls for all nine of the above operations in their full generality, so we find there are many ways to represent linear lists depending on the class of operations which are to be done most frequently. It is difficult to design a single representation method for linear lists in which all of the operations are efficient; for example, the ability to gain access to the kth node of a long list for random k is comparatively hard to do if at the same time we are inserting and deleting items in the middle of the list. Therefore, we distinguish between types of linear lists depending on the principal operations to be performed, just as we have noted that computer memories are distinguished by their intended applications.

Linear lists in which insertions, deletions, and accesses to values occur almost always at the first or the last node are very frequently encountered, and we give them special names:

  • A stack is a linear list for which all insertions and deletions (and usually all accesses) are made at one end of the list.
  • A queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end.
  • A deque (“doubled-ended queue”) is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list.

A deque is therefore more general than a stack or a queue; it has some properties in common with a deck of cards, and it is pronounced the same way.

Part III. JavaScript Implementations of Stacks

In this section, we examine three JavaScript implementations of a stack that has three typical operations or methods — isEmpty, push, and pop — which a user of the stack may invoke. When invoked, the methods operate on internal values or data structures that vary from implementation to implementation. One of the goals of this section is to show how the data structures used to implement a stack need not be of any concern to a user of the stack if the user cares only or primarily about what the operations do — their functionality — and not how efficiently they operate (within some reasonable limits, of course) in terms of storage space or execution time — their performance characteristics.

ArrayStack

Our first implementation of a stack is a function called ArrayStack that returns an object with public methods (isEmpty, push, and pop) that operate on a private Array object that only the methods have access to.

If you want to understand why the public methods of an object return by ArrayStack have access to the Array object named array, you should learn about JavaScript Closures. If you want to understand why other code outside of the ArrayStack function cannot access the Array object (i.e. why the object is private), you should study carefully how JavaScript functions work, especially with respect to scoping rules. 

function ArrayStack() {

  // Private values (data structures).
  const array = [];
  
  // Public operations (application programming interface).
  const operations = {
    isEmpty: function() {
      return array.length === 0;
    },
    push: function(value) {
      array.push(value);
      return operations;
    },
    pop: function() {
      return array.pop();
    }
  };
  
  return operations;
}

LimitedArrayStack

The next implementation of a stack is a function called LimitedArrayStack that expects to be passed a positive integer that will determine the maximum size of the stack. This implementation also depends on an internal Array object; however, it uses its Array objects in different ways than stacks returned by ArrayStack use their internal Array objects. Also, a second internal data structure named size is used in addition to the Array object. 

function LimitedArrayStack(limit) {

  // Private values (data structures).
  const array = new Array(limit);
  let size = 0;
  
  // Public operations (application programming interface).
  const operations = {
    isEmpty: function() {
      return size === 0;
    },
    push: function(value) {
      if (size < limit) {
        array[size] = value;
        size = size + 1;
      }
      return operations;
    },
    pop: function() {
      let value = null;
      if (size > 0) {
        size = size - 1;
        value = array[size];
      }
      return value;
    }
  };
  
  return operations;
}

JavaScript NodeStack Variation No. 1

Stack objects returned by the NodeStack function, the third and final implementation of a stack that we’ll examine in this section, are implemented using a data structure that is quite different from the internal data structures used by objects returned by ArrayStack and LimitedArrayStack. Instead of storing values in a JavaScript Array object, stacks constructed and returned by NodeStack store values in a series of nodes, each of which contains two fields: a field that refers to a value passed to the push method, and a field that refers to the next node in the series, if there is another one. If there is not a “next” node, then the value of the field that would otherwise refer to a node refers to the object literal object known as null. 

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  // Public operations (application programming interface).
  const operations = {
    isEmpty: function() {
      return top === null;
    },
    push: function(value) {
      top = { value: value, next: top }; // new node
      return operations;
    },
    pop: function() {
      let value = null;
      if (top !== null) {
        value = top.value;
        top = top.next;
      }
      return value;
    }
  };
  
  return operations;
}

useStack

Finally, we demonstrate how a stack object returned by ArrayStack, NodeStack, or LimitedArrayStack can be used. 
function useStack(stack) {
  stack.push(1).push(2).push(3);
  while (!stack.isEmpty())
    alert(stack.pop());
}
useStack(ArrayStack());
useStack(NodeStack());
useStack(LimitedArrayStack(2));

Part IV. More JavaScript Variations of NodeStack

In this section we look at several alternate ways of composing a JavaScript function that returns a “NodeStack” object. Each variation introduces one or more JavaScript programming techniques not present in prior variations while retaining much of the flavor of the previous variation. The final variation is the one that looks the most like the Java implementations of StringNodeStack that are presented in the next section.

JavaScript NodeStack Variation No. 2

This variation dynamically adds properties to the NodeStack object under construction using the “dot” or “member selection” operator instead of constructing the entire object in one fell swoop (using a single statement). 

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  // Public operations (application programming interface).
  const operations = {};
  operations.isEmpty = function() {
    return top === null;
  };
  operations.push = function(value) {
    top = { value: value, next: top }; // new node
    return operations;
  };
  operations.pop = function() {
    let value = null;
    if (top !== null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
  
  return operations;
}

JavaScript NodeStack Variation No. 3

This variation creates the “embryonic” object using Object.create instead of assigning a literal object to a variable. Compared to the previous variation, the name of the local variable that refers to the object that is returned is thisStack instead of operations. 

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  const thisStack = Object.create(NodeStack.prototype);
  thisStack.__proto__.__proto__.constructor = NodeStack;

  // Public operations (application programming interface).
  thisStack.isEmpty = function() {
    return top === null;
  };
  thisStack.push = function(value) {
    top = { value: value, next: top }; // new node
    return thisStack;
  };
  thisStack.pop = function() {
    let value = null;
    if (top !== null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
  
  return thisStack;
}

JavaScript NodeStack Variation No. 4

This variation is significantly different from the previous ones. It requires the use of the new prefix operator in conjunction with the function when creating new objects; the object under construction is referred to by the special keyword this. When 

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  const thisStack = this;

  // Public operations (application programming interface).
  thisStack.isEmpty = function() {
    return top === null;
  };
  thisStack.push = function(value) {
    top = { value: value, next: top }; // new node
    return thisStack;
  };
  thisStack.pop = function() {
    let value = null;
    if (top !== null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
  
  return thisStack;
}

JavaScript NodeStack Variation No. 5

In this variation we get rid of the local variable thisStack and simply use the keyword this instead. Since the push method uses the value of this in the body of the method, we bind the method to the value of this. It’s not at all apparent from the code why we are doing this (pardon the easy pun). Curious readers are advised to read carefully the MDN documentation for the keyword this and the documentation for bind. 

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  // Public operations (application programming interface).
  this.isEmpty = function() {
    return top === null;
  };
  this.push = (function(value) {
    top = { value: value, next: top }; // new node
    return this;
  }).bind(this);
  this.pop = function() {
    let value = null;
    if (top !== null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };  
}

JavaScript NodeStack Variation No. 6

In this variation we employ “arrow functions” as a short-hand way of defining anonymous function literals. When using arrow functions, we do not need to bind push to this the way we did in the previous variation. Arrow functions behave remarkably different than non-arrow functions in this regard. (Pardon the pun again.) 

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  // Public operations (application programming interface).
  this.isEmpty = () => {
    return top === null;
  };
  this.push = (value) => {
    top = { value: value, next: top }; // new node
    return this;
  };
  this.pop = () => {
    let value = null;
    if (top !== null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
}

JavaScript NodeStack Variation No. 7

This variation is different from the previous one in a rather subtle way. Notice that the curly braces that were surrounding the body of of the arrow function used to initialize this.isEmpty have been removed along with the keyword return. Without the curly braces, we are in effect saying that the value of the arrow function evaluates to the value on the right hand side of the “arrow” (sometimes called a “fat arrow”); the keyword return is not needed in this case. 

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  // Public operations (application programming interface).
  this.isEmpty = () => top === null;
  this.push = (value) => {
    top = { value: value, next: top }; // new node
    return this;
  };
  this.pop = () => {
    let value = null;
    if (top !== null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
}

JavaScript NodeStack Variation No. 8

Finally, we replace the use of an object literal in the push function with a call to a LinearNode construction function that demonstrates the use of the new operator. 

function LinearNode(value, nextNode) {
  this.value = value;
  this.next = nextNode;
}

function NodeStack() {

  // Private values (data structures).
  let top = null;
  
  // Public operations (application programming interface).
  this.isEmpty = () => top === null;
  this.push = (value) => {
    top = new LinearNode(value, top);
    return this;
  };
  this.pop = () => {
    let value = null;
    if (top !== null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
}

Part V. Java Variations of StringNodeStack

A simple program that uses a StringNodeStack object. 

public class UseStringNodeStack {
  public static void main(String[] args) {
    StringNodeStack stack = new StringNodeStack();
    for (int i = args.length; i-- > 0; stack.push(args[i])); // <- Notice the semicolon!
    while (!stack.isEmpty()) System.out.println(stack.pop());
  }
}

Java StringNodeStack Variation No. 1

class LinearStringNode {
  public String value;
  public LinearStringNode next;
}

class Constructor {
  public static LinearStringNode
  makeLinearStringNode(String value, LinearStringNode nextNode) {
    LinearStringNode node = new LinearStringNode();
    node.value = value;
    node.next = nextNode;
    return node;
  }
}

class StringNodeStack {

  // Private values (data structures).
  private LinearStringNode top = null;
  
  // Public operations (application programming interface).
  public boolean isEmpty() { return top == null; }
  public StringNodeStack push(String value) {
    top = Constructor.makeLinearStringNode(value, top);
    return this;
  };
  public String pop() {
    String value = null;
    if (top != null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
}

Java StringNodeStack Variation No. 2

class LinearStringNode {
  public String value;
  public LinearStringNode next;
  public LinearStringNode(String value, LinearStringNode nextNode) {
    this.value = value;
    this.next = nextNode;
  }
}

class StringNodeStack {

  // Private values (data structures).
  private LinearStringNode top = null;
  
  // Public operations (application programming interface).
  public boolean isEmpty() { return top == null; }
  public StringNodeStack push(String value) {
    top = new LinearStringNode(value, top);
    return this;
  };
  public String pop() {
    String value = null;
    if (top != null) {
      value = top.value;
      top = top.next;
    }
    return value;
  };
}

Java StringNodeStack Variation No. 3

class LinearStringNode {
  public String value = null;
  public LinearStringNode next;
  public LinearStringNode(String value, LinearStringNode nextNode) {
    this.value = value;
    this.next = nextNode;
  }
  public LinearStringNode() { this.next = this; }
}

class StringNodeStack {

  // Private values (data structures).
  private LinearStringNode sentinel = new LinearStringNode();
  private LinearStringNode top = sentinel;
  
  // Public operations (application programming interface).
  public boolean isEmpty() { return top == sentinel; }
  public StringNodeStack push(String value) {
    top = new LinearStringNode(value, top);
    return this;
  };
  public String pop() {
    String value = top.value;
    top = top.next;
    return value;
  };
}

Exercises

  1. Examine the StringNodeClass examples shown above. Make a list of any questions you have about the code. Study each example carefully. Think about how the Java examples are similar to and different from the JavaScript examples that preceded them. What catches your eye? What piques your curiosity?
  2. Define the following terms as they are used in computer science.
    1. class
    2. object
    3. data structure
    4. data type
    5. abstract data type
    6. reference type
    7. value type
    8. member
    9. field
    10. property
    11. method
  3. What symbol denotes the “member selection” operator in Java? Is member selection a prefix, postfix, or infix operator? What types of operands does the operator take as inputs? What type of value does it produce as output? What is the precedence value of member selection? Does the member selection operator have a relatively high or low precedence value? What operators have precedence values equal to or greater than member selection? Why is it important for programmers to be familiar with the precedence values of operators?
  4. Learn about Java objects.
    1. Start by reading https://docs.oracle.com/javase/tutorial/java/javaOO/objects.html.
    2. Read about creating objects at https://docs.oracle.com/javase/tutorial/java/javaOO/objectcreation.html.
    3. Read about using objects at https://docs.oracle.com/javase/tutorial/java/javaOO/usingobject.html
    4. Read the section about objects and classes.
      1. Read the page about Returning a Value from a Method.
      2. Read the page about Using the this keyword.
      3. Read about Controlling Access to Members of a Class.
    5. Read the page about Understanding Class Members.
    6. Read the page about Initializing Fields.
    7. Read the Summary of Creating and Using Classes and Objects page.
  5. Use what you have learned about objects from doing the previous exercises to write brief paragraphs that introduce the variations of the Java StringNodeStack code samples shown above. Think about how what you read relates to the code. Recall any questions you had when you first studied the code samples. Try to write for a hypothetical student named Kant B. Bothered who has no time for lengthy conversations about programming such as chapters from textbooks or online tutorial pages like the ones you read in the previous exercise.
  6. In Java, how could you change StringNodeStack into, say, IntegerNodeStack if you needed a stack of Integer values instead of a stack of String values? What about a stack of int values? What if you needed stacks for several different types of values? Is there any way to avoid creating lots nearly identical classes in Java? How does JavaScript deal with this problem? Which solution (the Java approach or the JavaScript approach) seems better to you? Why?
  7. What chapters and sections of your textbook are relevant to these exercises?
  8. List some Wikipedia articles that are closely related to these exercises.
  9. Compose 3 original multiple-choice questions that would be suitable for a quiz or exam. (Do not plagiarize.) Your questions should be related to important topics discussed in the excerpts from Knuth above, the Oracle tutorial pages referenced in previous exercises, related sections of your textbook, or closely related Wikipedia articles. Provide the answers for your questions and cite your sources. Incorporate a brief Java program or class into at least one of your questions.