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（栈相关操作）】
文章图片

推荐阅读

• 

  redmi|再爆新品！Redmi Watch 2将于28日发布 这次有点猛！
• 

  长沙跨境电商公司 长沙电商平台众联什么样，长沙比较大的电商公司有哪些
• 

  香榧吃了会不会胖 香榧相关介绍
• 

  如何解决人脸识别服务器超时问题？ 人脸识别服务器超时怎么办
• 

  贫血吃什么
• 

  违章代码1355是什么意思
• 

  财务报表分析程序
• 

  学什么舞蹈能提升气质
• 

  云朵简笔画 云朵简笔画怎么画
• 

  别客气用英语怎么说 welcome
• 

  分布式理论
• 

  golang获取命令行参数方法总结
• 

  玻尿酸丰胸多少钱_玻尿酸丰胸和假体丰胸哪种好
• 

  四年级我就这样长大了作文3篇
• 

  QQ飞车手游荣耀勋章第9期车大全：荣耀勋章第九期全部奖励总汇
• 

  唐朝皇帝后宫女人等级是如何，唐朝宫女等级制度
• 

  刚做完流产已经三天没吃饭只喝点水解
• 

  喊山红霞被判几年
• 

  gis罐体外卡式，gis罐体常用材料
• 

  大巴车载客人数 中型客车核载多少人

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