# StacksQueues/Java

### From charlesreid1

## Contents

# Notes

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

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

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

# Implementations

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: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/stacks/ArrayStack.java

### 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: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java

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: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueueFS.java

import java.util.*; import java.io.*; 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: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/LinkedQueue.java

# Flags

Data StructuresThis is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
· Template:DataStructuresFlag · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |

Stacks and QueuesSeries on Data Structures
StacksQueues/Python StacksQueues/Python/LinkedStack
StacksQueues/Java StacksQueues/Java/LinkedStack
Postfix_Expressions#Stacks
· Template:StacksQueuesFlagBase · e |

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |

Linked ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |

Maps and DictionariesSeries on Data Structures
Maps Map implementations: Maps/AbstractMap Dictionary implementations: Dictionaries/LinkedDict
Hash Maps/OOP Hash Maps/Dynamic Resizing Hash functions: Hash Functions Hash map implementations: Hash Maps/AbstractHashMap
Skip Lists Java implementations: SkipList
Sets
· Template:MapsFlagBase · e |