The Stack Abstract Data Type (ADT)

Session Objectives

We continue our discussion of the stack ADT. Chapter 5 is the corresponding reading from our textbook.

Objective 1 

Ensure that we all understand what an ADT is

Objective 2

Ensure that we all recognize the difference between an ADT and a concrete implementation of that ADT

Objective 3 

Provide an in-depth discussion of the stack ADT

Objective 4

Provide a preview of the first programming assignment

Objective 5

Understand how a stack can be implemented as a linked list

Objective 6

Understand how classes and objects are really represented in a computer in order to understand linked structures better

Review of ADTs

Remember that an abstract data type specifies the type by name (e.g., int) and the operations on items declared to be of that type (e.g., +, -, *, /)

Implementing an ADT

An ADT only specifies what the type is by name and what the operations are on values of that type.  It does not specify how an ADT is to be implemented.  It is up to the programmer to implement a concrete version of the abstract data type that meets the functional specifications of the ADT.  How is not important as long as the implementation works properly.  A secondary important consideration is efficiency.

The Stack ADT

Recall what the stack ADT is.  It defines the name of the type (stack) and operations that can be performed on the stack:

• push(item) -- places an item on the stack
• pop() -- removes from the stack and returns the most recently pushed item
• peek() -- returns the most recently pushed item without removing it from the stack
• empty() -- returns true if the stack contains no items and false otherwise

A Peek at the First Programming Assignment

You will be constructing a calculator that allows you to evaluate postfix arithmetic expressions

Linked Lists as a Data Structuring Paradigm

"Linked lists" as a data structuring term refers to a "free form" approach to structuring data by linking the items of data together explicity by including one or more explicit links in each object in the system to other objects as appropriate.

Example of a node to be used in a stack implemented as a linked list

/**
* Class for type node containing an integer
*
* @ Rocky
* @ January 29, 2008
*/
public class Node
{
      // instance variables - replace the example below with your own
         public int data;

     // type of value that can be stored in a Node object
        public Node next; // a reference to a Node object

    // Constructor for objects of class Node 
       public Node(int dataItem)
      {
          data = dataItem;
          next = null;
       }

       public Node(int dataItem, Node nodeReference)
      {
          data = dataItem;
          next = nodeReference;
      }

      public int get()
     {
          return (data);
     }

}

Behind the Scenes: Classes and Objects in Memory

Pay close attention.  Once you understand this you become the magician rather than the one for whom alll of this stuff seems like magic.