HL Mastery aspects:

ADT stack

To give an example of a stack, we use a character node class. A stack of any type could be built using similar techniques.

A simple Class.

CharNode.java
source code

This Class is very bare bones. For a better implementation, methods like:

top() return top of stack without popping it

size() return number of items in stack

should be added.

CharacterStack.java
source code

Exceptions should also be thrown for errors like an attempt to pop an empty stack.

ReverseMe.java
source code

On this page: [ Abstract Data Types | Character Node | Character Stack  | Applet ]

A stack is an ADT (Abstract Data Type) - that is, we describe it by its external behaviour rather than its  internal structure.  

We have looked at arrays, linked lists, records and lists of records - these structures have been well-defined in code ("concrete").  Stacks can be described in terms of operations like pop, push, empty and top. 

The actual stack can be represented by an array or by a linked list , for example. Its operations (push, pop) are still the same.   

Stack as Linked List

Consider a simple, singly linked list:

We can simply view this list as:

and we have a stack.  New items to be pushed are added at the front (top) and items to be popped are removed from the front (top).

Back to top

An Example Stack Node

/**
* CharNode.java
*
* @author Mr J
* @version 20050205
*/
class CharNode
{
   private char item;
   private CharNode next;
   // default constructor, sets fields to null
   public CharNode( )
   {
     item = '\0'; // UNICODE 0 - the null character
     next = null;
   }
   // Second Constructor for a student record, assigns fields
   public CharNode(char ch, CharNode nx )
   {
     setItem(ch);
     setNext(nx);
   }
   // accessor methods
   public char getItem() {return item;}
   public CharNode getNext(){return next;}
   // modifier methods
   public void setItem(char ch) {item = ch;}
   public void setNext(CharNode n){next = n;}
}

Back to top

An Example Stack Class

/**
* CharNode.java
* This Class implements a stack of characters
*
* @author Mr J
* @version 20050211
*/
public class CharacterStack
{
   CharNode item;
   CharNode top;
  /**
   * CharacterStack constructor.
   */
   public CharacterStack() { top = null; }
   /**
   * Test for empty stack
   */
   public boolean isEmpty()
   {
     return (top == null);
   }
   /**
   * pop character from stack - check for underflow
   */
   public char pop()
   {
     CharNode temp;
     if (!isEmpty())
     {
       temp = top;
       top = temp.getNext();
       return temp.getItem();
     }
     else
     {
       return '\0'; // return null char on error
     }
   }
   /**
   * push character on stack.
   */
   public void push(char ch)
   {
     CharNode temp = new CharNode( ch, top);
     top = temp;
   }
}

Back to top

An Example Stack Applet

import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
/**
* Take a Strin from the user and reverse it using a stack
*
* @author Mr J
* @version 20050211
*/
public class ReverseMe extends Applet implements ActionListener
{
   // sample awt objects
   private TextField name = new TextField("Type text here!");
   private Button pressMe = new Button("Reverse me!");
   private Label greeting = new Label("The message will appear here");
   // Data member
   private CharacterStack stack = new CharacterStack();
   /**
   * Add objects to the Applet
   */
   public void init()
   {
     add(name);
     add(pressMe);
     add(greeting);
     pressMe.addActionListener(this);
   }
   /**
   * When an event occurs on an object with an ActionListener attached, this
   * method is carried out.
   *
   * @param e carries details about the event that occurred
   */
   public void actionPerformed(ActionEvent e)
   {
     // push each character on to the stack
     String text = name.getText();
     for (int p = 0; p < text.length(); p++)
     {
       stack.push(text.charAt(p));
     }
     // pop each one off and add to String
     String reverse = "";
     while (!stack.isEmpty())
     {
       reverse = reverse + stack.pop();
     }
     greeting.setText(reverse);
   }
}

Back to top

Exercises

Add an EmptyStackException to the CharacterStack Class and handle it within the ReverseMe Applet.

This one is slightly more tricky.  Write an Applet that checks to see if the opening and closing brackets match in an expression such as (a + b) / (c - d) * ( x / (y - z) ).  The AppletSimple template has the layout you need.  If you succeed, consider different kinds of bracket like square ([ ]) and braces ({ }). 

Construct an Applet that takes a String and prints out it's components in dictionary order. For example, if the String "reverse" is input, the output would be "eeerrsv". This is not a problem that requires a stack (but the techniques in ReverseMe will come in handy).

Related: [ Java home | Previous: lists | Next: queues ]

Stacks have many uses as described over in theory topic 5.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.