408考研——栈代码题常见套路总结

本贴总结栈的实现和各种方法。栈作为一种操作受限的线性表，只要你会写线性表的实现，栈的实现就是手到擒来。和线性表一样，栈也有顺序存储和链式存储两种结构。由于比较冷门且和线性表大差不差，本帖只通过顺序栈来举例说明。

一.定义和初始化

和顺序表一样，顺序栈也是通过数组来实现的。与之前的写法不同，这次我们直接将length即栈中元素个数作为栈的成员变量。

struct SqStack{int data[25];int top;//虽然是栈顶指针，但其实本质为int型变量，也即数组下标~ int length;//栈中实际元素个数 
};

初始化时由于使用数组，无论栈中实际上有多少个元素，都会直接开辟出来数组的最大长度，因此我们需要将初值统一赋值为0。可能会有同志认为：如果插入或者删除的元素本身就是0，那么由于栈后进先出的特性，后面的空位也全是0，岂不是不能区分了？这点确实是个问题，因此我们将length直接作为了成员变量，实际上就是实际值和原生值的一个分界点。具体情况请看后面：

void InitStack(SqStack &S){for(int i=0;i<=24;i++)S.data[i]=0;//将预先开辟的数组每一位均置0 S.top=-1;//初始设置为负一，每次入栈先将栈顶指针加一，再插入元素 S.length=0; 
} 

与此同时top指针也即栈顶指针要设置为-1，因为数组的起始下标是0，这不难理解；length一开始也为0，这种定义方式有两种方式判空：即top=-1或者length=-0。

附加一个打印顺序栈的函数，太简单：

void PrintStack(SqStack &S){for(int i=0;i<=S.length-1;i++)cout<<S.data[i]<<" ";
}

二.入栈

实际上就是增删改查的增，这里一开始也命名为了Insert，后面通过typedef关键字改名为语义更好的Push。说句题外话，如果用C++11其实可以使用using和std::function的写法，这里为了兼容性博主还是使用了古典写法。

void Insert(SqStack &S,int value){if(S.top==24)return;S.top++;S.data[S.top]=value;S.length++;return;	
}
typedef void (*Push)(SqStack &S,int value);

对于栈空时top=-1的情形，入栈时应该先栈顶指针加1再赋值；如果一开始top为0，则是先赋值再加1，也即实际上是指向了栈顶后面的第一个空位。

三.出栈

出栈则是正好反过来的——先出栈再将指针值减一。这里所谓的出栈，实际上是将栈顶值赋值为0。这就回到了一开始的疑问——假设栈顶元素本身就为0怎么办？这就充分体现了length这个成员变量的作用：即便栈顶本身为0具有迷惑性，但只要其下标不再合法范围内（最大即length-1），那么这个0就是原始值0，而不是栈顶元素0！因此每次出栈一定要length--哦！

void Delete(SqStack &S){if(S.top==-1)//栈空return;S.data[S.top]=0;S.top--;S.length--; 	
}
typedef void (*Pop)(SqStack &S);

至于修改元素和查询元素，顺序栈实际上通过下标是可以随机访问的，即便理论上栈不能支持随访问，这里不多赘述~如下是测试用例，没什么bug~

void Delete(SqStack &S){if(S.top==-1)//栈空return;S.data[S.top]=0;S.top--;S.length--; 	
}
typedef void (*Pop)(SqStack &S);