Lists, Stacks, and Queues Quiz for AP Computer Science A

📚 Quick Study Guide

• 💾 List: An ordered collection of elements, allowing duplicates. Implemented using arrays or linked lists. Key operations include adding, removing, and accessing elements.
• 📊 Stack: A Last-In-First-Out (LIFO) data structure. Think of it like a stack of plates.
  • Key operations: push (add to the top), pop (remove from the top), peek (view the top element).
• 📦 Queue: A First-In-First-Out (FIFO) data structure, like a waiting line.
  • Key operations: enqueue (add to the rear), dequeue (remove from the front), peek (view the front element).
• ⏱️ Time Complexity:
  • List (ArrayList): Access O(1), Insert/Delete O(n)
  • List (LinkedList): Access O(n), Insert/Delete O(1)
  • Stack: Push/Pop/Peek O(1)
  • Queue: Enqueue/Dequeue/Peek O(1)
• ✏️ Key Differences: Understand when to use each data structure based on the problem requirements. Stacks are used in scenarios like backtracking and function calls, while queues are used in scenarios like breadth-first search and task scheduling.

🧪 Practice Quiz

1. Which data structure follows the LIFO (Last-In-First-Out) principle?
   1. List
   2. Queue
   3. Stack
   4. Array
2. Which of the following is NOT a fundamental operation of a Queue?
   1. Enqueue
   2. Dequeue
   3. Pop
   4. Peek
3. In terms of time complexity, what is the average time complexity to access an element in an ArrayList?
   1. O(n)
   2. O(log n)
   3. O(1)
   4. O(n^2)
4. Which data structure is most suitable for implementing a 'Back' button functionality in a web browser?
   1. Queue
   2. List
   3. Stack
   4. Set
5. What is the purpose of the 'peek' operation in both Stacks and Queues?
   1. To remove an element
   2. To add an element
   3. To view the top/front element without removing it
   4. To search for a specific element
6. Which of the following scenarios is best suited for using a Queue?
   1. Managing function calls in a program
   2. Processing tasks in the order they were received
   3. Implementing a search algorithm with backtracking
   4. Storing a list of unique elements
7. What is the time complexity of the `push` operation in a Stack?
   1. O(n)
   2. O(log n)
   3. O(1)
   4. O(n log n)