Stacks Queues Study Guide

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.