Stacks and the type Object

Stacks as destructive lists

The stack operation push is like the list operation cons: it adds a new item to the front (or top, since we generally think of stacks as building upwards, hence the name) of the structure. The stack operation pop is like the list operation tail: it takes the item off the front (top) of the structure.

Here is some code for stacks of integers, with the stacks implemented by linked lists:

class IntStack
{
 private Cell llist;

 public int top()
 {
  return llist.first;
 }

 public void pop()
 {
  llist = llist.next;
 }

 public void push(int n)
 {
  llist = new Cell(n,llist);
 }

 public boolean isEmpty()
 {
  return llist==null;
 }

 private static class Cell
 {
  int first;
  Cell next;

  Cell(int f,Cell n)
  {
   first=f;
   next=n;
  }
 }
}

As you can see, where with the type List, the method tail returned a List whose llist field was set to add the new integer to the llist field of the List object it was called on, here with the method push the llist is actually changed, but the return type is void. Similarly, where with the type List the method tail returned an object whose llist field was the linked list of all but the first element of the object it was called on, here with the method pop the llist field is actually changed to cut out the first element. So, if l refers to a List and s refers to a Stack, the statement

s.push(n);

l = l.cons(n);

s.pop();

l = l.tail();

In some implementations of stacks, the operation pop has a dual role. It both returns the top item of the stack, and changes the stack to remove that top item. In that case, the implementation of the method pop would be:

 public int pop()
 {
  int n = llist.first;
  llist = llist.next;
  return n;
 }

i = s.pop();

i = l.head();
l = l.tail();

Use of stacks for multiple undo

However, the undo command also worked to undo the undo command. If you added or deleted an element from the set then entered the undo command, then entered the undo command again you got back to the position after you added or deleted the element. This meant you could not reverse the effect of more than one add or delete commands. If you added two elements in succession, you could reverse the effect of adding the second element, but not the effect of adding both elements (in this simple example, you could, of course, effectively do this using the delete command, but we could imagine more complex systems where there is no so easy a way to reverse the effect of a command without a special undo command).

An alternative form of undo command would work to reverse the effect of all previous add or delete operations if used multiple numbers of times. So calling the undo command twice after adding two numbers would return to the situation before adding those two numbers and so on.

If we want to do this, we need to keep a collection storing references to the previous states of the set. This collection operates as a stack. Each time we make a change to the set, we push the previous form of it onto the stack of old set states. When we do an undo, we return to the top element of the stack and pop that top element off.

Since the undo command no longer reverses itself, we need another command to undo an undo, in our simple system r for "redo". We then need to keep a separate stack so that the redo command can also be issued a multiple number of times. Suppose we add two numbers, issue to undo commands to revert to the situation before adding them, then decide to reverse both undo commands, we want to be able to do this by issuing two redo commands. So when an undo command is issued, the current state is pushed onto the stack of undone states. When a redo command is issued, the current set is replaced by the top set from this stack, and the stack is popped. For example, if the following sequence of commands is issued (from the start position of an empty set),

a 7
a 5
a 4
d 5
a 3
a 8
a 6
d 3
a 2
u
u
u

Here mySet is the name for the current set. If another u command is issued, {3,4,7,8} will be pushed onto the stack undone, {3,4,7} will be popped off the stack done and mySet will be set to refer to {3,4,7}. If an r command is issued, {3,4,7,8} will be pushed onto the stack done, {3,4,6,7,8} will be popped off stack undone and mySet will be set to refer to {3,4,6,7,8}.

You might note that the behaviour here is very similar to that of the Back and Forward buttons on a web browser. You have the current web page you are viewing, a stack of records of previous web pages you have viewed, accessible via the Back button, and if you have used the Back button to get to your current web page, another stack of web pages you have visited available via the Forward button.

Here is the code for a set maintenance system including an undo command which can be used multiple numbers of times, and a redo command:

import java.io.*;

class UseIntSets20
{
// Set maintenance program with constructive set class
// Includes 'undo' command with multiple levels of undo

 public static void main(String[] args)
 throws IOException
 {
  int n=0;
  char ch;
  String line;
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  Stack done = new Stack(), undone = new Stack();
  IntSet20 mySet = new IntSet20();
  do {
      System.out.print(": ");
      line = in.readLine();
      ch = line.charAt(0);
      if(line.length()>1)
         n = Integer.parseInt(line.substring(1).trim());
      switch(ch)
         {
          case 'q' : 
            break;
          case 'd' :
            done.push(mySet);
            mySet = mySet.delete(n);
            undone = new Stack();
            break;
          case 'a' :
            done.push(mySet);
            mySet = mySet.add(n);
            undone = new Stack();
            break;
          case 'm' :
            if(mySet.member(n))
               System.out.println("Is a member");
            else
               System.out.println("Not a member");
            break;
          case 'u':
            if(done.isEmpty())
               System.out.println("Nothing to undo");
            else
               {
                undone.push(mySet);
                mySet = (IntSet20) done.top();
                done.pop();
               }
            break;
          case 'r':
            if(undone.isEmpty())
               System.out.println("Nothing to redo");
            else
               {
                done.push(mySet);
                mySet = (IntSet20) undone.top();
                undone.pop();
               }
            break;
          case 'p':
            System.out.println(mySet);
            break;
          default:
            System.out.print("d - delete, a - add, m - member,");
            System.out.println("u - undo,  r - redo, p - print, q - quit");
            break;
         }
     }
  while(ch!='q');
 }

}

class Stack
{
 private Cell llist;

 public Object top()
 {
  return llist.first;
 }

 public void pop()
 {
  llist = llist.next;
 }

 public void push(Object obj)
 {
  llist = new Cell(obj,llist);
 }

 public boolean isEmpty()
 {
  return llist==null;
 }

 private static class Cell
 {
  Object first;
  Cell next;

  Cell(Object f,Cell n)
  {
   first=f;
   next=n;
  }
 }
}

Because the primitive types like int are not object types, the code for Stack above cannot be used to make stacks of integers. However, Java provides types called the wrapper classes which are object types to match the primitive types. The wrapper class for int is Integer.

Last modified: 18 March 2005