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

推荐阅读

• 

  香薰蜡烛可以带上飞机吗，香薰蜡烛可以带上飞机么
• 

  国务院联防联控机制|国家药监局：特事特办，第一时间完成疫苗的审批
• 

  工业废气处理方法有哪些
• 

  养小鬼什么意思?？梦见有人养小鬼什么意思
• 

  又何加焉句式
• 

  护目镜消毒处理流程
• 

  兔子拔毛是怎么回事
• 

  空心菜如何繁殖 空心菜如何育种
• 

  本地数据库上传到云服务器数据库笔记 本地数据库怎么上传服务器
• 

  学生平板电脑
• 

  邢台一天SEO... 抖音经营类目在哪里设置
• 

  关于网络信息的资料 关于网络信息内容的资料
• 

  林内锅炉显示L0怎么回事 ,无非就是这几个原因
• 

  这份情如此亲切
• 

  却道天凉好个秋全诗
• 

  HSTS 示例讲解
• 

  电商运营夏天生活用品改上什么
• 

  君子兰用高锰酸钾泡多长时间 高锰酸钾泡多长时间
• 

  喝蜂蜜水能解决便秘吗
• 

  一加7pro支持红外遥控吗怎么设置 一加7pro支持红外遥控吗

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