From charlesreid1

Definitions and Variations

LIFO - last in, first out (stacks)

FIFO - first in, first out (queues)

stack - LIFO data structure that only provides access at one end

queue - FIFO data structure that provides limited access at either end

dequeue - FIFO data structure that provides limited access at both end

adapter pattern - a class that adapts one type of class and matches its methods to a different but related interface/class

Variations:

  • Linked versus array implementation
  • Fixed vs variable size
  • Sorted (priority) queues

ADT and Interfaces

Stack:

  • push
  • pop
  • peek
  • size
  • empty

Extra:

  • clear
  • clone
  • equals

Queue:

  • enqueue
  • dequeue
  • peek
  • size
  • empty

Extra:

  • clear
  • clone
  • equals

Dequeue:

  • addFront
  • addBack
  • removeFront
  • removeBack
  • peekFront
  • peekBack
  • size
  • empty

Extra:

  • clear
  • clone
  • equals

Implementations

Array-based

ArrayStack:

  • data array
  • top pointer (integer)
  • size (integer)

ArrayQueue:

  • data array
  • front pointer (integer)
  • size (integer)

ArrayDeque

  • data array
  • front pointer (integer)
  • size (integer)

Link-based

LinkedStack:

  • private instance of linked list
  • adapter pattern

LinkedQueue:

  • private instance of linked list

Linked Circular Queue:

  • private instance of circular linked list

Linked Deque:

  • private instance of doubly linked list

Algorithms for Operations

Linked Stack Algorithms

push(e) method:

  • list.addFront(e)

pop() method:

  • list.removeFront()

peek() method:

  • list.first()

Linked Queue Algorithms

enqueue(e):

  • list.addBack()

dequeue():

  • list.removeFront()

peek:

  • list.first()

Linked Deque

This uses a doubly linked list (DLL, or dll, below).

addFront:

  • dll.addFront()

add/addBack();

  • dll.addBack()

removeFront()/remove():

  • dll.removeFront()

removeBack:

  • dll.removeBack()

Complexity and Cost

Big O Complexity Table

Stacks

Big-O Complexity of Stacks


Stacks

push O(1)*
pop O(1)*
peek O(1)
empty O(1)
size O(1)

Queues

Big-O Complexity of Queues


Queues

enqueue O(1)*
dequeue O(1)*
peek O(1)
empty O(1)
size O(1)

Deque

Big-O Complexity of Deques


Deques

addFront O(1)*
addBack O(1)*
removeFront O(1)*
removeBack O(1)*
peekFront O(1)
peekBack O(1)
empty O(1)
size O(1)

OOP Principles

  • Adapter pattern - results in simple, compact, portable classes.

Flags