Lecture 22 Objectives

KNOW:

• That the Java ArrayList is a data structure that provides random access (direct access) to its elements
• That the capacity of an ArrayList is automatically increased to accomodate the number of additions to the ArrayList
• That an ArrayList prevents access to uninitialized elements
• That a stack is an ADT that accesses its elements in a last-in-first-out order
• That a queue is an ADT that accesses its elements in a first-in-first-out order
• That the Java libraries provide classes that implement stacks and queues

BE ABLE TO:

• Define an ArrayList
• Manipulate an ArrayList through the use of the methods add(), get(), isEmpty(), remove(), set(), and size()
• Implement a stack (with operations push/pop/peek) using a LinkedList
• Implement a stack (with operations push/pop/peek) using an ArrayList
• Implement a queue (with operations enqueue/dequeue/front) using an LinkedList
• Implement a queue (with operations enqueue/dequeue/front) using an ArrayList

Sample Exam Question:

In a short paragraph, compare the efficiency (big-O) of the queue operations

• enqueue
• dequeue