镇楼图
Pixiv:望月けい
〇、栈构建前的细节问题
采用顺序结构还是链式结构
实现的方式有所不同，如果是临时使用且不存在已造好的轮子的情况下，我建议直接顺序结构实现，而且空间要足够大，不存在满栈一说，越简单越好
由于栈本身操作受限，无论是顺序结构实现也好还是链式结构实现也好，之间的差别并不会特别影响时间复杂度
不过有一点要说明，在使用出栈时，顺序结构的栈并非真的删除了元素（其值还保留在原处），而链式结构的栈确确实实会删除元素
是否带头节点
在实现中，一般顺序结构不带头节点简化操作，而链式结构会带上头节点方便只有一个元素时删除
一、顺序栈
顺序栈的实现极其简单，只需要带上栈顶指针即可
typedef struct{
int value;
}element,*Element;
typedef struct{
Element data;//数组
int top;//栈顶指针
int len;//可容纳最大长度
}stack;
操作
(1)创建栈
void stack_create(stack &L,int length){
L.data = (Element)malloc(sizeof(element)*length);
L.top = 0;
L.len = length;
}
(2)清空栈
void stack_clear(stack &L){
L.top = 0;
}
(3)删除栈
void stack_delete(stack &L){
realloc(L.data,0);
}
(4)判断是否空栈/满栈
bool stack_iffull(stack L){
return (L.top == L.len) ? true : false ;
}
bool stack_ifempty(stack L){
return (!L.top) ? true : false ;
}
(5)入栈
void stack_push(stack &L,element e){
if(stack_iffull(L)){
printf("错误：满栈\n");
return;
}
L.data[L.top++] = e;
}
(5)出栈
element stack_pop(stack &L){
if(stack_ifempty(L)){
printf("错误：空栈\n");
return L.data[L.top+1];
}
return L.data[--L.top];
}
注：请注意所使用的栈是否包含虚拟节点，以及入栈前后、出栈前后栈顶指针的关系
入栈具体操作细节：先将top指针向上移动，然后再插入数据
出栈具体操作细节：先返回结果，然后再将top指针向下移动
二、链栈
链栈与顺序栈大体相同，但由于是链式结构，因此不必考虑长度原因，基本也不用考虑满栈的情况
typedef struct{
int value;
}element;
typedef struct __stacknode{
element data;
struct __stacknode *next;
}stacksize,*stack;
一般情况而言，为了方便实现，需要头指针
入栈时采用头插法，而出栈也只需要从头部删除即可
(1)创建栈
void stack_create(stack &L){
L = (stack)malloc(sizeof(stacksize));
L->next = NULL;
}
(2)清空栈
void stack_clear(stack &L){
stack p1 = L,p2 = L->next;
while(!p2){
p1 = p2;
p2 = p2->next;
free(p1);
}
}
(3)删除栈
void stack_delete(stack &L){
stack_clear(L);
free(L);
}
(4)判断是否空栈
bool stack_ifempty(stack &L){
return (!L->next) ? true : false;
}
(5)入栈
void stack_push(stack &L,element e){
stack newnode = (stack)malloc(sizeof(stacksize));
newnode->data = e;
newnode->next = L->next;
L->next = newnode;
}
(6)出栈
element stack_pop(stack &L){
if(stack_ifempty(L)){
printf("错误：空栈\n");
return L->data;
}
element e = L->next->data;
stack p =L->next;
L->next = L->next->next;
free(p);
return e;
}