Stack ADT

The Stack Abstract Data Type

Key Concepts

Abstract Data Type A model of how a data type works. The program only needs to know how to interact with the construct, but not the inner-workings Stack A data collection where the last item added to the collection if the first one that can be accessed LIFO Last In, First Out (LIFO) data accessible collection

Introduction

A collection of data elements organized in a LIFO construct is a Stack. It is similar to a start of plates or coins

Learn More

Abstract Data Types

Stack ADT

Accessing Stack Data

Data is added to the stack one element at a time. It is added to the top of the collection

As in a stack of plates on a kitchen counters, a new plate is stacked on top

When a plate is needed, the top plate, the last one in is the first one sent out for use

Stack Abstraction

The inner-workings of the stack in a given language does not need to be understood by a programmer using a stack. The programmer needs to know the functions public functions available for use. The actions a program can perform on a Stack, like most ADTs, is to add and remove data from it as the main program requires

Push

New data added to the stack is pushed onto the stack. The stack provides a public Push function to accomplish this

import java.util.Stack;

public class StackExample {

  public static void main(String[] args) {
    // Create an empty stack
    Stack<String> names = new Stack<>();

    // Push elements onto the stack
    names.push("Alice");
    names.push("Bob");
    names.push("Charlie");
  }

  System.out.println("Elements in the stack (top to bottom):");
    while (!names.isEmpty()) {
      System.out.println(names.pop());
    }
}

Java provides a Stack ADT in java.util.Stack package

This code creates a Stack using Strings as the data to be contains with the stack

Lines 10 - 12 push 3 strings onto the stack

True/False In the java code, above, the first name that can be accessed is Charles
True	False

Pop

Data is removed from the stack by popping it off the stack. The last data element is removed from the stack and returned to the main program for use

import java.util.Stack;

public class StackExample {

  public static void main(String[] args) {
    // Create an empty stack
    Stack<String> names = new Stack<>();

    // Push elements onto the stack
    names.push("Alice");
    names.push("Bob");
    names.push("Charlie");
  }

  System.out.println("Elements in the stack (top to bottom):");
    while (!names.isEmpty()) {
      System.out.println(names.pop());
    }
}

The Pop function removes the last data element added, and returns it to the calling code

We also see a secondary function isEmpty() (line 16) that lets the main program know when there are no more data elements on the stack

True/False In the java code, above, the output will be Alice, Bob, Charles
True	False

Conclusion

Terms

Term	Meaning
Asynchronous	A data exchange between sender and receiver when they do not share an internal clock. - See Notes for more on how to better this definition and Synchronous definition.
Data Register	A storage location that a central processing unit (CPU) and Input/Output (I/O) Device use to exchange data. Data registers are used in Polling and Asynchronous data exchange.
Driver	A type of software that negotiates data transfer between an I/O device and a CPU.
Input/Output Device	A hardware component installed on a motherboard that facilitates passing of data between that device and the CPU. Inputs and outputs are from the perspective of the CPU. A keyboard is a CPU input device and a monitor is a CPU output device.
Interrupt	Controlling data exchange by requiring the I/O device to notify the CPU there is new data, then waiting until the CPU to request the new data when it is ready to process it.
Polling	Controlling data exchange by checking for new data in a repetitious time interval.
Priorities	A system the CPU uses to decide which I/O data to process next if there are multiple devices with data ready to process.
Status Register	A storage location that CPU and I/O Device use to share the I/O Device's status. Status registers are used in Polling and Asynchronous data exchange.
Synchronous	A data exchange between sender and receiver when they share an internal clock. - See Notes for more on how to better this definition and Asynchronous definition.