Loading...
Data Structures: Queues
Collection of flash cards about queues
Creator
HlC44W6cOAT4s90O5qHtwtzi6lm2
What happens when a Vector runs out of capacity?
It typically allocates a larger block of memory (e.g., doubles its current capacity), copies all existing elements to the new block, and then deallocates the old block.
What is a Queue?
A linear data structure that follows the First-In, First-Out (FIFO) principle.
What is the time complexity for inserting or deleting an element in the middle of a Vector?
O(n) (linear time), because subsequent elements need to be shifted.
What is a potential disadvantage of an array-based Queue implementation?
Fixed size or the need for re-sizing (if not circular), and potential for wasted space or 'wraparound' complexity.
What does an 'isEmpty' operation check for in a Queue?
If the queue contains no elements.
What is the 'dequeue' operation in a Queue?
Removing an element from the front of the queue.
What is the 'capacity' of a Vector?
The total number of elements the Vector can hold before it needs to reallocate memory.
What is a double-ended queue (deque)?
A queue-like data structure that allows elements to be added or removed from both the front and the rear.
Which end of the Queue is used for removing elements?
The front end.
What is the 'size' of a Vector?
The number of elements currently stored in the Vector.
What is a potential advantage of a linked list-based Queue implementation?
Dynamic size, allowing it to grow or shrink as needed without explicit resizing.
What does FIFO stand for in the context of Queues?
First-In, First-Out.
Which end of the Queue is used for adding elements?
The rear (or back) end.
What does a 'size' operation return for a Queue?
The number of elements currently in the queue.
What is the time complexity for adding an element to the end of a Vector (amortized)?
O(1) (amortized constant time), as reallocations happen infrequently.
What is a Vector in programming?
A dynamic array, which is a contiguous block of memory that can automatically grow or shrink in size.
What data structure is often used to implement a Priority Queue efficiently?
A heap (min-heap or max-heap).
What is the 'push_back' (or 'add') operation in a Vector?
Adding an element to the end of the Vector.
How can you remove an element from the end of a Vector?
Using an operation like 'pop_back'.
Name two common ways to implement a Queue.
Using an array (circular array) or a linked list.
What is a Priority Queue?
A special type of queue where each element has a priority, and elements with higher priority are dequeued before elements with lower priority.
How does a Vector differ from a static array?
A static array has a fixed size defined at compile time, while a Vector can change its size during runtime.
What is the 'enqueue' operation in a Queue?
Adding an element to the rear of the queue.
What is the time complexity for accessing an element by index in a Vector?
O(1) (constant time), because elements are stored contiguously.
What is the purpose of the 'front' or 'peek' operation in a Queue?
To view the element at the front of the queue without removing it.
What is the time complexity of enqueue and dequeue operations in a queue (linked list implementation)?
Enqueue: O(1). Dequeue: O(1).
What is dequeue?
The process of removing an element from the front of the queue.
What are the advantages and disadvantages of using a linked list to implement a queue?
More complex to implement, but more efficient in terms of memory usage.
What is an input-restricted deque?
A deque where insertion is allowed at only one end.
What is a deque?
A double-ended queue, where elements can be added or removed from both ends.
What is the time complexity of enqueue and dequeue operations in a queue (array implementation)?
Enqueue: O(1). Dequeue: O(1).
What are the two types of deques?
Input-restricted deque and Output-restricted deque.
How are elements stored in an array-based queue?
Elements are stored in contiguous memory locations.
What is a queue?
A linear data structure that follows the First-In-First-Out (FIFO) principle.
What is enqueue?
The process of adding an element to the rear of the queue.
What does the size() method do?
Determines the number of elements in the queue.
What is an output-restricted deque?
A deque where deletion is allowed at only one end.
What is queue overflow?
A situation when the queue is completely full and no more elements can be added.
How do you check if a queue is empty?
Check if the front and rear pointers are pointing to the same location or if front is NULL.
When is a queue the appropriate data structure to use?
Useful when you need to maintain the order of elements and process them in the order they arrived.
What is a priority queue?
A queue where the elements have priorities assigned to them. Elements with higher priority are processed before elements with lower priority.
How is memory allocated in an array implementation of a queue?
Memory allocation is static and fixed in size.
What does FIFO stand for?
First-In-First-Out. The element that is added first is the element that is removed first.
What are the advantages and disadvantages of using an array to implement a queue?
Simple to implement, but can be inefficient if the queue becomes full.
What is a circular queue?
A queue that connects the front and rear ends, forming a circle. This helps in better memory utilization.
What are the two primary operations of a queue?
Enqueue: Adds an element to the rear of the queue. Dequeue: Removes an element from the front of the queue.
What does the peek() method do?
Returns the element at the front of the queue without removing it.
How do you check if a queue implemented using an array is full?
Check if the rear pointer has reached the last index of the array.
How is memory allocated in a linked list implementation of a queue?
Memory is allocated dynamically.
What are two common ways to implement a queue?
Arrays and linked lists.
Give three real-world applications of queues.
Print queues, call centers, and task scheduling.
What does the isEmpty() method do?
Verifies whether the queue is empty.
What are 'front' and 'rear' pointers in a queue?
front: Points to the front element in the queue. rear: Points to the rear element in the queue.
What is queue underflow?
A situation when the queue is completely empty and no more elements can be removed.
What are some common methods for a queue class?
enqueue(), dequeue(), peek()
When should you use a queue data structure?
When you need to process elements in the order they arrive.
How do you declare an empty queue of integers in C++ using STL?
std::queue<int> myQueue;
How do you dequeue an element from a queue named 'myQueue' in C++?
myQueue.pop();
What are the advantages of using a linked list for queue implementation?
Dynamic size and easier insertion/deletion.
What are the advantages of using an array for queue implementation?
Simple implementation and efficient access.
Give some real-world examples where queues are used.
Handling print jobs, managing network traffic, and CPU task scheduling.
How do you declare an empty priority queue of integers in C++ using STL?
std::priority_queue<int> myPQueue;
How are elements ordered in a priority queue?
Elements with higher priority are processed before elements with lower priority.
What are two common ways to implement a queue?
Linked List and Array
What are the restrictions on adding or removing elements in a queue?
Elements can only be inserted or deleted at the ends (front and rear).
What header file is needed to use queues in C++ STL?
#include <queue>
What operation returns the element at the rear of the queue without removing it?
rear()
What is the time complexity for front() and rear() operations in a typical queue implementation?
O(1)
Give some examples where priority queues are used.
Used in task scheduling and event simulation systems.
In what scenarios are queues particularly useful?
Useful when order of processing is important.
What is a priority queue?
A queue where elements are assigned priorities and processed based on that priority.
How do you access the rear element of a queue named 'myQueue' in C++ (C++11 and later)?
myQueue.back();
What graph traversal algorithm uses a queue?
Breadth-First Search (BFS)
What is the operation to remove an element from the front of the queue called?
dequeue()
What is the time complexity for enqueue operation in a typical queue implementation?
O(1)
What is the time complexity for dequeue operation in a typical queue implementation?
O(1)
What is a queue?
A data structure that follows the First-In-First-Out (FIFO) principle.
What data structure is commonly used to implement priority queues?
Heaps
How do you check if a queue named 'myQueue' is empty in C++?
myQueue.empty();
What operation returns the element at the front of the queue without removing it?
front()
How do you enqueue the value 10 into a queue named 'myQueue' in C++?
myQueue.push(10);
How do you find the number of elements in a queue named 'myQueue' in C++?
myQueue.size();
What is the operation to add an element to the rear of the queue called?
enqueue()
How do you access the front element of a queue named 'myQueue' in C++?
myQueue.front();
What is the defining access order of elements in a queue?
First-In-First-Out (FIFO)