“This is the 26th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

This article introduces two primary algorithm questions: rush ~~

  • Implement queues with two stacks

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)

Example 1: input: [" CQueue ", "appendTail", "deleteHead", "deleteHead"] [[], [3], [], []] output: [3, null, null, 1] example 2: input: [" CQueue deleteHead ", ""," appendTail ", "appendTail", "deleteHead", "deleteHead"] [[], [], [5], [2], [], []] output: [null, 1, null, null, 5, 2]Copy the code

Answer:

Stack is last in first out, queue is first in first out, so we might as well set up a queue in the stack and a queue out

In the queue directly into the queue stack, out of the queue check whether the stack is empty, if it is empty, need to first into the queue stack out of the queue operation, otherwise directly out of the queue;

The JavaScript implementation is as follows:

var CQueue = function() { this.stackA = []; this.stackB = []; }; /** * @param {number} value * @return {void} */ CQueue.prototype.appendTail = function(value) { this.stackA.push(value);  }; /** * @return {number} */ CQueue.prototype.deleteHead = function() { if (this.stackB.length) { return this.stackB.pop();  } else { while (this.stackA.length) { this.stackB.push(this.stackA.pop()); } if (! this.stackB.length) { return -1; } else { return this.stackB.pop(); }}};Copy the code
  • The stack containing the min function

Define the data structure of the stack. Please implement a min function in this type that can get the smallest element of the stack. In this stack, the time complexity of calling min, push and pop is O(1).

Example: MinStack MinStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> return -3.minstack.pop (); minStack.top(); --> return 0. Minstack.min (); -- -- > to return to 2.Copy the code

Answer:

The topic:

  1. Push (x) – Pushes element X onto the stack.

  2. Pop () — Removes the top element of the stack.

  3. Top () — Gets the top element on the stack.

  4. GetMin () — Retrieves the smallest element in the stack.

  5. Operations like regular apipush and pop operate on the stack and print null directly;

  6. Top and min require us to sort the stack ourselves and output the elements as the problem asks

The JavaScript implementation is as follows:

/** * initialize your data structure here. */ var MinStack = function() { this.stack = [] }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { this.stack.push(x) }; /** * @return {void} */ MinStack.prototype.pop = function() { return this.stack.pop() }; /** * @return {number} */ MinStack.prototype.top = function() { return this.stack[this.stack.length - 1] }; /** * @return {number} */ MinStack.prototype.min = function() { let array = JSON.parse(JSON.stringify(this.stack)) array  = array.sort((a,b)=>a - b) // console.log("array:", array,',stack:', this.stack) return array[0] };Copy the code

OK, that’s it

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~~