河南省路桥建设集团网站,wordpress 按月归档,已满18点此自动转,可以做网站的软件一、栈#xff08;stack#xff09;栈的概念#xff1a;① 栈是一种特殊的线性表#xff0c;它只允许在固定的一端进行插入和删除元素的操作。② 进行数据插入的删除和操作的一端#xff0c;称为栈顶 。另一端则称为 栈底 。③ 栈中的元素遵守后进先出的原则#xff0c;即…一、栈stack栈的概念① 栈是一种特殊的线性表它只允许在固定的一端进行插入和删除元素的操作。② 进行数据插入的删除和操作的一端称为栈顶 。另一端则称为 栈底 。③ 栈中的元素遵守后进先出的原则即 LIFO原则Last In First Out。压栈栈的插入操作叫做 进栈 / 压栈 / 入栈 入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。两道栈的选择题1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E 依次入栈然后再依次出栈则元素出栈的顺序是 。A 12345ABCDEB EDCBA54321C ABCDE12345D 54321EDCBA2.若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是 。A 1,4,3,2B 2,3,4,1C 3,1,4,2D 3,4,2,1答案:1.A2.c栈的结构数组栈和链式栈实现栈无非就两种结构数组结构 和 链式结构两种结构都可以实现。数组栈和链式栈哪种结构更好相对而言数组的结构实现更优尾插尾删的效率高缓存利用率高它的唯一缺点只是增容但是增容1次扩2倍对栈来说本身就比较合理是无伤大雅的。而链式栈虽然不会空间浪费用一个 malloc 申请一个但是链式栈存在一个致命的缺点单链表不好出数据必须要实现双向链表否则尾上删除数据将会异常麻烦。如果硬要使用链式栈① 如果用尾做栈顶尾插尾删要设计成双向链表否则删数据效率低。② 如果用头做栈顶头插头删就可以设计成单链表。本章栈的实现将采用数组结构二、栈的定义数组栈和顺序表定义差不多静态栈简单介绍下静态栈typedef char StackDataType;
#define N 10typedef struct Stack
{
StackDataType _array[N]; //数组
int _top; //栈顶
} Stack;解读N 给多了浪费给少了又不够用所以静态栈在实际中是不实用的。静态栈满了就不能扩大了而动态栈是 malloc 出来的不够了可以 realloc 扩容。虽然不实用但是我们也得认识它知道有这么一个东西。动态栈本章将采用动态栈实现typedef int StackDataType;typedef struct Stack
{StackDataType* array; //数组int top; //栈顶int capacity; //容量
} Stack;三、栈的实现完整代码实现了顺序表和链表栈的实现很简单直接放完整代码了Stack.h#pragma once#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int StackDataType;typedef struct Stack
{StackDataType* array; //数组int top; //栈顶int capacity; //容量
} Stack;void StackInit(Stack* ps);//初始化
void StackDestroy(Stack* ps);//销毁
void StackPush(Stack* ps, StackDataType x);//进栈
bool StackEmpty(Stack* ps);//判断栈是否为空
void StackPop(Stack* ps);// 出栈
StackDataType StackTop(Stack* ps);//返回栈顶数据
int StackSize(Stack* ps);//返回栈的大小Stack.c#include Stack.hvoid StackInit(Stack* ps)//初始化
{assert(ps);ps-array NULL;ps-top 0; // ps-top -1ps-capacity 0;
}void StackDestroy(Stack* ps)//销毁
{assert(ps);free(ps-array);ps-array NULL;ps-capacity ps-top 0;
}void StackPush(Stack* ps, StackDataType x)//进栈
{assert(ps);if (ps-top ps-capacity) {int new_capacity ps-capacity 0 ? 4 : ps-capacity * 2;StackDataType* tmp_arr (StackDataType *) realloc(ps-array, sizeof(StackDataType) * new_capacity);if (tmp_arr NULL) {printf(realloc failed!\n);exit(-1);}// 更新ps-array tmp_arr;ps-capacity new_capacity;}ps-array[ps-top] x;// 填入数据ps-top;
}bool StackEmpty(Stack* ps)//判断栈是否为空
{assert(ps);return ps-top 0; //等于0就是空就是真
}void StackPop(Stack* ps)// 出栈
{assert(ps);//assert(ps-top 0); //防止top为空assert(!StackEmpty(ps));ps-top--;
}StackDataType StackTop(Stack* ps)//返回栈顶数据
{assert(ps);//assert(ps-top 0); //防止top为空assert(!StackEmpty(ps));return ps-array[ps-top - 1];
}int StackSize(Stack* ps) //计算栈的大小
{assert(ps);return ps-top;// 因为我们设定top是指向栈顶的下一个所以top就是size
}Test.c#include Stack.hvoid TestStack1()
{Stack st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);StackPush(st, 4);StackPop(st);StackPop(st);StackPop(st);StackPop(st);//StackPop(st);printf(%d, StackTop(st));StackDestroy(st);
}void TestStack2()
{// 入栈1 2 3 4Stack st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);// 出栈4 3 2 1while (!StackEmpty(st)){printf(%d , StackTop(st));StackPop(st);}StackDestroy(st);
}void TestStack3()
{// 入栈1 2 3 4Stack st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);// 提前出栈4 3printf(%d , StackTop(st));StackPop(st);printf(%d , StackTop(st));StackPop(st);// 入栈5 6StackPush(st, 5);StackPush(st, 6);// 出栈6 5 2 1while (!StackEmpty(st)){printf(%d , StackTop(st));StackPop(st);}StackDestroy(st);
}int main()
{//TestStack1();//TestStack2();TestStack3();return 0;
}四、一道栈的OJ题力扣链接20. 有效的括号难度简单给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例 1输入s ()输出true示例 2输入s ()[]{}输出true示例 3输入s (]输出false提示1 s.length 104s 仅由括号 ()[]{} 组成bool isValid(char * s){}解析代码这道题用C写就很简单用C语言写就需要创建一个栈。可以用数组什么的但不好我们刚写了一个栈直接把Stack.h和Stack.c复制粘贴过去,把头文件删掉再把typedef int StackDataType; 改成typedef char StackDataType;typedef char StackDataType;typedef struct Stack
{StackDataType* array; //数组int top; //栈顶int capacity; //容量
} Stack;void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, StackDataType x);
bool StackEmpty(Stack* ps);
void StackPop(Stack* ps);
StackDataType StackTop(Stack* ps);
int StackSize(Stack* ps);void StackInit(Stack* ps)//初始化
{assert(ps);ps-array NULL;ps-top 0; // ps-top -1ps-capacity 0;
}void StackDestroy(Stack* ps)//销毁
{assert(ps);free(ps-array);ps-array NULL;ps-capacity ps-top 0;
}void StackPush(Stack* ps, StackDataType x)//进栈
{assert(ps);if (ps-top ps-capacity) {int new_capacity ps-capacity 0 ? 4 : ps-capacity * 2;StackDataType* tmp_arr (StackDataType *) realloc(ps-array, sizeof(StackDataType) * new_capacity);if (tmp_arr NULL) {printf(realloc failed!\n);exit(-1);}// 更新ps-array tmp_arr;ps-capacity new_capacity;}ps-array[ps-top] x;// 填入数据ps-top;
}bool StackEmpty(Stack* ps)//判断栈是否为空
{assert(ps);return ps-top 0; //等于0就是空就是真
}void StackPop(Stack* ps)// 出栈
{assert(ps);//assert(ps-top 0); //防止top为空assert(!StackEmpty(ps));ps-top--;
}StackDataType StackTop(Stack* ps)//返回栈顶数据
{assert(ps);//assert(ps-top 0); //防止top为空assert(!StackEmpty(ps));return ps-array[ps-top - 1];
}int StackSize(Stack* ps) //计算栈的大小
{assert(ps);return ps-top;// 因为我们设定top是指向栈顶的下一个所以top就是size
}bool isValid(char* s) {Stack st;StackInit(st);while (*s){if ((*s () || (*s [) || (*s {)){StackPush(st, *s);}else{//栈是空且遇到右括号了栈里面没有左括号if (StackEmpty(st)){StackDestroy(st);return false;}StackDataType top StackTop(st);StackPop(st);if ((top ( *s ! ))|| (top [ *s ! ])|| (top { *s ! })){StackDestroy(st);return false;}}s;}//如果栈不是空说明还有左括号没出完不合题意//此时StackEmpty返回false相反栈是空返回truebool ret StackEmpty(st);StackDestroy(st);return ret;
}本篇完下一篇队列
