highlight: vs2015
大家好，我是melo，一名大二上软件工程在读生，经历了一年的摸滚，现在已经在工作室里边准备开发后台项目啦。
不过这篇文章呢，还是想跟大家聊一聊数据结构与算法，学校也是大二上才开设了数据结构这门课，希望可以一边学习数据结构一边积累后台项目开发经验。
上次的文章，我们已经初步入门了数据结构:链表 想入门数据结构，却总是拜倒在链表的石榴裙下?，入门后你是否坚持下来了呢，是不是在栈堆里边徘徊不前了，这篇带你来攻破ta！
普通栈
知识点
后进先出(只能在一端操作)
image.png
只能对栈顶(表尾)进行插入和删除
image.png
保证栈顶先出即可
image.png
**空栈最好是top=-1
image.png
应用场景
1)子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2)处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3)表达式的转换 [中缀表达式转后缀表达式] 与求值(实际解决)。
4)二叉树的遍历。
5)图形的深度优先(depth一first)搜索法。
数组实现栈
Java版
注意构造器，是根据maxSize，然后记得this.maxSize=maxSize
class ArrayStack{
//栈的大小
private int maxSize;
//维护的数组
private int[] stack;
//栈顶
private int top;
public ArrayStack() {
}
public ArrayStack(int maxSize) {
this.stack = new int[maxSize];
this.top = -1;
this.maxSize=maxSize;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("栈已空");
}
return this.stack[top--];
}
public void push(int val){
if(isFull()){
throw new RuntimeException("栈已满");
}
stack[++top]=val;
}
public boolean isFull(){
return this.top==this.maxSize-1;
}
public boolean isEmpty(){
return this.top==-1;
}
}
C语言版
头文件SqStack.h
#include"Common.h"
typedef struct{
ElemType* elem;//存储空间基址
int top;//栈顶的下一位
int size;//当前分配的内存容量
int increment;//扩容时的增量
}SqStack;
Status initStack_Sq(SqStack& S, int size, int inc);//初始化顺序栈
Status DestroyStack_Sq(SqStack& S);//销毁顺序栈
Status StackEmpty_Sq(SqStack& S);//判断是否为空栈
void ClearStack_Sq(SqStack& s);//清空栈
Status Push_Sq(SqStack& S, ElemType e);//元素入栈
Status Pop_Sq(SqStack& S, ElemType& e);//元素出栈,用e返回
Status GetTop_Sq(SqStack S, ElemType& e);//取栈顶元素,用e返回
头文件Common.h
Status起别名(可观性更好一点，类似Java中的封装返回结果)
定义一些相关的Status返回值
定义ElemType，方便扩展，更换元素数据类型
#include<stdio.h>
#include<stdlib.h>
//定义一些返回值
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//默认使用int类型返回值
typedef int Status;
//需要更改元素类型就在此更换int
typedef int ElemType;
源文件SqStack.cpp
#include"Common.h"
#include"SqStack.h"
//初始化顺序栈
Status initStack_Sq(SqStack &S, int size, int inc) {
S.elem = (ElemType*)malloc(size * sizeof(ElemType));
if (S.elem == NULL || size <= 0 || inc <= 0) return ERROR;
S.size = size;
S.increment = inc;
S.top = 0;
return OK;
}
//销毁顺序栈
Status DestroyStack_Sq(SqStack &S) {
S.top = 0;
S.size = 0;
S.increment = 0;
free(S.elem);
/*此处后来发现,free操作并不会改变指针的值
(所以并不会变成NULL),只是让他所指向的内存空间失效了,
不能正常访问了而已
*/
/*
//若销毁失败
if (S.elem!=NULL) return ERROR;
*/
return OK;
}
//判断是否为空栈
Status StackEmpty_Sq(SqStack& S) {
return S.top == 0;
}
//清空栈
void ClearStack_Sq(SqStack& S) {
S.top = 0;
}
//元素入栈
Status Push_Sq(SqStack& S, ElemType e) {
if (S.top >= S.size) {
S.elem = (ElemType*)realloc(S.elem, sizeof(ElemType) * (S.size + S.increment));
}
if (S.elem == NULL) return ERROR;
S.elem[S.top] = e;
S.top++;
return OK;
}
//元素出栈,用e返回
Status Pop_Sq(SqStack& S, ElemType& e) {
if (StackEmpty_Sq(S)) return ERROR;
e = S.elem[--S.top];
return OK;
}
//取栈顶元素,用e返回
Status GetTop_Sq(SqStack S, ElemType& e) {
if (StackEmpty_Sq(S)) return ERROR;
e = S.elem[S.top-1];
return OK;
}
注意
此处有点小问题喔，就是栈的销毁操作，起初我是
free(S.elem);
//若销毁失败
if (S.elem!=NULL) {
return ERROR;
}
后来再回过头来看这篇博客的时候，发现free后其实S.elem并不会等于NULL，为此我又整理了一篇关于"迷途"指针的问题，具体可参照 迷途指针
链栈
**判空
当top指针刚好指向基址的时候，说明此时链栈为空
image.png
入栈(满了就扩容)
直接S.top==NULL，就是栈满了的情况
image.png
#include "allinclude.h" //DO NOT edit this line
Status Push_Sq2(SqStack2 &S, ElemType e) {
// Add your code here
//其实可以直接S.top==NULL即可
if(*(S.top)>=S.size){
S.elem=(ElemType*)realloc(S.elem,sizeof(ElemType)*(S.size+S.increment));
if(S.elem==NULL) return ERROR;
}
*(S.top)=e;
S.top++;
return OK;
}
进制转换
image.png
#include "allinclude.h"
void Conversion(int N, int rd)
{ // Add your code here
SqStack stack;
//初始化栈
InitStack_Sq(stack,10,1);
//N>0
while(N>0){
Push_Sq(stack,N%rd);
N/=rd;
}
//再出栈便可实现逆序打印出来(因为栈的特性)
while(!StackEmpty_Sq(stack)){
ElemType temp;
Pop_Sq(stack,temp);
printf("%d",temp);
}
}
括号匹配
(力扣)20有效的括号
最初版本
思路
- 特判右括号，判断是否跟栈顶元素匹配
- 若栈已经为空了，说明左括号不够用来匹配，无效
- 若不匹配，也无效
- 若匹配，则将匹配到的左括号出栈，暂时有效
- 其他情况(左括号)直接压入栈
- 最后出循环的时候，若栈中还有元素说明左括号没有被匹配完，也无效
细节
- 有不符合的直接return false
优化
- 奇数个直接无效
bool isValid(char * s){
int length = strlen(s);
//初始化为-1
int top=-1;
char stack[length] ;
//若本身就是奇数个,则直接无效
if(length%2!=0){
return false;
}
//遍历字符串
for(int i=0;i<length;i++){
//特判右括号
if(s[i]==')'){
//若栈已空或者栈顶元素不匹配,直接false
if(top<0||stack[top]!='('){
return false;
}
//否则将匹配到的左括号出栈
top--;
}
//同理
else if(s[i]=='}'){
if(top<0||stack[top]!='{'){
return false;
}
top--;
}
else if(s[i]==']'){
if(top<0||stack[top]!='['){
return false;
}
top--;
}
//若是左括号.直接加入栈
else stack[++top]=s[i];
}
//出来时若栈不为空,说明没有完全匹配掉
if(top!=-1){
return false;
}
return true;
}
改进版本
- 先统一处理右括号变成左括号，以便后续可以直接统一判断相不相等即可
细节
- 注意要先
//若是左括号.直接加入栈
else{
stack[++top]=s[i];
continue;
}
bool isValid(char * s){
int length = strlen(s);
//初始化为-1
int top=-1;
char stack[length] ;
//若本身就是奇数个,则直接无效
if(length%2!=0){
return false;
}
//遍历字符串
for(int i=0;i<length;i++){
//将右括号统一变成左括号,后续可以直接统一判断相不相等即可
if(s[i]==')') s[i]='(';
else if(s[i]=='}') s[i]='{';
else if(s[i]==']') s[i]='[';
//若是左括号.直接加入栈
else{
stack[++top]=s[i];
continue;
}
//若栈已空或者栈顶元素不匹配,直接false
if(top<0||stack[top]!=s[i]){
return false;
}else{
//否则将匹配到的左括号出栈
top--;
}
}
//出来时若栈不为空,说明没有完全匹配掉
if(top!=-1){
return false;
}
return true;
}
题解(最优)
用函数将右括号预处理包装起来了，而且如果不是右括号，会返回0，直接解决了上边的三个都不符合得再else和continue的情况
- 要用个ch来保存!!!!!!!!!!!!!!!!!!!!!!!!，因为只是传值，没有传引用
char pairs(char a) {
if (a == '}') return '{';
if (a == ']') return '[';
if (a == ')') return '(';
return 0;
}
bool isValid(char* s) {
int n = strlen(s);
if (n % 2 == 1) {
return false;
}
int stk[n + 1], top = 0;
for (int i = 0; i < n; i++) {
//注意要用个ch来保存
char ch = pairs(s[i]);
if (ch) {
if (top == 0 || stk[top - 1] != ch) {
return false;
}
top--;
} else {
stk[top++] = s[i];
}
}
return top == 0;
}
细节容易出错版本
我这里是直接compare(exp[i])，但是没有修改到exp[i]，他依然是右括号，下边仍然拿这个来测就错了
#include "allinclude.h"
int compare(char str){
if(str==')') return '(';
if(str=='}') return '{';
if(str==']') return '[';
return 0;
}
Status matchBracketSequence(char* exp, int n)
{ // Add your code here
//若是空字符串或者奇数长度,则直接不匹配
if(n==0||n%2!=0) return false;
SqStack stack;
InitStack_Sq(stack,n,1);
for(int i=0;i<n;i++){
//若是右括号
if(compare(exp[i])){
ElemType temp;
GetTop_Sq(stack,temp);
//若非空且匹配,则出栈
if(stack.top==0||exp[i]!=temp){
return false;
}else{
Pop_Sq(stack,temp);
}
}
//若是左括号则直接入栈
else{
Push_Sq(stack,exp[i]);
}
}
//若非空,说明左括号没有匹配完
if(!StackEmpty_Sq){
return false;
}
return true;
}
最后
- 最近偷懒了，一直有在认真记录笔记，但是却疏于整理，没有发出来，希望近几天可以抽出更多时间来继续整理队列，哈希表，排序等方面的知识
