栈

栈和队列一、对于模仿栈应用何种模型 1.程序表：尾插尾删很快，缓存利用率高，然而要扩容 2.单链表：应用链表头作为栈顶来插入删除数据也很快 3.带头双向循环链表：也能够，工夫也是O(1) 二、栈的模仿实现 //"stack.h"typedef int type;typedef struct stack{ type* a; int top; int capacity;}st;//stack.c#include"stack.h"void st_init(st* sta){ assert(sta); sta->a = NULL; sta->top = 0;//数组下标的意思，是数据下一个下标，外面没有值;top = -1,则是top指向最初一个元素 sta->capacity = 0;}void st_push(st* sta, type x){ assert(sta); if (sta->top == sta->capacity) { //满了 int newcapa = sta->capacity == 0 ? 4 : 2 * sta->capacity; type* t = realloc(sta->a, sizeof(type) * newcapa);//扩容；如果a== NULL，它的行为就和malloc一样 if (t == NULL) { printf("realloc fail\n"); exit(-1); } sta->a = t; sta->capacity = newcapa; } sta->a[sta->top] = x; ++sta->top;}void st_destroy(st* sta){ assert(sta); free(sta->a); sta->a = NULL; sta->top = 0; sta->capacity = 0;}void st_pop(st* sta){ assert(sta); assert(sta->top > 0); sta->top--;}type st_top(st* sta){ assert(sta); assert(sta->top > 0); return sta->a[sta->top - 1];}bool st_empty(st* sta){ assert(sta); return sta->top == 0;}int st_size(st* sta){ assert(sta); return sta->top; }三、根底oj ...

如果在一个黑盒的测试过程中，咱们无奈通过debug的形式来单步调试程序，那么怎么能力晓得一个对象的值呢？通过print函数进行打印。对应的java语法就是： System.out.println(obj);对于一个对象或者一个数组对象是很容易通过打印或者遍历之后打印对象的值。那么对于栈的数据结构怎么遍历呢？认为遍历之后，栈中的每一个元素都要弹出栈，咱们须要弹出之后再进行压栈的操作。那么有没有简略的形式进行操作呢？能够的！办法就是通过copy栈中的数据，再遍历。那么有没有clone函数呢？我是没有找到(能够在钻研下)。另外一个形式就是开拓一个新的空间，把栈当做对象增加到新的栈空间中。 public void printStack(Stack<TreeNode> stack){ Stack<TreeNode> copy = new Stack<>(); copy.addAll(stack); while(!copy.isEmpty()){ System.out.println(copy.pop().val); }}public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }}

栈的应用习惯零碎在应用栈开拓内存空间时，是先应用高地址处的空间，而后在应用低地址处的空间。数组、函数传参等，开拓内存空间时，都是从右到左顺次开拓的。//下列这个程序会死循环int main(){ int i = 0; //先在栈的高地址开拓b的空间， int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; //而后在低地址开拓arr的空间（先开拓10的空间，而后再是9、8 ....） for (i = 0; i <= 12; i++) { arr[i] = 0; printf("hehehe\n"); } return 0;}//上述程序中，for循环中 arr[i] 的拜访溢出了（越界拜访），溢出到arr[12]的地址//然而arr[12]的地址可能与变量 i 重合了//所以给arr[12]的地址赋值为0，同时也会把变量 i 也赋值为0栈中内存构造如下：

1.栈是只运行在一端操作的线性表。n个元素进栈，出栈元素不同排列个数为2n!/n!/(n+1) 一般栈：#define Maxsize 10typedef struct{ ElemType data[Maxsize]; int top;......栈顶指针，因为栈实质上是数组，所以指针能够简化为一个数}Sqstack;共享栈：typedef struct{ ElemType data[Maxsize]; int top0; int top1;}Shstack;void InitStack(Shstack &S){ S.top0=-1; S.top1=Maxsize;}栈满条件：top0+1=top12.队列是在一端进，一端出的线性表 #define Maxsize 10typedef struct{ ElemType data[Maxsize]; int front,rear;}SqQueue;3.队列的插入与删除因为队列波及到来头尾的问题，所以为了运算不便，咱们应用模运算将队列在逻辑上变为环形 bool EnQueue(SqQueue &Q,Elemtype x){ if((Q.rear+1)%MaxSize==Q.front) return false; Q.data[Q.rear]=x; Q.rear=(Q.rear+1)%Maxsize; return true;}bool DeQueue(SqQueue &Q,Elemtype &x){ if(Q.rear+1==Q.front) return false; Q.data[Q.front]=x; Q.front=(Q.front+1)%Maxsize; return true;}4.判断队列空满的形式计划一：就义了一个存储空间（即rear指向的那个地位） 计划二： 计划三： 5.其余出题形式 有时rear指向的是队尾元素所在位置（起始时rear=front=0)（后面所写代码和判断形式均建设在这种形式上），有时指向的是队尾元素的下一个地位(起始时rear=n-1,front=0) 前一种：Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%Maxsize;后一种：Q.rear=(Q.rear+1)%Maxsize;Q.data[Q.rear]=x;然而对于后一种，咱们不能通过（Q.rear+1)%MaxSize==Q.front判断队满，因为它的队空是这样判断的，因而咱们能够就义一个存储单元，即当rear=n-2,front=0时就队满，或者通过设置size来判断

栈先入后出 栈的利用如果数据保留的程序和应用程序相同，那么最初保留的数据最先被应用，具备“后入先出”的特点，所以能够思考将数据保留到栈中。 后缀表达式题目：后缀表达式是一种算术表达式，它的操作符在操作数的前面。输出一个用字符串数组示意的后缀表达式，请输入该后缀表达式的计算结果。假如输出的肯定是无效的后缀表达式。例如，后缀表达式["2"，"1"，"3"，""，"+"]对应的算术表达式是“2+13”，因而输入它的计算结果5。/** * @param {string[]} tokens * @return {number} */var evalRPN = function(tokens) { let stack = [] for(const token of tokens) { switch(token) { case "+": case "-": case "*": case "/": let num1 = stack.pop(); let num2 = stack.pop(); stack.push(calculate(num2, num1, token)) break; default: stack.push(Number(token)) } } return stack.pop()};var calculate = function(num1, num2, operator) { switch(operator) { case "+": return num1 + num2; case "-": return num1 - num2; case "*": return num1 * num2; case "/": return num1 / num2 > 0 ? Math.floor(num1 / num2) : Math.ceil(num1 / num2); }}小行星碰撞题目：输出一个示意小行星的数组，数组中每个数字的绝对值示意小行星的大小，数字的正负号示意小行星静止的方向，正号示意向右航行，负号示意向左航行。如果两颗小行星相撞，那么体积较小的小行星将会爆炸最终隐没，体积较大的小行星不受影响。如果相撞的两颗小行星大小雷同，那么它们都会爆炸隐没。航行方向雷同的小行星永远不会相撞。求最终剩下的小行星。例如，有6颗小行星[4，5，-6，4，8，-5]，如图6.2所示（箭头示意航行的方向），它们相撞之后最终剩下3颗小行星[-6，4，8]。var asteroidCollision = function(anteroids) { const stack = []; for(let i = 0; i < anteroids.length; i++) { while(stack.length && stack[stack.length-1] > 0 && stack[stack.length-1]<-anteroids[i]) { stack.pop() } if(stack.length && anteroids[i] < 0 && stack[stack.length-1] == -anteroids[i]) { stack.pop() } else if (!stack.length || anteroids[i]>0 || stack[stack.length-1] < 0) { stack.push(anteroids[i]) } } return stack;}每日温度题目：输出一个数组，它的每个数字是某天的温度。请计算每天须要等几天才会呈现更高的温度。例如，如果输出数组[35，31，33，36，34]，那么输入为[3，1，1，0，0]。因为第1天的温度是35℃，要等3蠢才会呈现更高的温度36℃，因而对应的输入为3。第4天的温度是36℃，前面没有更高的温度，它对应的输入是0。其余的以此类推。暴力法// 写错了，搞成最高温度var dailyTemperatures(temperatures) { let result = [] for(let i = 0; i < temperatures.length; i++) { let max = 0; let count = 0; for(let j = i + 1; j < temperatures.length; j++) { if(temperatures[j]-temperatures[i]>max) { count = j - i } max = Math.max(max, temperatures[j]-temperatures[i]) } result.push(count) } return result;}栈/** * @param {number[]} temperatures * @return {number[]} */var dailyTemperatures = function(temperatures) { const result = new Array(temperatures.length).fill(0) const stack = [] for(let i = 0; i < temperatures.length; i++) { while(stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) { let prev = stack.pop(); result[prev] = i - prev } stack.push(i); } return result;};假如输出数组的长度为n。尽管上述代码中有一个嵌套的二重循环，但它的工夫复杂度是O（n），这是因为数组中每个温度入栈、出栈各1次。这种解法的空间复杂度也是O（n）。 ...

栈定义// 线性表的一种，构造上一端凋谢、一端关闭// 凋谢的一端，容许进行插入和删除操作，称为栈顶// 关闭的一端，成为栈底// 依据定义写出栈的结构构造体(假设栈中都是整型元素)type Stack struct { // 一个寄存栈元素的容器 container []int // 栈顶标记 top int // 容量限度 size int}// 依据构造体写出栈的构造方法func NewStack(size int) *Stack { // 返回的是Stack构造体指针 return &Stack{ // 用切片来示意栈容器 container: make([]int, size), // 初始栈顶元素为0 top: 0, // 容量限度同入参size size: size, }}基本操作栈判空：栈顶标记为零栈判满：栈顶标记等于容量限度入栈：把某一元素放入栈顶出栈：把栈顶元素取出// 栈判空func (s *Stack) IsEmpty() bool { if s.top == 0 { return true } return false}// 栈判满func (s *Stack) IsFull bool { if s.top == s.size { return true } return false}// 入栈func (s *Stack) Push(e int) bool { if s.IsFull() { fmt.Println(false, e) return false } s.container[s.top] = e s.top++ fmt.Println(true, e) return true}// 出栈func (s *Stack) Pop() (flag bool, ret int) { if s.IsEmpty() { return false, ret } ret = s.container[s.top] s.top-- return true, ret}测试func main() { s := NewStack(5) s.Push(1) s.Push(2) s.Push(3) s.Push(4) s.Push(5) s.Push(6) fmt.Println(s.Pop()) fmt.Println(s.Pop()) fmt.Println(s.Pop()) fmt.Println(s.Pop()) fmt.Println(s.Pop()) fmt.Println(s.Pop())}// 运行后果true 1true 2true 3true 4true 5false 6true 5true 4true 3true 2true 1false 0

1. 什么是栈(Stack)栈是一种数据结构。要阐明栈的定义，咱们须要从栈的个性说起，只有合乎这种个性的数据结构就能够叫做栈。 上面咱们来看看栈的个性是什么。 栈的个性是存入栈中的元素先进后出。先进后出是什么意思呢？ 咱们思考有一个桶，桶有5层，每层只能放一个球，并且只有桶的最下面有个闭口用来放球和拿球。 当初假如咱们有三个球叫A,B,C，桶也是空的。 咱们依照A,B,C的先后顺序把球放进桶里，那么此时的桶外面的球的排布如下： 第五层 | | 第四层 | | 第三层 | C | 第二层 | B | 第一层 | A | 此时咱们再从桶里逐个把球拿进去。首先只能拿C球，把C球拿掉后能力拿B球，而后才是A球。 依据以上场景，咱们能够晓得放球程序是A,B,C；拿球程序是C,B,A。 即后面所说的栈的个性：先进后出，并且栈只提供栈顶供咱们放元素和取元素。 2. java实现栈能够通过链表实现，也能够通过数组实现。 背刺抉择双链表作为实现栈的载体。 对于链表以及双链表的实现，能够参考以前的文章： Segment Fault Bugkit package org.bugkit.structure;/** * @author bugkit * @since 2021.10.27 */public class LinkedList<E> extends AbstractList<E> implements List<E>, Queue<E>, Stack<E> { private Node<E> head; private Node<E> tail; // 创立一个空栈 public LinkedList() { tail = head = null; } // 放入元素到栈中 @Override public boolean push(E e) { Node<E> node = new Node<>(e); if (isEmpty()) { tail = head = node; }else{ node.prev = tail; tail.next = node; tail = node; } size++; return true; } // 取出栈中的一个元素 @Override public E pop() { if (isEmpty()) { throw new RuntimeException("Stack is empty"); } E e = tail.e; if (size() == 1) { tail = head = null; }else{ tail = tail.prev; tail.next = null; } size--; return e; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("LinkedList: { "); Node<E> node = head; while (node != null) { sb.append(node.e).append("<->"); node = node.next; } sb.append("null }"); return sb.toString(); } private static class Node<E> { E e; Node<E> next; Node<E> prev; public Node(E e) { this.e = e; } }}

需要：实现一个“智能反复”函数，实现上面字符串的转换 将 2[abc] 转成 abcabc 将 2[1[a]2[b]] 转成 abbabb 将 2[1[a]2[3[b]4[c]]] 转成 abbbccccbbbccccabbbccccbbbcccc思路及原理原理：应用“栈”思维来实现，在JavaScript中实现“栈”的最好数据结构是数组思路： 1、定义两个栈（数组），栈1（stack1）、栈2（stack2），stack1用来存储数字，stack2用来存储字符串2、定义一个指针（索引），默认从0开始3、循环这个字符串，指针始终向后挪动，直到指针等于字符串长度减14、获取以后指针指向的这个字符，而后进行判断 a）、如果是数字 stack1中推入这个数字，stack2中推入一个空字符，指针持续向后挪动b）、如果是“[” 什么都不做，指针持续向后挪动c）、如果是字符串将stack2栈顶项批改为该字符串，指针持续向后挪动d）、如果是“]” stack1栈顶数字弹出，失去须要反复的次数，起个名字叫：repeatCountstack2栈顶空字符串弹出将stack2栈顶项批改为：tack2栈顶项 + 反复repeatCount后的字符串指针持续向后挪动用一涨动图来演示 代码实现function smartRepeat(template){ let stack1 = []; // 寄存数字 let stack2 = []; // 寄存字符串 let index = 0; // 指针 let remaining = template; // 残余局部 // 这里index要小于template.length - 1，当遇到最初一个“]”的时候就不须要再出栈了，因为此时数组长度为1了，此时出栈再获取数组最初一项的值就会变成undefined while (index < template.length - 1){ if(/(^\d+)\[/.test(remaining)){ // 如果是数字。因为xxx]里的xxx数字前面肯定是“]”，如果不加上“]”，那么在匹配的时候很可能会将要循环的字符串误匹配为数字 let countStr = RegExp.$1; // RegExp.$1获取的就是/(^\d+)/这个正则中括号分组中匹配到的内容 let len = countStr.length; stack1.push(countStr * 1); stack2.push(''); index += len; remaining = remaining.substr(len); console.log('推入数字：', countStr * 1); console.log('stack1', stack1); console.log('stack2', stack2); } else if(remaining.charAt(0) == '['){ // 如果是“[” index++; remaining = remaining.substr(1); console.log('推入空字符串：'); console.log('stack1', stack1); console.log('stack2', stack2); } else if(/^(\w+)\]/.test(remaining)) { // 如果是字符串。因为[xxx]里的xxx能够是数字、字母或数字字母的组合，并且他们前面肯定是“]”，所以这里的正则须要加上“]” let chats = RegExp.$1; let stack2LastStr = stack2[stack2.length - 1]; stack2[stack2.length - 1] = stack2LastStr + chats; index += chats.length; remaining = remaining.substr(chats.length); console.log('推入字符串：', chats); console.log('stack1', stack1); console.log('stack2', stack2); } else if(remaining.charAt(0) == ']') { // 如果是“]”，需出栈 let repeatCount = stack1.pop(); let needRepeatStr = stack2.pop(); console.log('出栈，两个栈顶：', repeatCount, needRepeatStr); let resultStr = needRepeatStr.repeat(repeatCount); // 后果字符串 let stack2LastStr = stack2[stack2.length - 1]; stack2[stack2.length - 1] = stack2LastStr + resultStr; index++; remaining = remaining.substr(1); console.log('出栈，后果字符串：', resultStr, stack2LastStr); console.log('stack1', stack1); console.log('stack2', stack2); } else { index++; remaining = remaining.substr(1); } } console.log('循环实现--------------', index); console.log('stack1', stack1); console.log('stack2', stack2); let repeatCount = stack1.pop(); let needRepeatStr = stack2.pop(); let resultStr = needRepeatStr.repeat(repeatCount); // 后果字符串 console.log('最终后果字符串：', resultStr); return resultStr;}// 输入后果：abcabcsmartRepeat('2[abc]');// 输入后果：abbabbsmartRepeat('2[1[a]2[b]]');// 输入后果：abbbccccbbbccccabbbccccbbbccccsmartRepeat('2[1[a]2[3[b]4[c]]]');// 输入后果：1ab2b2b2ccccb2b2b2cccc1ab2b2b2ccccb2b2b2ccccsmartRepeat('2[1[1a]2[3[b2]4[c]]]');

LeetCode第84题，使用枯燥递增栈求柱状图的最大面积，这个思维还是很奇妙的，记录下解题思路。 先看下题： 给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，可能勾画进去的矩形的最大面积。 示例: 输出: [2,1,5,6,2,3]输入: 10 其实我没看题解之前我是齐全懵逼，间接用暴力法求解，而后超时。前面看完题解之后才意识到既然还能用栈去解，想出这个解法的人真的对栈这种数据结构了解的太通透了。 然而当你看懂其实思路还是很简略的。 请跟着我的思路一起看下这个后果是怎么进去的，要求柱状图面积，那肯定须要晓得左右边界和高度，咱们先手动保护一个枯燥递增的栈。这个栈能有什么用呢？ 它会有一个个性，当第一个小于栈顶元素呈现时，咱们能算出栈里所有比以后元素大的以栈顶元素为右边界的这个柱子的最大面积，左边界怎么算呢，就是第二个栈顶元素+1，高度就是左右边界的最小高度。值为什么能这么算呢，因为栈是递增的，如果有比第二个栈顶元素小的元素时，它肯定是被弹出去了。（这个可能有点不那么好思考，倡议多写几遍或者debug一下） 接下来看下代码： int len = heights.length;int maxArea = 0;Stack<Integer> stack = new Stack<>();//这里能等于n的起因是当i=n-1的时候栈里还会有最初一个元素，因而须要结构一个最小的n把栈里残余其余元素拿进去for (int i = 0; i <= len;) { //等于n须要非凡解决 int h = (i == len ? 0 : heights[i]); //保护一个枯燥递增栈，如果压栈元素比栈顶元素大，间接压入栈中，否则顺次将比它大的元素取出 if (stack.isEmpty() || h >= heights[stack.peek()]) { stack.push(i); i++; }else { int curHeight = heights[stack.pop()]; int rightBoundary = i - 1; int leftBoundary = stack.isEmpty() ? 0 : stack.peek() + 1; int width = rightBoundary - leftBoundary + 1; maxArea = Math.max(maxArea, (curHeight * width)); }}return maxArea;解释下这块代码，咱们一开始初始化了一个栈，和一个最大值，而后开始遍历柱子。 ...

摘要：LiteOS工作栈是高地址向低地址成长的递加栈，栈指针指向行将入栈的元素地位。本文分享自华为云社区《LiteOS内核源码剖析系列六 -工作及调度（2）-工作LOS_Task》，原文作者：zhushy 。 咱们介绍下LiteOS工作栈的根底概念。LiteOS工作栈是高地址向低地址成长的递加栈，栈指针指向行将入栈的元素地位。初始化后未应用过的栈空间初始化的内容为宏OS_STACK_INIT代表的数值0xCACACACA，栈顶初始化为宏OS_STACK_MAGIC_WORD代表的数值0xCCCCCCCC。一个工作栈的示意图如下，其中，栈底指针是栈的最大的内存地址，栈顶指针，是栈的最小的内存地址，栈指针从栈底向栈顶方向成长。 1、 LOS_StackInfo工作栈构造体定义typedef struct { VOID *stackTop; // 栈顶指针 UINT32 stackSize; // 栈大小 CHAR *stackName; // 栈名称} StackInfo;另外定义了一个宏函数OS_STACK_MAGIC_CHECK(topstack)用于检测栈是否无效，当栈顶等于OS_STACK_MAGIC_WORD栈是失常的，没有溢出，否则栈顶被改写，产生栈溢出。 /* 1:无效失常的栈 0:有效，产生溢出的栈 */#define OS_STACK_MAGIC_CHECK(topstack) (*(UINTPTR *)(topstack) == OS_STACK_MAGIC_WORD)2、 LOS_StackInfo工作栈反对的操作2.1 工作栈初始化栈初始化函数VOID OsStackInit()应用2个参数，一个是栈顶指针VOID *stacktop，一个是初始化的栈的大小。把栈内容初始化为OS_STACK_INIT，把栈顶初始化为OS_STACK_MAGIC_WORD。 该函数被archarmcortex_msrctask.c的OsTaskStackInit(UINT32 taskId, UINT32 stackSize, VOID topStack)办法调用，进一步被创立工作时的OsTaskCreateOnly()办法调用，实现新创建工作的工作栈初始化。 VOID OsStackInit(VOID *stacktop, UINT32 stacksize){ (VOID)memset_s(stacktop, stacksize, (INT32)OS_STACK_INIT, stacksize); *((UINTPTR *)stacktop) = OS_STACK_MAGIC_WORD;}2.2 获取工作栈水线随着工作栈入栈、出栈，以后栈应用的大小不肯定是最大值，OsStackWaterLineGet()能够获取的栈应用的最大值即水线WaterLine。 该函数须要3个参数，UINTPTR stackBottom是栈底指针，const UINTPTR stackTop栈顶指针，UINT32 *peakUsed用于返回获取的水线值，即工作栈应用的最大值。 ⑴处代码示意如果*stackTop == OS_STACK_MAGIC_WORD，阐明栈没有被溢出毁坏，从栈顶开始栈内容被写满宏OS_STACK_INIT的局部是没有应用过的栈空间。应用tmp指针变量顺次向栈底方向减少，判断栈是否被应用过，while循环完结，栈指针tmp指向最大的未应用过的栈地址。⑵处代码应用栈底指针stackBottom减去tmp，获取最大的应用过的栈空间大小，即须要的水线。⑶处如果栈顶溢出，则返回有效值OS_INVALID_WATERLINE。 该函数被kernelbaselos_task.c中的函数LOS_TaskInfoGet(UINT32 taskId, TSK_INFO_S *taskInfo)调用，获取工作的信息。在shell模块也会应用来或者栈信息。 UINT32 OsStackWaterLineGet(const UINTPTR *stackBottom, const UINTPTR *stackTop, UINT32 *peakUsed){ UINT32 size; const UINTPTR *tmp = NULL;⑴ if (*stackTop == OS_STACK_MAGIC_WORD) { tmp = stackTop + 1; while ((tmp < stackBottom) && (*tmp == OS_STACK_INIT)) { tmp++; }⑵ size = (UINT32)((UINTPTR)stackBottom - (UINTPTR)tmp); *peakUsed = (size == 0) ? size : (size + sizeof(CHAR *)); return LOS_OK; } else { *peakUsed = OS_INVALID_WATERLINE; return LOS_NOK; }}3、 LOS_Task工作栈初始化咱们以AArch32 Cortex-M核为例，分析下工作栈初始化的过程，相干代码散布在archarmcortex_mincludearchtask.h、archarmcortex_msrctask.c。首先看下工作上下文。 ...

明天的知识点 (2020.11.19) —— 第583天 (我也要出题)[html] 应用canvas能实现哪些简单的性能？[css] 如何判断dpr的倍数？[js] 请解释下执行栈有哪些特点？[软技能] 你理解什么是无界画布吗？《论语》，曾子曰：“吾日三省吾身”（我每天屡次检查本人）。前端面试每日3+1题，以面试题来驱动学习，每天提高一点！让致力成为一种习惯，让奋斗成为一种享受！置信 保持 的力量！！！欢送在 Issues 和敌人们一起探讨学习！ 我的项目地址：前端面试每日3+1【举荐】欢送跟 jsliang 一起折腾前端，零碎整顿前端常识，目前正在折腾 LeetCode，打算买通算法与数据结构的任督二脉。GitHub 地址 微信公众号欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个Star, 同时欢送微信扫码关注 前端剑解 公众号，并退出 “前端学习每日3+1” 微信群互相交换（点击公众号的菜单：交换）。 学习不打烊，充电加油只为遇到更好的本人，365天无节假日，每天早上5点纯手工公布面试题（死磕本人，愉悦大家）。心愿大家在这虚夸的前端圈里，放弃沉着，保持每天花20分钟来学习与思考。在这变幻无穷，类库层出不穷的前端，倡议大家不要等到找工作时，才狂刷题，提倡每日学习！（不忘初心，html、css、javascript才是基石！）欢送大家到Issues交换，激励PR，感激Star，大家有啥好的倡议能够加我微信一起交换探讨！心愿大家每日去学习与思考，这才达到来这里的目标！！！（不要为了谁而来，要为本人而来！）交换探讨欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个[Star]

明天的知识点 (2020.09.30) —— 第533天 (我也要出题)[html] html页面中如何实现gif图片从新播放？[css] 简述下Flex的容器和我的项目的概念[js] 函数的调用栈是怎么工作的？[软技能] 我的项目工作量的评估中，“人天”指的是什么？它有什么作用？《论语》，曾子曰：“吾日三省吾身”（我每天屡次检查本人）。前端面试每日3+1题，以面试题来驱动学习，每天提高一点！让致力成为一种习惯，让奋斗成为一种享受！置信 保持 的力量！！！欢送在 Issues 和敌人们一起探讨学习！ 我的项目地址：前端面试每日3+1【举荐】欢送跟 jsliang 一起折腾前端，零碎整顿前端常识，目前正在折腾 LeetCode，打算买通算法与数据结构的任督二脉。GitHub 地址 微信公众号欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个Star, 同时欢送微信扫码关注 前端剑解 公众号，并退出 “前端学习每日3+1” 微信群互相交换（点击公众号的菜单：交换）。 学习不打烊，充电加油只为遇到更好的本人，365天无节假日，每天早上5点纯手工公布面试题（死磕本人，愉悦大家）。心愿大家在这虚夸的前端圈里，放弃沉着，保持每天花20分钟来学习与思考。在这变幻无穷，类库层出不穷的前端，倡议大家不要等到找工作时，才狂刷题，提倡每日学习！（不忘初心，html、css、javascript才是基石！）欢送大家到Issues交换，激励PR，感激Star，大家有啥好的倡议能够加我微信一起交换探讨！心愿大家每日去学习与思考，这才达到来这里的目标！！！（不要为了谁而来，要为本人而来！）交换探讨欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个[Star]

蕴含min函数的栈1. 题目形容定义栈的数据结构，请在该类型中实现一个可能失去栈中所含最小元素的min函数（工夫复杂度应为O（1））。 2. 示例无 3. 解题思路思路：利用一个辅助栈来寄存最小值 栈 3，4，2，5，1辅助栈 3，3，2，2，1每入栈一次，就与辅助栈顶比拟大小，如果小就入栈，如果大就入栈以后的辅助栈顶 当出栈时，辅助栈也要出栈 这种做法能够保障辅助栈顶肯定都以后栈的最小值 4. Java实现import java.util.Stack; public class Solution { private Stack<Integer> dataStack = new Stack(); private Stack<Integer> minStack = new Stack(); public void push(int node) { dataStack.push(node); if (minStack.isEmpty() || min() > node){ // 如果为空，则之间push进去，如果最小栈的最小值都比node大，也把node值push minStack.push(node); }else{ minStack.push(min()); } } public void pop() { dataStack.pop(); minStack.pop(); } public int top() { return dataStack.peek(); } public int min() { return minStack.peek(); }}5. Python实现# -*- coding:utf-8 -*-class Solution: def __init__(self): #应用两个栈来实现，两个栈的大小是雷同的 self.stack = [] self.minStack = [] def push(self, node): # write code here self.stack.append(node) if not self.minStack or self.min() > node: # 将最小值减少到minStack中 self.minStack.append(node) else: self.minStack.append(self.min()) def pop(self): # write code here if self.stack and self.minStack: self.stack.pop() self.minStack.pop() else: return None def top(self): # write code here return self.stack[-1] def min(self): # write code here return self.minStack[-1]如果您感觉本文有用，请点个“在看” ...

题目形容请依据每日 气温 列表，从新生成一个列表。对应地位的输入为：要想观测到更高的气温，至多须要期待的天数。如果气温在这之后都不会升高，请在该地位用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输入应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提醒：气温 列表长度的范畴是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范畴内的整数。 解题思路思路一：暴力破解，应用双循环，找到下一个大于以后值的序号； 思路二：1、反向开始算，最初一个必定是0； 2、而后开始排，用新数组记录对应的每个数值的下一个大于他的值的间隔 3、和下一个数值比照，联合下一个素值对应的新数组记录的下一个大于该值的地位，疾速找到下一个比照的数值的地位 ### 语言积攒和技巧 1、不必管最初一个数值的后果，应为new的时候，曾经给他赋值0了 2、在进行循环比照的时候，改良下逻辑关系，判断条件外面能够少一个比拟的操作，这样整题的运算工夫会有4ms降到3ms。具体看连贯2和连贯3的区别 ### vscode 代码连贯https://github.com/lunaDolphin/leetcode/tree/master/stack_dailyTemperatures_739https://github.com/lunaDolphin/leetcode/tree/master/stack_dailyTemperatures_739_1https://github.com/lunaDolphin/leetcode/tree/master/stack_dailyTemperatures_739_2

栈的定义栈是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。（百科全书） 栈的常用操作<font size="3">栈中有两个基本的操作 推入 ：从栈的顶端推入一个数据，依次往下推弹出 ：讲栈顶端的数据移除栈的基本提点就是 先进后出，后进先出除了头尾的节点，每个元素都有一个先驱和一个后继对于栈的画面的理解，可以想象成一个步枪弹夹添加子弹和射击的过程弹夹只有一个出入口进行推入和弹出</font> js模拟实现一个栈<body style='width: 80%;height:80%; margin: 10% auto;'><ul id="stackBox" style="width:100px;border:1px solid #1fb19e;"></ul><div style="width:400px; display:flex;"> <input id="funStackBox" value="执行函数"> <div style="margin-left:100px;"> <button onclick="pushStack()" type='primary'>进栈</button> <button onclick="popStack()" type='primary'>出栈</button> </div></div><script> // 栈盒子 let stackBox = document.getElementById('stackBox') // 执行函数盒子 let funStackBox = document.getElementById('funStackBox') // 栈类 class Stack { constructor(length) { this.list = [] this.length = length } // 新增栈 addStack(val) { if (this.length > this.list.length) { this.list.push(val) let beforeDom = document.getElementById(this.list.length - 1) // 新增栈 let el = document.createElement('li') el.id = this.list.length el.innerText = this.list[this.list.length - 1] stackBox.insertBefore(el, beforeDom) }else{ console.log('栈满了') } } // 弹出栈 popStack() { let delDom = document.getElementById(this.list.length) stackBox.removeChild(delDom) return this.list.pop() } // 栈的大小 stackLength() { console.log('当前栈大小为'+this.list.length) return this.list.length } // 栈的顶层元素 stackIsHas() { return this.list.length?this.list[this.list.length]:console.log('没有栈了') } //查看所有元素 showStack() { return this.list.join('\n'); } //清空队列 clearStack() { this.list = []; this.showStack() console.log('栈空了') } } stackOne = new Stack(5) /** * @author: 周靖松 * @information: 进栈 * @Date: 2019-06-10 12:47:16 */ function pushStack() { stackOne.addStack(funStackBox.value) console.log(funStackBox.value, '进栈') stackOne.stackLength() stackOne.stackIsHas() } /** * @author: 周靖松 * @information: 出栈 * @Date: 2019-06-10 12:47:16 */ function popStack() { let popStack = stackOne.popStack(funStackBox.value) console.log(popStack, '出栈') stackOne.stackLength() stackOne.stackIsHas() }</script></body><font size="3">效果图如下</font> ...

欢迎进入JAVA基础课程 博客地址：https://blog.csdn.net/houjiyu...本系列文章将主要针对JAVA一些基础知识点进行讲解，为平时归纳所总结，不管是刚接触JAVA开发菜鸟还是业界资深人士，都希望对广大同行带来一些帮助。若有问题请及时留言或加QQ：243042162。 寄语：生活之中会有很多机遇，也许你自认为错失了一次最美的机遇，但不知不觉中新的机遇已悄然到来。JAVA虚拟机JVM实现了JAVA语言最重要的特征：平台无关性。其原理：java程序并不直接在操作系统上执行，而是由JVM执行。 基本组成 详细框架 步骤：1.从操作系统的角度看来，虚拟机JVM（人）只是一个普通进程。2.虚拟机能够加载我们编写的class文件（食物）。3.加载class文件的是一个叫做类加载器的子系统（嘴巴）。4.虚拟机中的执行引擎（肠胃）用来执行class文件中的字节码指令。5.虚拟机在执行过程中，要分配内存创建对象。当这些对象过时无用了，必须要自动清理这些无用的对象。清理对象回收内存的任务由垃圾收集器负责。就好比人吃进去的食物，在消化之后，必须把废物排出体外，腾出空间可以在下次饿的时候吃饭并消化食物。参考网站：（1）https://www.jianshu.com/p/c07...（2）https://blog.csdn.net/lilamei...

前言想写好前端，先练好内功。栈内存与堆内存 、浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。 栈 定义 后进者先出，先进者后出，简称 后进先出（LIFO），这就是典型的栈结构。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。从栈的操作特性来看，是一种 操作受限的线性表，只允许在一端插入和删除数据。不包含任何元素的栈称为空栈。栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。 堆定义 堆数据结构是一种树状结构。它的存取数据的方式，与书架与书非常相似。我们不关心书的放置顺序是怎样的，只需知道书的名字就可以取出我们想要的书了。好比在 JSON 格式的数据中，我们存储的 key-value 是可以无序的，只要知道 key，就能取出这个 key 对应的 value。 堆与栈比较 堆是动态分配内存，内存大小不一，也不会自动释放。栈是自动分配相对固定大小的内存空间，并由系统自动释放。栈，线性结构，后进先出，便于管理。堆，一个混沌，杂乱无章，方便存储和开辟内存空间。栈内存与堆内存JavaScript 中的变量分为基本类型和引用类型。 基本类型是保存在栈内存中的简单数据段，它们的值都有固定的大小，保存在栈空间，通过按值访问，并由系统自动分配和自动释放。这样带来的好处就是，内存可以及时得到回收，相对于堆来说，更加容易管理内存空间。JavaScript 中的 Boolean、Null、Undefined、Number、String、Symbol 都是基本类型。 引用类型（如对象、数组、函数等）是保存在堆内存中的对象，值大小不固定，栈内存中存放的该对象的访问地址指向堆内存中的对象，JavaScript 不允许直接访问堆内存中的位置，因此操作对象时，实际操作对象的引用。JavaScript 中的 Object、Array、Function、RegExp、Date 是引用类型。 结合实例说明 let a1 = 0; // 栈内存let a2 = "this is string" // 栈内存let a3 = null; // 栈内存let b = { x: 10 }; // 变量 b 存在于栈中，{ x: 10 } 作为对象存在于堆中let c = [1, 2, 3]; // 变量 c 存在于栈中，[1, 2, 3] 作为对象存在于堆中 ...

前言基础知识就像是一座大楼的地基，它决定了我们的技术高度。我们应该多掌握一些可移值的技术或者再过十几年应该都不会过时的技术，数据结构与算法就是其中之一。栈、队列、链表、堆 是数据结构与算法中的基础知识，是程序员的地基。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。 1. 线性表与非线性表线性表（Linear List）：就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组、链表、队列、栈 等就是线性表结构。 非线性表：数据之间并不是简单的前后关系。二叉树、堆、图 就是非线性表。 本文主要讲线性表，非线性表会在后面章节讲。 2. 数组 定义数组 (Array) 是一个有序的数据集合，我们可以通过数组名称 (name) 和索引 (index) 进行访问。数组的索引是从 0 开始的。特点数组是用一组连续的内存空间来存储的。所以数组支持 随机访问，根据下标随机访问的时间复杂度为 O(1)。 低效的插入和删除。数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效，因为底层通常是要进行大量的数据搬移来保持数据的连续性。插入与删除的时间复杂度如下：插入：从最好 O(1) ，最坏 O(n) ，平均 O(n)删除：从最好 O(1) ，最坏 O(n) ，平均 O(n) 注意但是因为 JavaScript 是弱类型的语言，弱类型则允许隐式类型转换。 隐式：是指源码中没有明显的类型转换代码。也就是说，一个变量，可以赋值字符串，也可以赋值数值。 let str = "string"str = 123 console.log(str) // 123你还可以直接让字符串类型的变量和数值类型的变量相加，虽然得出的最终结果未必是你想象的那样，但一定不会报错。 let a = 123let b = "456"let c = a + b// 数值加字符串，结果是字符串console.log(c) // "123456"数组的每一项可以是不同的类型，比如： ...

队列栈与一般线性表区别线性表抽象是存储具有先后顺序元素数据的结构，支持任意位置的插入，删除操作。队列和栈限制插入删除操作，队列只能从尾部插入，首部取出(删除)，既先入先出;栈限制插入和取出操作只能在尾部进行，既先入后出。 实现方式队列和栈同一般线性表相同，可用数组和链式结构体实现。由于限制了插入和取出的位置，没有频繁的中间元素操作，数组实现比链式实现效率更高。对应缺点为初始化时要定义数组大小，无法动态分配大小。 代码实现栈struct stack;typedef struct stack sStack;typedef sStack *pStack;#define EmptyTOS -1;struct stack { int capacity; int topOfStack; long long int *data;};pStack elrInitStackInt(int capaticy) { pStack s; s = malloc(sizeof(sStack)); if (s == NULL) { printf("out of space!"); } s->data = malloc(sizeof(long long int) * capaticy); if (s->data == NULL) { printf("out of space!"); } s->capacity = capaticy; elrMakeStackEmpty(s); return s;}void elrFreeStackInt(pStack stack) { if (stack != NULL) { free(stack->data); free(stack); }}int elrIsStackEmpty(pStack stack) { return stack->topOfStack == EmptyTOS;}int elrIsStackFull(pStack stack) { return stack->topOfStack == (stack->capacity - 1);}void elrMakeStackEmpty(pStack stack) { stack->topOfStack = EmptyTOS;}void elrPushStackInt(pStack stack, long long int data) { if (elrIsStackFull(stack)) { printf("full stack"); } else { stack->data[++stack->topOfStack] = data; }}long long int elrPopStackInt(pStack stack) { if (elrIsStackEmpty(stack)) { printf("empty stack"); } else { return stack->data[--stack->topOfStack]; }}队列struct queue;typedef struct queue sQueue;typedef sQueue *pQueue;struct queue { int capacity; int front; int rear; int size; long long int *data;};pQueue elrInitQueueInt(int capaticy) { pQueue s; s = malloc(sizeof(sQueue)); if (s == NULL) { printf("out of space!"); } s->data = malloc(sizeof(long long int) * capaticy); if (s->data == NULL) { printf("out of space!"); } s->capacity = capaticy; elrMakeQueueEmpty(s); return s;}void elrFreeQueueInt(pQueue queue) { if (queue != NULL) { free(queue->data); free(queue); }}int elrIsQueueEmpty(pQueue queue) { return queue->size == 0;}int elrIsQueueFull(pQueue queue) { return queue->size == queue->capacity;}void elrMakeQueueEmpty(pQueue queue) { queue->size = 0; queue->front = 1; queue->rear = 0;}int succ(pQueue queue, int value) { if (++value == queue->capacity) { value = 0; } return value;}void elrEnqueuekInt(pQueue queue, long long int data) { if (elrIsQueueFull(queue)) { printf("full queue"); } else { queue->size++; queue->rear = succ(queue, queue->rear); queue->data[queue->rear] = data; }}long long int elrDequeueInt(pQueue queue) { if (elrIsQueueEmpty(queue)) { printf("empty queue"); } else { queue->size--; int data = queue->data[queue->front]; queue->front = succ(queue, queue->front); }}

栈和堆的区别中文原文：栈和堆的区别英文原文：Memory：Stack vs Heap 校对：xiaobai22 目录 栈和堆的区别栈堆栈和堆的优缺点 栈堆例子什么时候使用堆关联文章栈和堆的区别到目前为止，我们已经知道如何声明基础变量类型，例如：int,double 等以及复杂类型例如：数组和结构体。在C语言中，我们使用和其他语言诸如MATLAB,Python相同的语法声明它们，并把这些变量推到栈里。 栈什么是栈？这是计算机内存的特定区域，它存储每个函数创建的临时变量（包括main() 函数）。栈使用“LIFO”数据结构，由CPU管理和优化。每当函数声明一个新变量，它就会被推入栈。当函数退出时，所有被该函数推入栈的变量会被释放（这代表，它们已经被删除）。一旦栈的变量释放，此内存区可以被其他栈变量使用。 使用栈保存变量的优点：CPU帮你管理内存。你不需要手动分配和释放。更重要的是，CPU可以高效的组织内存，读写栈变量会非常快。 理解栈的关键 ：当函数退出时，它推入栈的所有变量会被弹出（永远丢失）。栈变量本质是局部的。这涉及到我们之前了解的 变量作用域 或 局部和全局变量。在C语言编程通常会遇到此类BUG：从函数外部企图读取函数内部的变量（在函数退出之后）。 栈另一个需要注意的特征是：保存在栈的变量是有大小限制的。堆的情况却不一样。 栈的总结： 栈的增长和缩容发生在函数推入和弹出局部变量时不需要你自己管理内存，变量会自动分配和释放栈有大小限制栈变量仅存在于创建它们的函数运行的时候堆堆是计算机的内存区，它不会帮你自动管理，也不由CPU管理。堆有更大的空间。你需要使用 C语言内置函数malloc()和 calloc() 分配内存到堆。当不再使用这块内存时，你负责使用free()进行释放。如果没做这步，你的程序会发生内存泄露。堆上的内存仍然被占用（不能被其他进程使用）。正如我们在调试中看到的，用 valgrind工具，帮助检测内存泄漏。 和栈不一样，堆没有大小限制（除了物理内存限制）。堆的读写稍微比较慢，因为必须使用指针访问堆上的内存。我们在后面会讨论指针。 和栈不一样，其他函数和你程序上的任何地方都可以访问堆上创建的变量。堆本质是全局的。 栈和堆的优缺点栈访问非常快不必显式的分配变量CPU有效的管理，不会产生内存碎片仅用于局部变量有大小限制（不同操作系统有区别）大小不能被调整堆变量可以全局访问没有内存限制（相对的）访问速度比较慢会产生内存碎片需要你分配和释放大小可以通过 realloc() 调整例子这是一个简短的程序，创建变量到栈。 #include double multiplyByTwo (double input) { double twice = input * 2.0; return twice;}int main (int argc, char *argv[]){ int age = 30; double salary = 12345.67; double myList[3] = {1.2, 2.3, 3.4}; printf("double your salary is %.3f\n", multiplyByTwo(salary)); return 0;}double your salary is 24691.340在10，11，12行我们声明了变量：int ，double，长度为3的浮点型数组。main() 进行分配的时候，这3个变量被推到栈。当main() 函数退出（程序停止），这些变量会被弹出栈。同样的，在函数 multiplyByTwo() 有2个 double 型的变量，会被推到栈。multiplyByTwo() 退出，这2个变量会被弹出栈，永远消失。 ...

了解和学习一种知识的最好方法是带着相关的问题去探索，当我们把一些常见的问题全部解答了，我们也就能对这种事物有一些初步的了解了。试着回答下面的几个问题，让我们对数据结构和算法有一个基本的认识吧。 什么是数据结构？为什么要了解数据结构？作为一个前端，日常工作当中，我们接触的数据结构有哪几种？数据结构和算法是什么关系？如何判断一个算法是否是最优？什么是数据结构？从字面意思来理解就是一种数据的多种表现方法，什么是结构——由组成整体的各部分的搭配和安排（百度百科）。我的理解是：数据的排列，不同的数据结构就是数据的多种排列形式，然后根据排列的情况我们通常用一个学名来表示它，比如说：数组，集合，树，图等。 为什么要了解数据结构？当我们了解了数据结构之后，在实际的编程过程当中，我们遇到某一类的数据的时候，我们就能够找到一种最合适的数据结构来表示他们了。这样再处理跟数据相关问题的时候就会变得高效，因为确定了数据结构，我们也就确定了针对该结构的数据，使用那些方法来对数据进行相关的操作了。比如说，我们需要一种数据结构来记录每天的天气情况，当我们说到某一天的时候，就能立刻知道当天的天气是怎么样的时候我们可以用一个数组来表现。又如，我们要描述一个家族的族谱的时候，用树型结构比较合适；描述一个人的年龄，身高，体重，民族，学历这种用集合比较合适；描述排队的情况用队列。 作为前端，通常我们接触到的数据结构有哪几种？最常用的应该有两种了：数组，对象。到了ES6又增加了两种新的数据结构Set和Map，其实Set和Map应该算是数组和对象的一种变种，但总的来说它们又是另外两种类型的数据结构； Set类数组结构——成员唯一，没有重复的值Map类对象结构——不同Object，键值通常是字符串，Map的键值可以是任何类型。数据结构和算法的关系数据结构只不过是我们描述数据的一种手段，但我们最终的目的通常是对这些数据进行相关的操作，比如：添加，删除，查找，排序等。所谓的算法就是如何去实现这种操作的一种计算方式。但算法往往不止一种，有道是条条道路通罗马，通常要达到某种目的，我们可能会有很多种的算法。比如一个数组我们要给他进行去重，就有很多种方法。你可以循环遍历，把每个值跟其他的值比较一遍，也可以把数组转成Set结构的数据。 如何判断一个算法是否最优？上面说到实现某种操作的方法有很多种，但是哪一种是最好的，我们要如何判断呢。我们可以通过算法的执行时间对吧，那种算法执行的速度越快，当然那种算法就最好。但计算机当中，还要考虑到算法的空间复杂度，也就是算法执行过程当中，可能占用的内存空间，一个算法执行的速度非常块，但执行的时候，需要1T的内存空间，这就不行。所以好的算法往往有两个条件: 运算的速度快占用的内存（存储空间） 小我还有个第三点，那就是代码便于理解，但这部分优秀的算法，往往涉及到很多数学相关的问题，如果没有这部分相关的概念，理解起来是非常不容易的。 其它涉及到前端数据结构和算法的一些学习笔记，我放到了github上面，内容还在更新，尽量一周分享一个，欢迎大家一起来讨论并参与分享，github地址如下: https://github.com/mmcai/Stru...

最近准备系统的学习数据结构与算法，学习的时候想配合着leetcode刷题，这样会加深印象。在学习栈的时候，老师举了计算器实现的例子，我搜了一下leetcode刚好有这样的题，就想着自己实现一下吧。leetcode题目：leetcode224leetcode227实现一个基本计算器肯定是要有四则运算和括号运算的，实现一个这样的计算器自然就把这两题做出来了。思路这里参考了浙大mooc数据结构课程的栈的部分，首先是将常用的中缀表达式转换为后缀表达式，再将后缀表达式进行求值运算。中缀表达式转为后缀表达式用栈来存运算符，按顺序读取中缀表达式的每个对象，对每个对象按不同情况处理：运算数：直接输出左括号：压入栈右括号：弹出并输出栈顶元素，直至遇到左括号停止，将左括号出栈丢弃运算符：若优先级大于栈顶元素，则把它压栈；若优先级小于等于栈顶元素，则弹出并输出栈顶元素，再比较新的栈顶元素，直至优先级大于栈顶元素或者栈为空，再将该元素压入栈处理完中序表达式后，将栈中还存留的运算符全部输出例：2*(9+1) -> 2 9 1 + 2+9/3-5 -> 2 9 3 / + 5 -后缀表达式求值用栈来存取运算数，按顺序读取后缀表达式各项，对运算符和运算数做不同处理：运算数：入栈运算符：从栈中弹出两个运算数，根据运算符做运算求出结果后，将结果压栈最后栈顶的元素就是表达式的值，此时栈中只有一个元素代码：转换表达式// 将中缀转为后缀表达式，以空格分割运算数和运算符private static String parseRPN(String s) { // 用于返回的字符串 StringBuilder returnSb = new StringBuilder(); // 创建操作符栈 Stack<Character> stack = new Stack<Character>(); // 将字符串转换为字符数组，这样遍历字符串会快一些，使用String.charAt()会每次从头遍历 char[] cs = s.toCharArray(); //开始从头处理中缀表达式的每个对象 int i = 0; while (i < cs.length) { // 匹配空格，将其舍弃 if (cs[i] == ’ ‘) { i++; continue; } // 匹配数字，若匹配成功则将数字添加至numberSb StringBuilder numberSb = new StringBuilder(); while(i < cs.length&&cs[i]>=‘0’&&cs[i]<=‘9’){ numberSb.append(cs[i]); i++; } if (numberSb.length()!=0) {//若前面匹配到了数字，则numberSb长度必不为0 returnSb.append(numberSb.append(’ ‘));//将numberSb添加空格后追加到returnSb continue; } // 匹配运算符 char symbol = cs[i]; // 遇到左括号直接压栈 if (symbol == ‘(’) { stack.push(symbol); } else // 遇到右括号，输出栈顶元素至左括号结束 if (symbol == ‘)’) { while (stack.peek() != ‘(’) { returnSb.append(stack.pop() + " “); } stack.pop();// 将左括号移出栈 } else // 处理其他符号 // 优先级大于栈顶元素时，直接压栈 if (stack.isEmpty() || (symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’)) { stack.push(symbol); } else {// 否则就输出栈顶元素至优先级大于栈顶元素或者遇到左括号或者栈为空，然后压栈 while (!stack.isEmpty()) { if (stack.peek() == ‘(’) break; if (!((symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’))) { returnSb.append(stack.pop() + " “); } else break; } stack.push(symbol); } i++; } //输出运算符栈的元素 while (!stack.isEmpty()) { returnSb.append(stack.pop() + " “); } return returnSb.toString();}后缀表达式求值定义的几个long型变量是为了观察运行时间public int calculate(String s) { long time1 = System.currentTimeMillis(); // 操作数栈 Stack<Integer> stack = new Stack<Integer>(); // 将s转为后缀表达式，并转为字符数组 char[] cs = parseRPN2(s).toCharArray(); long time2 = System.currentTimeMillis(); int i = 0; //tmpSb用来临时存放数字，主要是考虑到数字不止一位 StringBuilder tmpSb = new StringBuilder(); while (i < cs.length) { if (cs[i] == ’ ‘) {//遇到空格就把tmpSb转为数字并压入栈 if (tmpSb.length() != 0) { stack.push(Integer.parseInt(tmpSb + “”)); tmpSb = new StringBuilder(); } i++; continue; } //遇到数字就加在tmpSb后 if (cs[i] >= ‘0’ && cs[i] <= ‘9’) { tmpSb.append(cs[i]); i++; continue; } //不是空格也不是数字就是运算符，弹出两个数进行运算，注意这里弹出的第一个数为b，第二个数才是a，这里我一开始写错了 int b = stack.pop(); int a = stack.pop(); switch (cs[i]) { case ‘+’: stack.push(a + b); break; case ‘-’: stack.push(a - b); break; case ‘’: stack.push(a * b); break; case ‘/’: stack.push(a / b); break; } i++; } long time3 = System.currentTimeMillis(); System.out.println(“总耗时：” + (time3 - time1)); System.out.println(“转换后缀耗时：” + (time2 - time1)); System.out.println(“求值耗时：” + (time3 - time2)); //最后在栈里的唯一一个元素就是要求的值 return stack.pop();}测试public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.next(); System.out.println(new Solution().calculate(s));}输入:19 * (2+8)输出:总耗时：44转换后缀耗时：26求值耗时：18结果为：190还有一个输入为leetcode测试用例，s非常长，我写的这个方法也能在半秒之内得出结果，速度还是很快的。我之前写的一个转换后缀的方法由于大量的新建StringBuilder，就导致了这个测试用例因为超时而未通过，大概是7秒左右，在这里我也贴一下代码，这里不提倡使用。超时代码private static String parseRPN2(String s) { StringBuilder returnSb = new StringBuilder(); Stack<Character> stack = new Stack<Character>(); Pattern space = Pattern.compile(”\s+”); Pattern number = Pattern.compile(”\d+"); StringBuilder sb = new StringBuilder(s); while (sb.length() != 0) { Matcher spaceMatcher = space.matcher(sb); if (spaceMatcher.lookingAt()) { sb = new StringBuilder(sb.subSequence(spaceMatcher.end(), sb.length())); continue; } Matcher numberMatcher = number.matcher(sb); if (numberMatcher.lookingAt()) { returnSb.append(numberMatcher.group() + " “); sb = new StringBuilder(sb.subSequence(numberMatcher.end(), sb.length())); continue; } char symbol = sb.charAt(0); if (symbol == ‘(’) { stack.push(symbol); } else if (symbol == ‘)’) { while (stack.peek() != ‘(’) { returnSb.append(stack.pop() + " “); } stack.pop(); } else if (stack.isEmpty() || (symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’)) { stack.push(symbol); } else { while (!stack.isEmpty()) { if (stack.peek() == ‘(’) break; if (!((symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’))) { returnSb.append(stack.pop() + " “); } else break; } stack.push(symbol); } sb = new StringBuilder(sb.subSequence(1, sb.length())); } while (!stack.isEmpty()) { returnSb.append(stack.pop() + " “); } return returnSb.toString();}结语计算器的基本实现就是基于这样的方法，后面我在学习其他数据结构和算法时会继续分享， ...

前言上一篇：算法分析下一篇：基本排序本篇内容主要是栈，队列 (和包)的基本数据类型和数据结构在很多应用中，我们需要维护多个对象的集合，而对这个集合的操作也很简单基本数据类型对象的集合操作：insert – 向集合中添加新的对象remove – 去掉集合中的某个元素iterate – 遍历集合中的元素并对他们执行某种操作test if empty – 检查集合是否为空做插入和删除操作时我们要明确以什么样的形式去添加元素，或我们要删除集合中的哪个元素。处理这类问题有两个经典的基础数据结构：栈(stack) 和队列(queue)两者的区别在于去除元素的方式：栈：去除最近加入的元素，遵循后进先出原则(LIFO: last in first out)。插入元素对应的术语是入栈 – push；去掉最近加入的元素叫出栈 – pop队列：去除最开始加入的元素，遵循先进先出原则(FIFO: first in first out)。关注最开始加入队列的元素，为了和栈的操作区分，队列加入元素的操作叫做入队 – enqueue；去除元素的操作叫出队 – dequeue此篇隐含的主题是模块式编程，也是平时开发需要遵守的原则模块化编程这一原则的思想是将接口与实现完全分离。比如我们精确定义了一些数据类型和数据结构(如栈，队列等)，我们想要的是把实现这些数据结构的细节完全与客户端分离。客户端可以选择数据结构不同的实现方式，但是客户端代码只能执行基本操作。实现的部分无法知道客户端需求的细节，它所要做的只是实现这些操作，这样，很多不同的客户端都可以使用同一个实现，这使得我们能够用模块式可复用的算法与数据结构库来构建更复杂的算法和数据结构，并在必要的时候更关注算法的效率。Separate client and implementation via API.API：描述数据类型特征的操作Client：使用API操作的客户端程序。Implementation：实现API操作的代码。下面具体看下这两种数据结构的实现栈栈 API假设我们有一个字符串集合，我们想要实现字符串集合的储存，定期取出并且返回最后加入的字符串，并检查集合是否为空。我们需要先写一个客户端然后再看它的实现。字符串数据类型的栈性能要求：所有操作都花费常数时间客户端：从标准输入读取逆序的字符串序列测试客户端import edu.princeton.cs.algs4.StdIn;import edu.princeton.cs.algs4.StdOut;public static void main(String[] args){ StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) { //从标准输入获取一些字符串 String s = StdIn.readString(); //如果字符串为"-",则客户端将栈顶的字符串出栈，并打印出栈的字符串 if (s.equals("-")) StdOut.print(stack.pop()); //否则将字符串入栈到栈顶 else stack.push(s); }}客户端输入输出：栈的实现：链表链表(linked-list)连接待添加…我们想保存一个有节点组成的，用来储存字符串的链表。节点包含指向链表中下一个元素的引用(first).维持指针 first 指向链表中的第一个节点Push：入栈，在链表头插入一个新的节点Pop：出栈，去掉链表头处第一个节点Java 实现public class LinkedStackOfStrings{ //栈中唯一的实例变量是链表中的第一个节点的引用 private Node first = null; //内部类，节点对象，构成链表中的元素，由一个字符串和指向另一个节点的引用组成 private class Node { private String item; private Node next; } public boolean isEmpty() { return first == null; } // public void push(String item) { //将指向链表头的指针先保存 Node oldfirst = first; //创建新节点：我们将要插入表头的节点 first = new Node(); first.item = item; //实例变量的next指针指向链表oldfirst元素，现在变成链表的第二个元素 first.next = oldfirst; } //出栈 public String pop() { //将链表中的第一个元素储存在标量 item 中 String item = first.item; //去掉第一个节点：将原先指向第一个元素的指针指向下一个元素，然后第一个节点就等着被垃圾回收处理 first = first.next; //返回链表中原先保存的元素 return item; }}图示：出栈：入栈：性能分析通过分析提供给客户算法和数据结构的性能信息，评估这个实现对以不同客户端程序的资源使用量Proposition 在最坏的情况下，每个操作只需要消耗常数时间(没有循环)。Proposition 具有n个元素的栈使用 ~40n 个字节内存(没有考虑字符串本身的内存，因为这些空间的开销在客户端上)栈的实现：数组栈用链表是实现花费常数的时间，但是栈还有更快的实现另一种实现栈的 natural way 是使用数组储存栈上的元素将栈中的N个元素保存在数组中，索引为 n，n 对应的数组位置即为栈顶的位置，即下一个元素加入的地方使用数组 s[] 在栈上存储n个元素。push()：在 s[n] 处添加新元素。pop()：从 s[n-1] 中删除元素。在改进前使用数组的一个缺点是必须声明数组的大小，所以栈有确定的容量。如果栈上的元素个数比栈的容量多，我们就必须处理这个问题(调整数组)Java 实现public class FixedCapacityStackOfStrings{ private String[] s; //n 为栈的大小，栈中下一个开放位置，也为下一个元素的索引 private int n = 0; //int capacity：看以下说明 public FixedCapacityStackOfStrings(int capacity) { s = new String[capacity]; } public boolean isEmpty() { return n == 0; } public void push(String item) { //将元素放在 n 索引的位置，然后 n+1 s[n++] = item; } public String pop() { //然后返回数组n-1的元素 return s[–n]; }}int capacity： 在构造函数中加入了容量的参数，破坏了API，需要客户端提供栈的容量。不过实际上我们不会这么做，因为大多数情况下，客户端也无法确定需要多大栈，而且客户端也可能需要同时维护很多栈，这些栈又不同时间到达最大容量，同时还有其他因素的影响。这里只是为了简化。在调整数组中会处理可变容量的问题，避免溢出对于两种实现的思考上述的实现中我们暂时没有处理的问题：Overflow and underflowUnderflow ：客户端从空栈中出栈我们没有抛出异常Overflow ：使用数组实现，当客户端入栈超过容量发生栈溢出的问题Null item：客户端是否能像数据结构中插入空元素Loitering 对象游离：即在栈的数组中，我们有一个对象的引用，可是我们已经不再使用这个引用了数组中当我们减小 n 时，在数组中仍然有我们已经出栈的对象的指针，尽管我们不再使用它，但是Java系统并不知道。所以为了避免这个问题，有效地利用内存，最好将去除元素对应的项设为 null，这样就不会剩下旧元素的引用指针，接下来就等着垃圾回收机制去回收这些内存。这个问题比较细节化，但是却很重要。public String pop(){ String item = s[–n]; s[n] = null; return item;} 调整数组队列泛型迭代器栈与队列的应用附录 ...

题目定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数据进栈时栈的最小值.2.每次数据进栈时，将此数据和最小值栈的栈顶元素比较，将二者比较的较小值再次存入最小值栈.4.数据栈出栈，最小值栈也出栈。3.这样最小值栈的栈顶永远是当前栈的最小值。代码var dataStack = [];var minStack = []; function push(node){ dataStack.push(node); if(minStack.length === 0 || node < min()){ minStack.push(node); }else{ minStack.push(min()); }}function pop(){ minStack.pop(); return dataStack.pop();}function top(){ var length = dataStack.length; return length>0&&dataStack[length-1]}function min(){ var length = minStack.length; return length>0&&minStack[length-1]}

栈是一种限定仅在表尾进行插入和删除操作的线性表。栈的应用有很多，比如常见的递归，计算机表达式求值等。下面我们用栈来实现简易的四则运算计算器。列一下本文的思路:实现链栈的数据结构及其操作中缀表达式转后缀表达式后缀表达式求值1、首先, 先实现一个链栈。//定义栈的数据结构class Node{ public $symbol; public $next; public function __construct( $symbol, $next ) { $this->symbol = $symbol; $this->next = $next; }}//初始化栈,生成头结点function initStack( &$node ){ $node = new Node( ‘’, null );}//入栈function push( Node &$node, $symbol ){ $p = new Node( $symbol, null ); $p->next = $node->next; $node->next = $p;}//出栈function pop( Node &$node, &$symbol ){ if ( null == $node->next ) { echo “栈空\n”; return; } $q = $node->next; $symbol = $q->symbol; $node->next = $node->next->next; unset( $q );}2、其次, 利用第一步实现的链栈，将中缀表达式转为后缀表达式。//获取运算符的优先级function get_priority( $symbol ){ switch ( $symbol ) { case ‘(’: $priority = 3; break; case ‘’: case ‘/’: $priority = 2; break; case ‘+’: case ‘-’: $priority = 1; break; case ‘)’: $priority = 0; break; default: $priority = 0; break; } return $priority;}//栈顶依次出栈,如果遇到’(‘则停止function clear_stack( &$list ){ $res = ‘’; while ( null != $list->next ) { if ( ‘(’ != $list->next->symbol ) { pop( $list, $item ); $res .= $item; } else { pop( $list, $item ); return $res; } } return $res;}//中缀表达式转后缀表达式function middle_to_back( $middle_expression ){ initStack( $list ); $back_expression = ‘’; $length = strlen( $middle_expression ); for ( $i = 0; $i < $length; $i ++ ) { $symbol = $middle_expression[ $i ]; if ( ’ ’ != $symbol ) { if ( is_numeric( $symbol ) ) { //数字直接输出 $back_expression .= $symbol; } else {//非数字则比较优先级 $stack_top_priority = get_priority( null == $list->next ? ’’ : $list->next->symbol ); $current_symbol_priority = get_priority( $symbol ); if ( $current_symbol_priority > $stack_top_priority ) {//优先级比栈顶高则进栈 push( $list, $symbol ); } else { $output = clear_stack( $list ); $back_expression .= $output; if ( ‘)’ != $symbol ) { push( $list, $symbol ); } } } } } while ( null != $list->next ) {//将栈清空 pop( $list, $item ); $back_expression .= $item; } return $back_expression;}3、接下来, 我们利用第一步实现的链栈，和第二步得到的后缀表达式，计算最后的值。//是否是四则运算符号function is_arithmetic_symbol( $symbol ){ $arithmetic_symbols = array( ‘+’, ‘-’, ‘’, ‘/’ ); if ( in_array( $symbol, $arithmetic_symbols ) ) { return true; } else { return false; }}//计算后缀表达式的值function calculate( $expression ){ $stack = new Node( ‘’, null ); $length = strlen( $expression ); for ( $i = 0; $i < $length; $i ++ ) { if ( ’ ’ != $expression[ $i ] ) {//为空则跳过 if ( is_numeric( $expression[ $i ] ) ) { push( $stack, $expression[ $i ] ); } else if ( is_arithmetic_symbol( $expression[ $i ] ) ) { pop( $stack, $n1 ); pop( $stack, $n2 ); $res = get_result( $n2, $n1, $expression[ $i ] ); push( $stack, $res ); } else { echo “wrong symbol, exit”; exit(); } } } $value = $stack->next->symbol; return $value;}最后，我们测试一下所实现的计算器。function main(){ $back_expression = middle_to_back( ‘((1+2)*3-4) * 5’ ); $result = calculate( $back_expression ); echo “后缀表达式的值为: " . $back_expression, PHP_EOL; echo “result : " . $result, PHP_EOL;}main();得到的结果如下: 简易的计算器就实现啦！~~~（代码中有一些细节未做判断，希望读者理解。欢迎大家提出批评修改意见，感谢~） ...

题目Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.Example 1:Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]Output: trueExplanation: We might do the following sequence:push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1Example 2:Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]Output: falseExplanation: 1 cannot be popped before 2.Note:0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed is a permutation of popped.pushed and popped have distinct values.题目地址讲解典型的栈的题目，练习此题，有助于加深对栈的理解和运用。java代码class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { Stack<Integer> stack = new Stack<>(); int index=0; for(int i=0;i<popped.length;i++){ if(stack.isEmpty()){ if(index<pushed.length){ stack.push(pushed[index++]); }else{ return false; } } while(popped[i]!=stack.peek()){ if(index<pushed.length){ stack.push(pushed[index++]); }else{ return false; } } stack.pop(); } return true; }} ...

Minimum Add to Make Parentheses ValidGiven a string S of ‘(’ and ‘)’ parentheses, we add the minimum number of parentheses ( ‘(’ or ‘)’, and in any positions ) so that the resulting parentheses string is valid.Formally, a parentheses string is valid if and only if:It is the empty string, orIt can be written as AB (A concatenated with B), where A and B are valid strings, orIt can be written as (A), where A is a valid string.Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.Example 1:Input: “())“Output: 1Example 2:Input: “(((“Output: 3Example 3:Input: “()“Output: 0Example 4:Input: “()))((“Output: 4Note:S.length <= 1000S only consists of ‘(’ and ‘)’ characters.题目地址这是栈的经典应用java代码class Solution { public int minAddToMakeValid(String S) { Stack<Character> stack = new Stack<>(); char[] c = S.toCharArray(); for(int i=0;i<c.length;i++){ if(c[i]==’)’ && !stack.empty() && stack.peek()==’(’){ stack.pop(); }else{ stack.push(c[i]); } } return stack.size(); }}

题目题解import java.util.Stack;public class Solution { Stack<Integer> stack = new Stack(); Stack<Integer> helpStack = new Stack(); public void push(int node) { int helpStackTop = node; if (!helpStack.isEmpty()) { helpStackTop = Math.min(helpStack.peek(), helpStackTop); } stack.push(node); helpStack.push(helpStackTop); } public void pop() { if (stack.isEmpty()) { return; } stack.pop(); helpStack.pop(); } public int top() { return stack.peek(); } public int min() { return helpStack.peek(); }}