Stacks and Queues

• What is a stack in data structures?

  A data structure for storing data
• What does LIFO stand for in the context of stacks?

  Last In First Out
• What happens when you pop an item from a stack?

  You remove the last item added
• How is a stack implemented?

  Using one pointer
• What are three uses of stacks?

  Reversing data, storing return addresses, CPU registers
• What are the contents of a stack after the following operations: Push A, Push B, Push C, Pop?

  • Stack Contents: AB
• What is the difference between a stack and a queue?

  • Stack: LIFO (Last In First Out)
  • Queue: FIFO (First In First Out)
• What is a queue in data structures?

  A data structure for storing data
• What does FIFO stand for in the context of queues?

  First In First Out
• What happens when you pop an item from a queue?

  You remove the first item added
• How is a queue implemented?

  Using two pointers
• What are two common uses of queues?

  Buffers for data processing and keyboard input
• What are the steps in the Push function for a stack?

  1. Check for stack overflow
  2. Increment pointer
  3. Add item to stack
• What are the steps in the Pop function for a stack?

  1. Check for underflow error
  2. Return item at pointer
  3. Decrement pointer
• What are the steps in the PushQ function for a queue?

  1. Check for queue overflow
  2. Increment back pointer
  3. Add item to queue
• What are the steps in the PopQ function for a queue?

  1. Check for queue empty error
  2. Return item at front pointer
  3. Increment front pointer
• How can an array implement a queue?

  • Head pointer and tail pointer
  • Tail pointer increments on enqueue
  • Head pointer increments on dequeue
• What is a circular queue?

  • A queue that wraps around in memory
  • Resets pointer to start when reaching end
• What are the steps in the Push function for a circular queue?

  1. Check for queue overflow
  2. Increment back pointer
  3. Reset back pointer if at max
• What are the steps in the Pop function for a circular queue?

  1. Check for queue empty error
  2. Return item at front pointer
  3. Increment front pointer and reset if at max
• How does a circular queue solve the problem of memory migration?

  It wraps around to the start of memory
• What error does the Push function check for in a stack?

  Stack Overflow error
• What error does the Pop function check for in a stack?

  Underflow error
• What error does the PushQ function check for in a queue?

  Queue Overflow error
• What error does the PopQ function check for in a queue?

  Queue Empty error
• What happens if the back pointer reaches the maximum pointer in a circular queue?


  It resets to the start of memory
• What happens if the front pointer equals the back pointer in a queue?

  It indicates a queue empty error