今天给大家分享两道栈的题目，因为博主用的是C写的，所以需要调用栈，但是每个代码都放一个栈显得冗余，所以先把栈放在这里吧。
typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps,STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); //只能尾插 if (ps->top==ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
🏆一、栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
通过题目我们知道pushed和poped的元素个数一样，而且里面都不会出现重复元素。我们通过栈来解决这道题目。
🖊①引入栈实现
1、我们引入一个栈，设立一个pos指针指向pushed数组，设立一个pt指针指向poped数组。我们先遍历pushed数组，如果pos指针指向的元素和pt指针指向的元素不相同，那么就入栈，然后pos++。
2、如果pos指针指向的元素和pt指针指向的元素相同，如果栈不空，我们就要判断栈顶元素和pt指向poped数组元素是否一样，如果一样就pop出栈，pt++，如果不一样就break。
3、遍历完pushed数组，我们成功的标志是pt指向的poped数组能否走完！也就等价于栈是否为空，如果不空，就返回false。最后栈空或者pt走完poped数组就返回true。
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) { ST st; StackInit(&st); int pos=0; int pt=0; while(pos<pushedSize) { if(pushed[pos]==popped[pt]) { pos++; pt++; while(!StackEmpty(&st)) { if(StackTop(&st)==popped[pt]) { StackPop(&st); pt++; } else break; } } else { StackPush(&st,pushed[pos]); pos++; } } while(!StackEmpty(&st)) { if(StackTop(&st)==popped[pt]) { StackPop(&st); pt++; } else { return false; } } StackDestory(&st); return true; }
🖊②模拟栈实现
1、上一种方式还有缺陷，我们其实对于不需要返回的空间，比如栈。如果我们不需要调用它的接口，比如这道题，大可不必引入栈，我们模拟一个栈(数组模拟)即可，开一个局部变量就行。
2、上面博主说过，判断为true的条件有两个，一个为pt指针能否成功遍历结束poped数组；一个为栈最后是否为空。上面的引入栈博主使用的是前一种方式，这里博主采用第二种方式，只需遍历一遍pushed数组，然后判断模拟栈是否为空。
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) { //top能不能返回到0 if(pushedSize<1) return true; int stack[pushedSize];//数组模拟栈 int top=0; for(int i=0,j=0;i<pushedSize;++i) { stack[top++]=pushed[i]; while(top>0&&stack[top-1]==popped[j]) { top--; j++; } } return top==0;//判断是否为空 }
🏆二、包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
🖊①倒栈求min
这道题目比较有意思的就是求栈中最小数的接口函数。
我们想写求栈中最小数的接口，创建两个栈st1和st2，st1用于push，st2只有在求栈中最小数的时候，我们把st1中的数据不断pop，push到st2，然后在这个过程中找到最小的返回；需要注意我们找到最小后还需要把st2的数据再pop，push到st1.
时间复杂度：O(N)
空间复杂度：O(N)
typedef struct { ST st1; ST st2; } MinStack; /** initialize your data structure here. */ MinStack* minStackCreate() { MinStack* obj=(MinStack*)malloc(sizeof(MinStack)); StackInit(&obj->st1); StackInit(&obj->st2); return obj; } void minStackPush(MinStack* obj, int x) { StackPush(&obj->st1,x); } void minStackPop(MinStack* obj) { if(!StackEmpty(&obj->st1)) { StackPop(&obj->st1); } } int minStackTop(MinStack* obj) { if(!StackEmpty(&obj->st1)) { return StackTop(&obj->st1); } return -1; } int minStackMin(MinStack* obj) { int min=StackTop(&obj->st1); while(!StackEmpty(&obj->st1)) { if(StackTop(&obj->st1)<min) min=StackTop(&obj->st1); StackPush(&obj->st2,StackTop(&obj->st1)); StackPop(&obj->st1); } while(!StackEmpty(&obj->st2)) { StackPush(&obj->st1,StackTop(&obj->st2)); StackPop(&obj->st2); } return min; } void minStackFree(MinStack* obj) { StackDestory(&obj->st1); StackDestory(&obj->st2); free(obj); }
🖊②辅助栈存最小
上面的时间复杂度能否再降呢？是可以的！因为我们上面主要麻烦的就是求最小需要倒栈，如果我们把最小的数都放到st2，只要取最小就到st2取。这样时间复杂度为O(1)。可能说的抽象，具体来说：
1、在st2 push进INT_MAX（这有利于我们存放第一个最小的数，也省去判断是否为第一个数），当我们往st1里面push数据时，把它和st2栈顶的元素比较，取最小存放到st2中，st2中栈的元素始终比st1多一个INT_MAX（需要注意）。
2、当调用取最小的接口时直接取st2的栈顶元素就是当前st1栈中的最小值，当pop掉一个元素时，st1和st2都需要pop掉栈顶。
我再来解释一下：
为什么往st1里面push数据，要和st2栈顶比较，并取最小放到st2呢？
比如这样，当往st1里面依次存-2，-1，0.对应st2里面存放的是-2，-2，-2。这样存会方便我们在取栈中最小时可以直接拿到，最小，因为只要st1中的-2没有被pop掉，栈中最小的始终为-2.而在pop时一并pop掉st1和st2的栈顶元素可以保证st2中始终存的是当前st1中最小的元素！！！
typedef struct { ST st1; ST st2; } MinStack; /** initialize your data structure here. */ MinStack* minStackCreate() { MinStack* obj=(MinStack*)malloc(sizeof(MinStack)); StackInit(&obj->st1); StackInit(&obj->st2); StackPush(&obj->st2,INT_MAX); return obj; } void minStackPush(MinStack* obj, int x) { int min=x<StackTop(&obj->st2)?x:StackTop(&obj->st2); StackPush(&obj->st1,x); StackPush(&obj->st2,min); } void minStackPop(MinStack* obj) { if(!StackEmpty(&obj->st1)) { StackPop(&obj->st2); StackPop(&obj->st1); } } int minStackTop(MinStack* obj) { if(!StackEmpty(&obj->st1)) { return StackTop(&obj->st1); } return -1; } int minStackMin(MinStack* obj) { if(!StackEmpty(&obj->st1))//因为我们刚开始存了一个int_max return StackTop(&obj->st2); return -1; } void minStackFree(MinStack* obj) { StackDestory(&obj->st1); StackDestory(&obj->st2); free(obj); }
