Implement queue with stack (Question 232)

The title

Implement the FIRST in, first out queue using only two stacks. The queue should support all the operations that a normal queue supports (push, pop, peek, empty) :

Implement the MyQueue class:

  • void push(int x)The elementxPush to the end of the queue
  • int pop()Removes and returns the element from the beginning of the queue
  • int peek()Returns the element at the beginning of the queue
  • boolean empty()If the queue is empty, returntrue; Otherwise, returnfalse

Description:

You can only use standard stack operations — that is, only push to top, peek/pop from top, size, and is empty are legal. The language you are using may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.

Advanced:

Can you amortize a queue of O(1) per operation? In other words, the total time complexity of performing n operations is O(n), even though one of the operations may take a long time.

Example:

Input: [" MyQueue ", "push" and "push" and "peek", "pop", "empty"] [[], [1], [2], [], [], []] output: [null, null, null, 1, 1, false] MyQueue MyQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return falseCopy the code

Tip:

  • 1 <= x <= 9
  • Most call100 次 push,pop,peek 和 empty
  • Assume that all operations are valid (for example, an empty queue is not calledpoporpeekOperation)

link

Leetcode-cn.com/problems/im…

explain

There’s nothing to explain, because the array is all integrated, so it’s basically the definition of the queue, first in first out, last in last out, as long as you’re clear about the concept, just call the native method of the array

The solution

/** * Initialize your data structure here. */ var MyQueue = function() { this.arr = [] }; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { this.arr.push(x) }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop =  function() { // console.log(this.arr.pop()) // console.log(this.arr) return this.arr.shift() }; /** * Get the front element. * @return {number} */ MyQueue.prototype.peek = function() { return this.arr.length > 1 ? this.arr[0] : null }; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function() { console.log(this.arr) return this.arr.length === 0 }; /** * Your MyQueue object will be instantiated and called as such: * var obj = new MyQueue() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.peek() * var param_4 = obj.empty() * /Copy the code

Implementing stacks with queues (Question number 225)

The title

You implement a last in, first out (LIFO) stack with only two queues and support all four operations of a normal queue (push, top, pop, and Empty).

Implement the MyStack class:

  • void push(int x)The elementxPush the top of the stack.
  • int pop()Removes and returns the top stack element.
  • int top()Returns the top element on the stack.
  • boolean empty()If the stack is empty, returntrue; Otherwise, returnfalse 。

 

Note:

You can only use the basic operations of the queue — push to back, peek/pop from front, size, and is Empty. Your language may not support queues. You can use a list or deque to simulate a queue, as long as it’s a standard queue operation.

Example:

Input: [" MyStack ", "push" and "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] output: Null, null, null, 2, 2, false) MyStack MyStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // Return 2 mystack.pop (); // Return 2 myStack.empty(); / / returns FalseCopy the code

Tip:

  • 1 <= x <= 9
  • A maximum of 100 callspush,pop,top 和 empty
  • Each callpop 和 topMake sure the stack is not empty

 

Advanced: Can you achieve an O(1) stack for each operation? In other words, the total time complexity of performing N operations is O(n), although one of them may take longer than the others. You can use more than two queues.

link

Leetcode-cn.com/problems/im…

explain

There’s nothing to explain, because the arrays are all integrated, so it’s basically the stack definition, first in last out, last in first out, as long as you understand the concept, just call the native method of the array.

The solution

/**
 * Initialize your data structure here.
 */
var MyStack = function() {
  this.arr = []
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
  this.arr.push(x)
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
  return this.arr.pop()
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
 return this.arr[this.arr.length - 1]
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
  return this.arr.length === 0
};

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */
Copy the code




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ