Stacks Queues Study Guide

Implementations

Array-based

ArrayStack:

• data array
• top pointer (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.