栈
栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
栈数据结构
我们需要一种数据结构来保存栈里的元素。可以选择数组。数组允许我们在任何位置添加或删除元素。由于栈遵循 LIFO 原则，需要对元素的插入和删除功能进行限制。下面基本使用js实现一些栈的方法：
- push(element(s))：添加一个（或几个）新元素到栈顶。
- pop()：移除栈顶的元素，同时返回被移除的元素。
- peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。
- isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
- clear()：移除栈里的所有元素。
- size()：返回栈里的元素个数。该方法和数组的length属性很类似
class Stack{
constructor(){
this.items = []
}
push(ele){
this.items.push(ele)
}
pop(){
return this.items.pop()
}
peek(){
return this.items[this.items.length-1]
}
isEmpty(){
return this.items.length===0
}
size(){
return this.items.length
}
clear(){
this.items=[]
}
}
到这，我们基本对栈的数据结构及其方法都有了比较清晰的认识，下面直接进行实现联系吧。
leetcode应用
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
- 思路：首先如果字符串能组成有效的括号，则长度一定是偶数，我们可以遍历字符串，遇到左括号则暂存，期待后面有右括号可以和它匹配，如果遇到右括号则检查是否能和最晚暂存的做括号匹配。这就和栈这种数据结构先进后出的特性相吻合了。所以我们可以准备一个栈存放括号对，遍历字符串的时候，如果遇到左括号入栈，遇到右括号则判断右括号是否能和栈顶元素匹配，在循环结束的时候还要判断栈是否为空，如果不为空，则不是有效括号匹配的字符串
- 复杂度分析：
- 时间复杂度：O(n)，其中 nn是字符串 s 的长度。
- 空间复杂度：O(n + ∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度
var isValid = function(s) {
const n = s.length;
if (n % 2 === 1) {//如果字符串能组成有效的括号，则长度一定是偶数
return false;
}
const pairs = new Map([//用栈存储括号对
[')', '('],
[']', '['],
['}', '{']
]);
const stk = [];
for (let ch of s){//循环字符串
if (pairs.has(ch)) {
//遇到右括号则判断右括号是否能和栈顶元素匹配
if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
return false;
}
stk.pop();
} else {
stk.push(ch);//如果遇到左括号入栈
}
};
return !stk.length;//循环结束的时候还要判断栈是否为空
};
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。
var MyQueue = function () {
//准备两个栈
this.stackIn = [];
this.stackOut = [];
};
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
this.stackIn.push(x);
};
/**
* @return {number}
*/
MyQueue.prototype.pop = function () {
// pop的时候判断输出栈是否为空
const size = this.stackOut.length;
if (size) return this.stackOut.pop(); //不为空则输出栈出栈
while (this.stackIn.length) { //输出栈为空，则把输入栈所有的元素加入输出栈
this.stackOut.push(this.stackIn.pop());
}
return this.stackOut.pop();
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function () {
//查看队头的元素 复用pop方法，由于元素已经从输出栈pop，需要再次push到输出栈
const x = this.pop();
this.stackOut.push(x);
return x;
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
return !this.stackIn.length && !this.stackOut.length
};
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
-
MinStack() 初始化堆栈对象。
-
void push(int val) 将元素val推入堆栈。
-
void pop() 删除堆栈顶部的元素。
-
int top() 获取堆栈顶部的元素。
-
int getMin() 获取堆栈中的最小元素。
- 思路：定义两个栈stack和min_stack，stack正常push，min_stack只会push需要入栈和min_stack栈顶中较小的元素，这样每次删除min_stack均可以保证其栈顶元素为最小值。getMin返回min_stack栈顶元素，top返回stack栈顶元素。
- 复杂度分析
- 时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。
- 空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。
var MinStack = function() {
this.stack = [];
this.min_stack = [Infinity];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val);
// min_stack只会push需要入栈和栈顶中较小的元素
this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], val));
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.stack.pop();
this.min_stack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
// 返回stack栈顶元素
return this.stack[this.stack.length - 1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
// 返回min_stack栈顶元素
return this.min_stack[this.min_stack.length - 1];
};
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
提示：
1 <= pushed.length <= 10000 <= pushed[i] <= 1000-
pushed 的所有元素 互不相同
popped.length == pushed.length-
popped 是 pushed 的一个排列
- 思路：用栈模拟出栈入栈的过程，当
popped中index指向的位置的元素和stack栈顶的元素一致时，出栈且 index++，最后判断stack是否完全遍历popped。
- 复杂度分析：
- 时间复杂度
O(n)，pushed中的元素入栈出栈一次；
- 空间复杂度
O(n)
/**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function(pushed, popped) {
const stack = [];//用栈模拟出栈入栈的过程
let index = 0;
const len = pushed.length;
for (let i = 0; i < len; i++) {
stack.push(pushed[i]);
//当popped中index指向的位置的元素和stack栈顶的元素一致时，出栈 并且 index++
while (stack.length && index<len && popped[index] === stack[stack.length - 1]) {
stack.pop();
index++;
}
}
return index === len; // 最后判断 index是否完全遍历popped
};
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
提示：
- 链表的长度范围为
[1, 100]
0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
var addTwoNumbers = function(l1, l2) {
const stack1 = [];
const stack2 = [];
while (l1 || l2) {//两链表入栈
if (l1) {
stack1.push(l1.val);
l1 = l1.next;
}
if (l2) {
stack2.push(l2.val);
l2 = l2.next;
}
}
let carry = 0;
let ansList = null;
while (stack1.length || stack2.length || carry !== 0) {//不断出栈
const s1 = stack1.length ? stack1.pop() : 0;
const s2 = stack2.length ? stack2.pop() : 0;
let val = s1 + s2 + carry;
carry = parseInt(val / 10);//计算进位
val = val % 10;//计算当前节点的值
const curNode = new ListNode(val);
curNode.next = ansList;//向链表前插入新节点
ansList = curNode;//重新赋值ansList
}
return ansList;
};
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
- 整数
x - 表示本回合新获得分数 x
-
"+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
-
"D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
-
"C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
/**
* @param {string[]} ops
* @return {number}
*/
var calPoints = function (ops) {
let ans = []
for (let i = 0; i < ops.length; i++) {
switch(ops[i]) {
case 'C':
ans.pop();
break;
case 'D':
ans.push(+ans[ans.length - 1] * 2);
break;
case '+':
ans.push(+ans[ans.length - 1] + +ans[ans.length - 2]);
break;
default:
ans.push(+ops[i])
}
}
return ans.reduce((a, b) => a + b, 0);
};
