2.4 Stacks and queues

• What does LIFO stand for in the context of stacks?

  Last-In-First-Out
• Arrays allow random access, while stacks only allow access to the top element.
• Function calls and expression evaluation are use cases for stacks
• A stack is a FIFO data structure.

  False
• What does FIFO stand for in the context of queues?

  First-In-First-Out
• Queues allow insertion at the end and deletion from the front.
• Job scheduling in operating systems is a practical use case for queues
• Steps for implementing a stack using an array

  1️⃣ Define an array and a top pointer

  2️⃣ Implement push operation to add elements

  3️⃣ Implement pop operation to remove elements

  4️⃣ Implement peek operation to view the top element
• Push and pop operations in an array-based stack have a time complexity of $O(1)$
• What is used to store elements in a linked list implementation of a stack?

  Nodes
• Steps for implementing a stack using a linked list

  1️⃣ Create a node class with data and next pointer

  2️⃣ Implement push operation to add new nodes

  3️⃣ Implement pop operation to remove top node

  4️⃣ Implement peek operation to view top node
• The storage type for arrays is contiguous
• Linked lists allow unlimited stack size without pre-defining.
• Steps for implementing a queue using an array

  1️⃣ Define an array, front pointer, and rear pointer

  2️⃣ Implement enqueue operation to add elements

  3️⃣ Implement dequeue operation to remove elements
• What is the role of the rear pointer in a linked list implementation of a queue?

  Points to the last element
• Match the storage feature with the correct data structure:

  Contiguous storage ↔️ Array

  Dynamic storage ↔️ Linked List
• Linked lists are more memory-efficient for large queues compared to arrays.
• What is the size of the queueArray in the array-based queue implementation in pseudocode?

  10
• In the dequeue operation for an array-based queue, the front pointer is incremented if it is less than or equal to the rear
• A queue underflow occurs in an array-based queue when the front pointer exceeds the rear pointer.
• What type of memory allocation does a linked list use for queues?

  Dynamic
• Steps for the enqueue operation in a linked list-based queue

  1️⃣ Create a new node with the given value

  2️⃣ If the queue is empty, set both front and rear to the new node

  3️⃣ Otherwise, set the current rear's next to the new node and update the rear
• What does the acronym LIFO stand for in the context of a stack?

  Last-In-First-Out
• Stacks allow random access to any element, similar to arrays.

  False
• What does the acronym FIFO stand for in the context of a queue?

  First-In-First-Out
• Match the data structure with its access type:

  Stack ↔️ LIFO

  Queue ↔️ FIFO

  Array ↔️ Random
• Adding an element to the rear of a queue is called enqueue
• What type of memory allocation does an array-based stack use?

  Contiguous
• In an array-based stack, a stack overflow occurs when the top pointer exceeds the maximum size of the array.
• Which type of stack implementation is more efficient for large stacks?

  Linked List
• Steps for the push operation in a linked list-based stack

  1️⃣ Create a new node with the given value

  2️⃣ Set the new node's next pointer to the current top

  3️⃣ Update the top to the new node
• In a linked list-based stack, the top pointer is updated to the next node after a pop
• What type of memory allocation does an array-based queue use?

  Contiguous
• In an array-based queue, a queue overflow occurs when the rear pointer reaches the end of the array.
• Which type of queue implementation is more flexible in size?

  Linked List
• Steps for the enqueue operation in a linked list-based queue

  1️⃣ Create a new node with the given value

  2️⃣ If the queue is empty, set both front and rear to the new node

  3️⃣ Otherwise, set the current rear's next pointer to the new node and update the rear
• How do stacks manage function calls in computer science?

  LIFO
• Stacks are used in expression evaluation to convert infix expressions to postfix
• Backtracking algorithms use stacks to store intermediate states for reverting when necessary.
• What is one practical use case of queues in operating systems?

  Job Scheduling