Loading...
Data Structures: Queues
Collection of flash cards about queues
Creator
HlC44W6cOAT4s90O5qHtwtzi6lm2
What is the 'size' of a Vector?
The number of elements currently stored in the Vector.
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 the purpose of the 'front' or 'peek' operation in a Queue?
To view the element at the front of the queue without removing it.
Name two common ways to implement a Queue.
Using an array (circular array) or a linked list.
What is the 'push_back' (or 'add') operation in a Vector?
Adding an element to the end of the Vector.
Which end of the Queue is used for adding elements?
The rear (or back) end.
What does FIFO stand for in the context of Queues?
First-In, First-Out.
What is the time complexity for accessing an element by index in a Vector?
O(1) (constant time), because elements are stored contiguously.
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 data structure is often used to implement a Priority Queue efficiently?
A heap (min-heap or max-heap).
What is the 'capacity' of a Vector?
The total number of elements the Vector can hold before it needs to reallocate memory.
What is the 'dequeue' operation in a Queue?
Removing an element from the front of the queue.
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.
How can you remove an element from the end of a Vector?
Using an operation like 'pop_back'.
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.
Which end of the Queue is used for removing elements?
The front end.
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 the 'enqueue' operation in a Queue?
Adding an element to the rear of the queue.
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.
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 a 'size' operation return for a Queue?
The number of elements currently in the queue.
What is a Queue?
A linear data structure that follows the First-In, First-Out (FIFO) principle.
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 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.
What is the time complexity of enqueue and dequeue operations in a queue (linked list implementation)?
Enqueue: O(1). Dequeue: O(1).
What are two common ways to implement a queue?
Arrays and linked lists.
What does the size() method do?
Determines the number of elements in the queue.
What is dequeue?
The process of removing an element from the front of the queue.
What is an output-restricted deque?
A deque where deletion is allowed at only one end.
Give three real-world applications of queues.
Print queues, call centers, and task scheduling.
What is the time complexity of enqueue and dequeue operations in a queue (array implementation)?
Enqueue: O(1). Dequeue: O(1).
What is a deque?
A double-ended queue, where elements can be added or removed from both ends.
What is an input-restricted deque?
A deque where insertion is allowed at only one end.
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.
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.
What is a queue?
A linear data structure that follows the First-In-First-Out (FIFO) principle.
What is queue underflow?
A situation when the queue is completely empty and no more elements can be removed.
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 enqueue?
The process of adding an element to the rear of the queue.
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 implemented using an array is full?
Check if the rear pointer has reached the last index of the array.
How are elements stored in an array-based queue?
Elements are stored in contiguous memory locations.
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.
How is memory allocated in an array implementation of a queue?
Memory allocation is static and fixed in size.
What does the isEmpty() method do?
Verifies whether the queue is empty.
What are the two types of deques?
Input-restricted deque and Output-restricted deque.
What are some common methods for a queue class?
enqueue(), dequeue(), peek()
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 priority queue?
A queue where the elements have priorities assigned to them. Elements with higher priority are processed before elements with lower priority.
What does the peek() method do?
Returns the element at the front of the queue without removing it.
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 does FIFO stand for?
First-In-First-Out. The element that is added first is the element that is removed first.
What is a circular queue?
A queue that connects the front and rear ends, forming a circle. This helps in better memory utilization.
How is memory allocated in a linked list implementation of a queue?
Memory is allocated dynamically.
What is a priority queue?
A queue where elements are assigned priorities and processed based on that priority.
How do you enqueue the value 10 into a queue named 'myQueue' in C++?
myQueue.push(10);
How do you access the rear element of a queue named 'myQueue' in C++ (C++11 and later)?
myQueue.back();
How are elements ordered in a priority queue?
Elements with higher priority are processed before elements with lower priority.
What is the time complexity for front() and rear() operations in a typical queue implementation?
O(1)
What operation returns the element at the rear of the queue without removing it?
rear()
When should you use a queue data structure?
When you need to process elements in the order they arrive.
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 graph traversal algorithm uses a queue?
Breadth-First Search (BFS)
Give some real-world examples where queues are used.
Handling print jobs, managing network traffic, and CPU task scheduling.
What is the defining access order of elements in a queue?
First-In-First-Out (FIFO)
What is the operation to add an element to the rear of the queue called?
enqueue()
What are the advantages of using an array for queue implementation?
Simple implementation and efficient access.
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 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)
How do you dequeue an element from a queue named 'myQueue' in C++?
myQueue.pop();
What header file is needed to use queues in C++ STL?
#include <queue>
What are two common ways to implement a queue?
Linked List and Array
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.
How do you declare an empty priority queue of integers in C++ using STL?
std::priority_queue<int> myPQueue;
What is the time complexity for dequeue operation in a typical queue implementation?
O(1)
What operation returns the element at the front of the queue without removing it?
front()
What is a queue?
A data structure that follows the First-In-First-Out (FIFO) principle.
How do you access the front element of a queue named 'myQueue' in C++?
myQueue.front();
How do you find the number of elements in a queue named 'myQueue' in C++?
myQueue.size();
How do you declare an empty queue of integers in C++ using STL?
std::queue<int> myQueue;
What are the advantages of using a linked list for queue implementation?
Dynamic size and easier insertion/deletion.