1.6.2 Stacks1.6.1.1 Polymorphism via Interfaces1.6 Abstract Data Types1.6.3 Queues

1.6.2 Stacks

A stack is a pile of items. We may place a new item on the top ("push") and remove an item from the top ("pop"), but we do not have access to the items below the top. The last item pushed is always the first item popped; a stack is therefore also called a  LIFO data structure ("last in, first out"). This idea is illustrated by the following picture.


Stack

Stack Operations
 


The following applet illustrates the various stack operations.

If you don't see the applet your Browser does not support Java. Click here, to view a precomputed image.

Applet

The abstract datatype "stack of integers" is represented by the following Java interface:

  interface Stack
  {
    // -----------------------------------------------------
    // b = isEmpty()
    // 'b' is true exactly if 'this' stack has no elements
    // -----------------------------------------------------
    boolean isEmpty();

    // -----------------------------------------------------
    // push(t)
    // push 't' on top of 'this' stack
    //
    // Output:
    //   'this' is the old stack with the new top 't' i.e.
    //   'pop() == t' and 'top() == t'
    // -----------------------------------------------------
    void push(int t);

    // -----------------------------------------------------
    // t = pop()
    // 't' is the result of popping the top of 'this' stack.
    //
    // Input:
    //   '!isEmpty()'
    // Output:
    //   't' is the last item pushed on the stack.
    //   'this' is the old stack without the top element
    // -----------------------------------------------------
    int pop();

    // -----------------------------------------------------
    // t = top()
    // 't' is the top of 'this' stack.
    //
    // Input:
    //   '!isEmpty()'
    // Output:
    //   't' is the last item pushed on the stack.
    //   'this' stack remains unchanged.
    // -----------------------------------------------------
    int top();
  }

We can easily implement a stack by a linked list as shown by the following declaration:

  class ListStack implements Stack
  {
    Node head;

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

    public void push(int t)
    {
      Node node = new Node(t, head);
      head = node;
    }

    public int pop()
    {
      int value = top();
      head = head.next;
      return value;
    }

    public int top()
    {
      return head.value;
    }
  }

We may then use the stack as follows:

  Stack s = new ListStack();
  s.push(3); s.push(4); s.push(5);
  int v0 = s.pop(); System.out.println(v0);
  int v1 = s.pop(); System.out.println(v1);

which gives output

  5
  4

Example  (Parenthesis Matching) We want to write a function that takes a string of parentheses, e.g.
  (([()[]][])[])

and returns true if and only if the closing parentheses match the open parentheses (like in above example). It would return false if a closing parenthesis would not have an opening counterpart (or vice versa) or if it would encounter an mismatch as in

  (([()[])[])[])

Our solution uses a stack: whenever we encounter an open parenthesis, we push it on the stack. When we encounter a closing parenthesis, we pop one element from the stack and check whether it has the right shape.

  static boolean checkParens(String word)
  {
    int n = word.length();
    Stack stack = new ListStack();
    for (int i = 0; i < n; i++)
    {
      char ch = word.charAt(i);
      switch (ch)
      {
        case '(': case '[':
          stack.push(ch);
          break;
        case ')': case ']':
          if (stack.isEmpty()) return false;
          char ch0 = (char)stack.pop();
          if (ch == ')' && ch0 != '(') return false;
          if (ch == ']' && ch0 != '[') return false;
          break;
        default:
          break;
      }
    }
    return stack.isEmpty();
  }

When we encounter a closing parenthesis, we first check whether the stack is empty. If yes, there is a closing parenthesis that has no matching open parenthesis such that we return false. Otherwise, we pop the top element and check whether it has the right shape. If not, we return false. When we have processed all characters, we return true provided that the stack is empty. If not, there was an open parenthesis without a closing counterpart. When parsing the word [()[]] the stack will take the following values:

Next Character Stack Contents
[ [
( [(
) [
[ [[
] [
]

All parentheses have matched and the stack is finally empty. Therefore the function returns true.

The Java standard library provides a class Stack implemented on top of class Vector; for the class interface, please consult the Java Manual.


© Wolfgang Schreiner; February 3, 2005

1.6.2 Stacks1.6.1.1 Polymorphism via Interfaces1.6 Abstract Data Types1.6.3 Queues