// Push new element into the end of the queue
void push(T item) {
[Link](item); // Add item to the tail (end) of the queue
// Remove and return the element from the head of the queue
T pop() {
if ([Link]()) {
throw std::out_of_range("Queue is empty");
return [Link](0); // Remove from the head (front) of the queue
// Return the value of the element at the head of the queue (without removing)
T top() {
if ([Link]()) {
throw std::out_of_range("Queue is empty");
return [Link](0); // Get the element at the head (front) of the queue
}
// Determine if the queue is empty
bool empty() {
return [Link]();
// Get the size of the queue
int size() {
return [Link]();
// Clear all elements of the queue
void clear() {
[Link]();
int sumOfMaxSubarray(vector<int>& nums, int k) {
deque<int> dq; // Deque to store the indices of elements in the current window
int sum = 0; // To store the total sum of maximums of all subarrays
// Traverse through each element in the array
for (int i = 0; i < [Link](); ++i) {
// Remove elements from the front of the deque that are outside the current window
if (![Link]() && [Link]() <= i - k) {
dq.pop_front();
}
// Remove elements from the back of the deque that are smaller than the current element
while (![Link]() && nums[[Link]()] <= nums[i]) {
dq.pop_back();
// Add the current element's index to the deque
dq.push_back(i);
// Once we have processed at least the first k elements
if (i >= k - 1) {
// The element at the front of the deque is the maximum of the current window
sum += nums[[Link]()];
return sum;
}
void bfs(vector<vector<int>> graph, int start) {
int n = [Link](); // Number of nodes in the graph
vector<bool> visited(n, false); // To track visited nodes
queue<int> q; // Queue to manage the BFS process
// Start BFS from the start node
[Link](start);
visited[start] = true;
// While there are nodes to visit
while (![Link]()) {
int node = [Link](); // Get the front node
[Link](); // Remove it from the queue
cout << node << " "; // Print the visited node
// Explore the neighbors of the current node
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
[Link](neighbor); // Enqueue the unvisited neighbor
visited[neighbor] = true; // Mark it as visited
}
bool isBipartite(vector<vector<int>> graph) {
int n = [Link](); // Number of nodes in the graph
vector<int> color(n, -1); // Color array: -1 means uncolored, 0 and 1 are the two colors
// Process all nodes (to handle disconnected components)
for (int start = 0; start < n; ++start) {
if (color[start] == -1) {
// Start BFS from this uncolored node
queue<int> q;
[Link](start);
color[start] = 0; // Color the start node with 0
// Perform BFS
while (![Link]()) {
int node = [Link]();
[Link]();
// Traverse all adjacent nodes
for (int neighbor : graph[node]) {
if (color[neighbor] == -1) {
// Assign the opposite color to the neighbor
color[neighbor] = 1 - color[node];
[Link](neighbor);
} else if (color[neighbor] == color[node]) {
// If the neighbor has the same color, the graph is not bipartite
return false;
return true; // If all components are successfully colored, the graph is bipartite
// iostream, vector and queue are included
// Hint: use breadth-first-search
int secondsToBeRotten(vector<vector<int>>& grid) {
int rows = [Link]();
int cols = grid[0].size();
queue<pair<int, int>> q;
int freshApples = 0;
int time = 0;
// Direction vectors for adjacent cells (up, down, left, right)
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// Step 1: Enqueue all rotten apples and count fresh apples
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
[Link]({i, j}); // Rotten apple
} else if (grid[i][j] == 1) {
freshApples++; // Fresh apple
// If there are no fresh apples, return 0 (no time required)
if (freshApples == 0) return 0;
// Step 2: Perform BFS to rot the fresh apples
while (![Link]()) {
int size = [Link]();
bool rotted = false;
// Process each rotten apple in the queue
for (int i = 0; i < size; i++) {
pair<int, int> cell = [Link]();
[Link]();
// Check all 4 adjacent cells
for (auto dir : directions) {
int newRow = [Link] + [Link];
int newCol = [Link] + [Link];
// If the adjacent cell is a fresh apple, rot it
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&
grid[newRow][newCol] == 1) {
grid[newRow][newCol] = 2; // Rot the fresh apple
[Link]({newRow, newCol});
freshApples--;
rotted = true;
// If at least one apple was rotted in this iteration, increase the time
if (rotted) time++;
// If there are still fresh apples, return -1, otherwise return the time
return freshApples == 0 ? time : -1;
}
void interleaveQueue(queue<int>& q) {
int n = [Link]();
stack<int> s;
// Step 1: Push the first half into a stack
for (int i = 0; i < n / 2; i++) {
[Link]([Link]());
[Link]();
// Step 2: Enqueue elements from stack back to queue (they will be in reverse order)
while (![Link]()) {
[Link]([Link]());
[Link]();
// Step 3: Move the first half (which is now at the front) to the back of the queue
for (int i = 0; i < n / 2; i++) {
[Link]([Link]());
[Link]();
// Step 4: Push the first half into the stack again (now in the correct order)
for (int i = 0; i < n / 2; i++) {
[Link]([Link]());
[Link]();
// Step 5: Interleave the stack with the remaining queue
while (![Link]()) {
[Link]([Link]());
[Link]();
[Link]([Link]());
[Link]();
}
// iostream, vector and queue are included
// You can write helper methods
long long nthNiceNumber(int n) {
queue<string> q;
// Initialize the queue with the first two nice numbers
[Link]("2");
[Link]("5");
string currentNiceNumber;
// Process until we reach the nth nice number
for (int i = 0; i < n; ++i) {
// Get the next nice number
currentNiceNumber = [Link]();
[Link]();
// Generate next nice numbers and add them to the queue
[Link](currentNiceNumber + "2");
[Link](currentNiceNumber + "5");
// Convert the final nice number to long long
return stoll(currentNiceNumber);