Stack栈
目录

• Stack栈
• • • • 1.顺序栈操作：
      • 2.顺序栈扩容：
      • 3.LC20:ValidParathese
      • • （1）方法1：简化思维：
        • （2）方法2：stack栈解决：
      • 4.链栈基本操作：
      • 5.栈和队列的应用：

1.顺序栈操作：

#include #include #includetypedef struct SqStack { int *base; //栈底指针 int top; //栈顶指针 int stacksize; //栈可用最大容量 } SqStack; //1.初始化栈操作 SqStack *InitStack(int n) { SqStack *s = (SqStack *)malloc(sizeof(SqStack)); s->base = (int *)malloc(sizeof(int) * n); s->stacksize = n; s->top = -1; return s; }//2.栈的销毁操作 void DestroyStack(SqStack *s) { if (s == NULL) return; free(s->base); free(s); return; }//3.判断栈是否为空 int StackEmpty(SqStack *s) { return s->top == -1; }//4.获取栈顶元素 int GetTop(SqStack *s) { return s->base[s->top]; }//5.入栈操作 int Push(SqStack *s, int val) { if (s == NULL) return 0; if (s->top == s->stacksize - 1) return 0; //栈已满 s->top++; //注意：这里栈顶指针指向的是栈顶元素故需要先++再赋值 s->base[s->top] = val; return 1; }//6.出栈操作 int Pop(SqStack *s) { if (s == NULL) return 0; if (StackEmpty(s)) return 0; s->top--; return 1; }//print操作 void print(SqStack *s) { if (s == NULL) return; printf("Stack : ["); for (int i = 0; i <= s->top; ++i){ i && printf(", "); printf("%d", s->base[i]); } printf("]\n"); return; }int main(){ srand(time(0)); #define MAX_OP 20 SqStack *s = InitStack(MAX_OP); for (int i = 0; i < MAX_OP; ++i) { int op = rand() % 4; int val = rand() % 100; switch (op) { case 0: case 1: case 2: { printf("push %d to the Stack = %d\n", val, Push(s, val)); } break; case 3: { printf("pop %d from the stack = ", GetTop(s)); printf("%d\n", Pop(s)); } break; } print(s); } #undef MAX_OP DestroyStack(s); return 0; }

文章图片

2.顺序栈扩容： 关键代码：

//SqStack扩容操作 int expand(SqStack *s) { int expand_size = s->stacksize; int *p; //顺序栈的循环扩容 while (expand_size) { p = (int *)realloc(s->base, sizeof(int) * (s->stacksize + expand_size)); if (p != NULL) break; //realloc扩容成功 expand_size >>= 1; //realloc扩容失败则将扩容容量extend缩小,再次尝试扩容 } if (p == NULL) return 0; s->stacksize += expand_size; s->base = p; return 1; }//5.入栈操作 int Push(SqStack *s, int val) { if (s == NULL) return 0; if (s->top == s->stacksize - 1) { if (!expand(s)) { printf(RED("fail to expand!\n")); return 0; } printf(GREEN("success to expand! the new size = %d\n"), s->stacksize); } s->top++; //注意：这里栈顶指针指向的是栈顶元素故需要先++再赋值 s->base[s->top] = val; return 1; }

完整代码：

#include #include #include#define COLOR(a, b) "\033[" #b "m" a "\033[0m" #define GREEN(a) COLOR(a, 32) #define RED(a) COLOR(a, 31)typedef struct SqStack { int *base; //栈底指针 int top; //栈顶指针 int stacksize; //栈可用最大容量 } SqStack; //1.初始化栈操作 SqStack *InitStack(int n) { SqStack *s = (SqStack *)malloc(sizeof(SqStack)); s->base = (int *)malloc(sizeof(int) * (n)); s->stacksize = n; s->top = -1; return s; }//2.栈的销毁操作 void DestroyStack(SqStack *s) { if (s == NULL) return; free(s->base); free(s); return; }//3.判断栈是否为空 int StackEmpty(SqStack *s) { return s->top == -1; }//4.获取栈顶元素 int GetTop(SqStack *s) { return s->base[s->top]; }//SqStack扩容操作 int expand(SqStack *s) { int expand_size = s->stacksize; int *p; //顺序栈的循环扩容 while (expand_size) { p = (int *)realloc(s->base, sizeof(int) * (s->stacksize + expand_size)); if (p != NULL) break; //realloc扩容成功 expand_size >>= 1; //realloc扩容失败则将扩容容量extend缩小,再次尝试扩容 } if (p == NULL) return 0; s->stacksize += expand_size; s->base = p; return 1; }//5.入栈操作 int Push(SqStack *s, int val) { if (s == NULL) return 0; if (s->top == s->stacksize - 1) { if (!expand(s)) { printf(RED("fail to expand!\n")); return 0; } printf(GREEN("success to expand! the new size = %d\n"), s->stacksize); } s->top++; //注意：这里栈顶指针指向的是栈顶元素故需要先++再赋值 s->base[s->top] = val; return 1; }//6.出栈操作 int Pop(SqStack *s) { if (s == NULL) return 0; if (StackEmpty(s)) return 0; s->top--; return 1; }//print操作 void print(SqStack *s) { if (s == NULL) return; printf("Stack : ["); for (int i = 0; i <= s->top; ++i){ i && printf(", "); printf("%d", s->base[i]); } printf("]\n"); return; }int main(){ srand(time(0)); #define MAX_OP 20 SqStack *s = InitStack(1); for (int i = 0; i < MAX_OP; ++i) { int op = rand() % 4; int val = rand() % 100; switch (op) { case 0: case 1: case 2: { printf("push %d to the Stack = %d\n", val, Push(s, val)); } break; case 3: { printf("pop %d from the stack = ", GetTop(s)); printf("%d\n", Pop(s)); } break; } print(s); } #undef MAX_OP DestroyStack(s); return 0; }

文章图片

3.LC20:ValidParathese Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.
An input string is valid if：

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

（1）方法1：简化思维： 可以将问题先简化为1种括号的匹配问题（判断左括号、右括号的数量是否相等），再扩展括号匹配的种类：

文章图片

1. +1可以等价为进入，-1可以等价为出去
2. 一对()可以等价为一个完整的事件
3. (())可以看做事件与事件之间的完全包含关系

1种括号的匹配问题：

文章图片


文章图片

多种括号的匹配问题：

#include #include #include using namespace std; bool judgeOne(char *s, int *i, int d) { bool flag = true; int j = d; while (s[*i] && flag) { switch (s[*i]) { case '(' : ++(*i); flag = judgeOne(s, i, d + 1); if (s[*i] == ')') {++(*i); flag &= true; } else if (s[*i] == ']' || s[*i] == '}' || s[*i] == '\0') flag = false; break; case '[' : ++(*i); flag = judgeOne(s, i, d + 1); if (s[*i] == ']') {++(*i); flag &= true; } else if (s[*i] == ')' || s[*i] == '}' || s[*i] == '\0') flag = false; break; case '{' : ++(*i); flag = judgeOne(s, i, d + 1); if (s[*i] == '}') {++(*i); flag &= true; } else if (s[*i] == ')' || s[*i] == ']' || s[*i] == '\0') flag = false; break; case ')' : case ']' : case '}' : return j = 0 ? false : true && flag; default : return false; } } return flag; }bool isValid(char * s) { int i = 0, len = strlen(s); bool flag = true; while (i < len && flag) { flag &= judgeOne(s, &i, 0); } return flag; }int main() { char s[1000]; cin >> s; cout << s << " isValid : " << isValid(s) << endl; return 0; }

注意：该程序虽然可以判断成功，但是执行的时间复杂度太高导致超时。

（2）方法2：stack栈解决：

#include using namespace std; typedef struct Stack { char *base; int top; int stackSize; } Stack; void InitStack(Stack &s, int n) { s.base = new char[100000]; // s->base = (int *)malloc(sizeof(int) * n); // s->base = malloc(stackSize); s.stackSize = n; s.top = -1; }; bool EmptyStack(Stack &s) { return s.top == -1; }void PushStack(Stack &s, char c) { s.top++; s.base[s.top] = c; }void PopStack(Stack &s) { s.top--; }char GetTop(Stack &s) { return s.base[s.top]; }bool isValid(string s) { int len = s.length(); Stack stack; InitStack(stack, len); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(': case '[': case '{': PushStack(stack, s[i]); break; case ')': if (EmptyStack(stack)) return false; if (GetTop(stack) != '(') return false; PopStack(stack); break; case '}': if (EmptyStack(stack)) return false; if (GetTop(stack) != '{') return false; PopStack(stack); break; case ']': if (EmptyStack(stack)) return false; if (GetTop(stack) != '[') return false; PopStack(stack); break; } } return EmptyStack(stack); }int main() { char s[1000]; cin >> s; cout << s << "isValid : " << isValid(s) << endl; return 0; }

4.链栈基本操作：

#include #include #includetypedef struct Node { int data; struct Node *next; } Node; typedef struct Stack { Node *top; int length; } LinkStack; //1.初始化结点 Node *InitNode(int val) { Node *p = (Node *)malloc(sizeof(Node)); p->data = https://www.it610.com/article/val; p->next = NULL; return p; }//2.初始化栈 LinkStack *InitStack() { LinkStack *s = (LinkStack *)malloc(sizeof(LinkStack)); s->top = NULL; s->length = 0; return s; }//3.销毁结点 void DestroyNode(Node *node) { if (node == NULL) return; free(node); return; }//4.销毁栈操作 void DestroyStack(LinkStack *ls) { if (ls == NULL) return; Node *p = ls->top, *temp; while (p != NULL) { temp = p->next; free(p); p = temp; } free(ls); return; }//5.链栈判空 int Empty(LinkStack *ls) { return ls->top == NULL; }//6.获取栈顶元素 int GetTop(LinkStack *ls) { return ls->top->data; }//7.链栈入栈 int Push(LinkStack *ls, int val) { if (ls == NULL) return 0; Node *p = InitNode(val); p->next = ls->top; ls->top = p; ls->length += 1; return 1; }//8.链栈出栈 int Pop(LinkStack *ls) { if (ls == NULL) return 0; if (Empty(ls)) return 0; Node *temp = ls->top; ls->top = ls->top->next; free(temp); ls->length -= 1; return 1; }void print(LinkStack *ls) { if (ls == NULL) return; printf("Stack[%d] : ", ls->length); for (Node *p = ls->top; p; p = p->next) { p != ls->top && printf(" "); printf("%d", p->data); } printf("\n"); return; }int main(){ srand(time(0)); #define MAX_OP 20 LinkStack *ls = InitStack(); for (int i = 0; i < MAX_OP; ++i) { int op = rand() % 4; int val = rand() % 100; switch (op) { case 0: case 1: case 2: { printf("push %d to the Stack = %d\n", val, Push(ls, val)); } break; case 3: { if (!Empty(ls)) { printf("pop %d form the Stack = ", GetTop(ls)); printf("%d\n", Pop(ls)); } } break; } print(ls); } #undef MAX_OP DestroyStack(ls); return 0; }

文章图片

5.栈和队列的应用： 【Data|【练习】04（栈相关操作）】
文章图片

推荐阅读

• 

  艾尔登法环PK地点有哪些 常用PK地点介绍
• 

  ps制作漂亮的彩色花纹字效果
• 

  猫在风水上代表什么 四个颜色的猫不能养
• 

  车门防撞条有什么坏处 汽车车门防撞条什么作用
• 

  马诗 石灰吟 竹石的诗意 运用了什么写作手法
• 

  贵州最高气温是多少度 最高气温多少度
• 

  ck公司的4p分析,用4P分析华为公司
• 

  UG4最低版怎么新建建模
• 

  米氮平片是抗抑郁的吗 抑郁症的药物有哪些
• 

  信用卡逾期多久停息挂账合适？
• 

  奶枣的具体做法 奶枣的棉花糖怎么选择
• 

  旗云2灯光开关示意图 旗云1灯光怎么用?
• 

  吃西兰花的注意事项
• 

  意大利哪个产区的葡萄酒最好？
• 

  网络薅羊毛是什么意思 羊毛电商是什么意思，电商薅羊毛群
• 

  消毒液消毒比例多少 消毒液消毒多长时间起作用
• 

  经常吃炒黑豆和核桃仁好吗
• 

  终究还是没那么强的气场 章子怡艺妓回忆录
• 

  水生少年梦歌词 少年梦歌词
• 

  鱼头炖什么最有营养价值

• 最新链表面试问题及其答案合集
• 算法|C语言版扫雷（递归实现自动展开）
• 个人的小白成长经历|【濡白的C语言】初学者-从零开始-5（模块化设计——函数，传值和传址）
• 经验分享|Tic Tac Toe简单井字棋
• Java|【数据结构与算法】——必知必会的排序算法你会几种
• 数据结构与算法|数据结构与算法 | 用Java语言实现顺序表真的不难
• CSAPP-datalab
• R编程中的数据结构介绍
• java|动态规划刷题攻略(二)