基本数据结构

队列

特点：先进先出

class Queue {
  constructor() {
    this.dataSource = [];
  }
  enqueue(ele) {
    this.dataSource.push(ele);
  }
  dequeue() {
    return this.dataSource.shift();
  }
  back() {
    return this.dataSource[this.dataSource.length - 1];
  }
  font() {
    return this.dataSource[0];
  }
  isEmpty() {
    return this.dataSource.length === 0;
  }
  toString() {
    return this.dataSource.toString();
  }
}
const queue = new Queue();
queue.enqueue('guan');
queue.enqueue('qing');
queue.enqueue('chao');
console.log(queue.toString());
console.log(queue.dequeue());

栈

特点：先进后出

class Stack {
  constructor() {
    this.dataSource = [];
  }
  push(ele) {
    this.dataSource.push(ele);
  }
  pop() {
    return this.dataSource.pop();
  }
  //获取栈顶元素
  peek() {
    return this.dataSource[this.dataSource.length - 1];
  }
  clear() {
    this.dataSource.length = 0;
  }
  length() {
    return this.dataSource.length;
  }
  toString() {
    return this.dataSource.toString();
  }
  isEmpty(){
    return this.dataSource.length===0;
  }
}
const stack = new Stack();
stack.push('guan');
stack.push('qing');
stack.push('chao');
console.log(stack.toString());
console.log(stack.pop());
console.log(stack.peek());

练习题目

循环队列

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

//case: ()[]{}
// 思路: 遇到左括号push相应的右括号,右括号，判断栈顶元素是否跟当前右括号相等
var isValid = function(s) {
    var stack = new Stack();
    for(var i = 0; i<s.length; i++){
        //碰到左括号，push右括号
        if(s[i] === "(") {
            stack.push(")");
        } else if(s[i] === "[") {
            stack.push("]");
        } else if(s[i] === "{") {
            stack.push("}");
        } else{
        //不是左括号，判断栈是否为空或栈顶元素是否等当前元素
            if(!stack.isEmpty || stack.peek() != s[i]){
                return false
            }else{
                stack.pop()
            }
        } 
    }
    return !stack.top;
};

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

思路：定义两个栈 smain， smin， smin栈顶始终是最小元素，同时进行push pop 操作

var MinStack = function() {
    this.smain = [];
    this.smin = [];
};
/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    var smain = this.smain;
    var smin = this.smin;
    smain.push(x);
    if (smin.length === 0) {
        smin.push(x);
    } else if (x < smin[smin.length-1]) {
        smin.push(x);
    }
    else {
        smin.push(smin[smin.length-1]);
    }
};
/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    var smain = this.smain;
    var smin = this.smin;
    smain.pop();
    smin.pop();
};
/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    var smain = this.smain;
    // var smin = this.smin;
    return smain[smain.length-1];
};
/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
        // var smain = this.smain;
    var smin = this.smin;
    return smin[smin.length-1];
};

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路：用两个栈来实现队列

// 使用两个数组的栈方法（push, pop） 实现队列
/**
* Initialize your data structure here.
*/
var MyQueue = function() {
   this.stack1 = [];
   this.stack2 = [];
};
/**
* Push element x to the back of queue. 
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
   this.stack1.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function() {
   const size = this.stack2.length;
   if(size) {
       return this.stack2.pop();
   }
   while(this.stack1.length) {
       this.stack2.push(this.stack1.pop());
   }
   return this.stack2.pop();
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function() {
   const x = this.pop();
   this.stack2.push(x);
   return x;
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
   return !this.stack1.length && !this.stack2.length
};

https://labuladong.github.io/algo/2/20/51/

var MyStack = function() {
    this.stack = []
}

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

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
    const remove = this.stack[this.stack.length - 1]
    this.stack.length -= 1
    return remove
}

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

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    if (this.stack.length === 0) {
        return true
    } else {
        return false
    }
}

/**
 * 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()
 */

数据结构与算法

队和栈

基本数据结构

队列

栈

练习题目

循环队列

有效的括号

最小栈

232. 用栈实现队列