Recently I have been looking at data structures and algorithms, trying to sum up my debut ~

TL; DR

Features of the queue: first in, first out.

Exercise: Implement queues with stacks

Stack last in first out, queue first in first out.

When the input stack is pushed properly, it is equivalent to the queue in reverse order. If the elements of the “input stack” are ejected one by one into the “output stack”, which is equivalent to a positive order queue, then ejected achieves first-in, first-out.

Steps:

  • Treat one stack as “input stack” and the other as “output stack”
  • When pushing () a new element, enter the “input stack”
  • When an element is popped (), the element is preferentially popped from the output stack. If the output stack is empty, the elements of the input stack are pushed one by one into the output stack, so that the output stack is a positive queue ready to perform the pop operation

/** * Initialize your data structure here. */
var MyQueue = function () {
  // Instacks can only be fetched from this stack. If this stack is empty, instacks can be fetched from the top of the stack
  this.outStack = [];
  // The queue can only be entered from this stack
  this.inStack = [];
};

/**
 * Push element x to the back of queue.
 * @param {number} x
 * @return {void}* /
MyQueue.prototype.push = function (x) {
  this.inStack.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}* /
MyQueue.prototype.pop = function () {
  if (this.outStack.length) {
    return this.outStack.pop();
  }
  while (this.inStack.length) {
    this.outStack.push(this.inStack.pop());
  }
  return this.outStack.pop();
};

/**
 * Get the front element.
 * @return {number}* /
MyQueue.prototype.peek = function () {
  if (this.outStack.length) {
    return this.outStack[this.outStack.length - 1];
  }
  while (this.inStack.length) {
    this.outStack.push(this.inStack.pop());
  }
  return this.outStack.length && this.outStack[this.outStack.length - 1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}* /
MyQueue.prototype.empty = function () {
  return !this.outStack.length && !this.inStack.length;
};

Copy the code

Notice here that although there may be cycles in the extraction, the amortized time complexity is actually O(1), which can be simply interpreted as most of the extraction is O(1).

The official solution

Exercise: Double-endian queue

A double-ended queue is a queue that allows inserts and deletions at both ends of the queue.

In terms of encoding, the most common vectors are arrays that allow pop and push as well as Shift and unshift.

General method: cycle, find the maximum value of each window, time complexity O(kN).

So, again, space for time, two-way queue, order n.

The first queue is always the index of the maximum value of the current window. The queue is a decrement queue, after storing the index, advancing the value, to determine whether the head of the queue is outside the window, the other is removed. After removal, the new queue head is the maximum value of the current window.

Steps:

  • Iterate over the elements in the given array,
  • If the queue is not empty and the current value>The tail element is removed. The current value is not pushed into the queue until the queue is empty or the current value is less than the new end-of-queue element;
  • Subscript of the element at the head of the queue<When the left boundary of the current window is L, it indicates that the element of the head of the queue is no longer in the sliding window and needs to be removed from the head of the queue.
  • At this point, the header element is the maximum value in the window. But since the array subscript starts at 0, only when the window is bounded to the rightR>=k-1, means the window is formed, pay attention to this prerequisite.

Demos and ideas are elements, but in real code, for ease of operation, queues store indexes.

const last = (arr) = > arr[arr.length - 1];
const first = (arr) = > arr[0];
var maxSlidingWindow = function (nums, k) {
  // Store an array of maximum values
  let res = [];
  // decrement the queue
  let queue = [];
  R represents the right edge of the sliding window
  for (let R = 0; R < nums.length; R++) {
    const cur = nums[R];
    // Maintain the decrement queue, pop as long as the current value is greater than the end of the queue, until less than or empty before entering the queue
    while (queue.length && cur > nums[last(queue)]) {
      queue.pop();
    }
    queue.push(R);
    // The pointer index to the left of the window
    const L = R - k + 1;
    // The queue header index is less than L, indicating that it is outside the window and needs to be removed
    if (first(queue) < L) {
      queue.shift();
    }
    // when R>=k-1, the window is formed, and the column header is the maximum index, which is stored in res
    if (R >= k - 1) { res[L] = nums[first(queue)]; }}return res;
};
Copy the code

Detailed diagrams and other official programs

reference

  • The front-end algorithm and data structure of xiuyan