From charlesreid1


Stacks and Queues in Java are implemented as part of the Collections library. Also implemented are Deques and priority queues.

Goodrich Java Chapter 6

Chapter 6 of Goodrich covers stacks and queues. These data structures can be implemented using array-based or link-based data structures. Thus, when covering data structures it's useful to start by covering array-based data structures that are dynamic, and their big-O cost of operations.


Stacks are LIFO - last in first out - data structures

Stacks lend themselves naturally to a linked list implementation, but can be implemented as an O(1) operation for both singly linked lists and array based lists.

  • pushing onto the stack - O(1) operation
  • popping from the stack - O(1) operation


Queues are FIFO - first in first out - data structures

Queue - singly-linked list implementation - single head pointer - allows us to:

  • insert/remove at the head with O(1)
  • insert/remove at the tail with O(n)

Removing is O(n) because in a singly-linked list, we need the thing that links to tail.

Implementing a doubly linked list makes access to second-to-last element faster, at a higher overhead cost.

Doubly-linked queue allows for

  • insertion with O(1) speed
  • removal with O(1) speed


Stacks and queues can be implemented using various implementations:

  • fixed/variable size
  • contiguous/linked memory structure (array list vs linked list)
  • singly/circular/doubly linked lists
  • size of lists, size of objects and pointers

measurement/profiling of Java code for memory and performance, timing, etc.

  • inputs X, outputs Y, with timing/profiling.

Stack interfaces

Interfaces in Java provide programmers with "inheritance lite" - in the form of a set of virtual methods that a class is required to implement.

These allow a uniform interface to be imposed for data collections objects.

Here is a Java interface for a Stack class that adheres to the Stack interface described at the Abstract Data Types page:

StacksQueues/Java/Stack Interface

Stack classes

Array-based Stack Implementation

implementation of a stack using a fixed or variable size array.

Wiki notes: StacksQueues/Java/ArrayStack and Wiki notes: StacksQueues/Java/ArrayStackFS

Array-based stack implementation:

Array-based Queue Implementation

The first array-based queue implementation is a data structure that uses a dynamically allocated array size to store data. ArrayQueue class:

The second aray-based queue implementation is a data structure that uses a fixed array size, and throws a Full exception when full. ArrayQueueFS class:

import java.util.*;

class Empty extends ArrayIndexOutOfBoundsException{};
class Full extends ArrayIndexOutOfBoundsException{};

Linked List-based Queue Implementation

The linked queue class uses a circular linked list to conserve memory for linked lists with high throughput.

See LinkedQueue class: