Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push
, peek
, pop
, and empty
).
Implement the MyQueue
class:
void push(int x)
Pushes element x to the back of the queue.int pop()
Removes the element from the front of the queue and returns it.int peek()
Returns the element at the front of the queue.boolean empty()
Returns true
if the queue is empty, false
otherwise.Notes:
push to top
, peek/pop from top
, size
, and is empty
operations are valid.1 <= x <= 9
100
calls will be made topush
, pop
, peek
, and empty
.pop
and peek
are valid.var MyQueue = function() {
this.queue = [];
};
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
this.queue.push(x);
};
/**
* @return {number}
*/
MyQueue.prototype.pop = function() {
return this.queue.shift();
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
return this.queue[0];
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
return this.queue.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()
*/
pushed
and popped
each with distinct values, return true
if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false
otherwise.Example 1:
Example 2:
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed
are unique.popped.length == pushed.length
popped
is a permutation of pushed
./**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function(pushed, popped) {
const stack = [pushed[0]];
let pushedIndex = 1;
for (const poppedNumber of popped) {
while (pushedIndex < pushed.length && poppedNumber !== stack[stack.length - 1]) {
stack.push(pushed[pushedIndex]);
pushedIndex++;
}
if (poppedNumber === stack[stack.length - 1]) {
stack.pop();
}
}
return stack.length === 0;
};
var validateStackSequences = function(pushed, popped) {
const stack = [];
let poppedIndex = 0;
for (const pushedNumber of pushed) {
stack.push(pushedNumber);
while (stack.length && stack[stack.length - 1] === popped[poppedIndex]) {
stack.pop();
poppedIndex++;
}
}
return pushed.length === poppedIndex;
}
s
consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.We repeatedly make duplicate removals on s
until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Example 1:
Example 2:
1 <= s.length <= 10^5
s
consists of lowercase English letters./**
* @param {string} s
* @return {string}
*/
var removeDuplicates = function(s) {
const stack = [];
for (let i = 0; i < s.length; i++) {
const str = s[i];
if (stack.length && stack[stack.length - 1] === str) {
stack.pop();
} else {
stack.push(str);
}
}
return stack.join('');
};