数据结构之栈
1.简介
栈（stack）又名堆栈，它是一种访问受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。故栈又称为先进后出（FILO—first in last out）线性表。
栈包含的基本操作：
1.入栈操作：在栈顶插入数据
2.出栈操作：在栈顶删除数据
3.栈中没有元素时，称为空栈
4.栈中存储达到预定上限，称为满栈
栈可以使用数组或链表作为物理存储结构，使用数组实现的队列称为顺序栈，使用链表实现的队列称为链式栈。本文针对最常用的顺序栈进行代码实现。
2.顺序栈
顺序栈的实现依赖数组作为底层物理存储结构，其特点是内存连续，并且数组的大小一般在初始时固定（如果使用动态内存可以修改）。
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
struct Stack {
int* buf;
int top;
int maxSize;
};
// 栈初始化
void init(struct Stack* st, int size)
{
st->top = 0;
st->maxSize = size;
st->buf = (int*)malloc(sizeof(int) * size);
}
// 栈内存释放
void destroy(struct Stack* st)
{
free(st->buf);
st->buf = NULL;
}
// 遍历栈
void display(struct Stack* st)
{
printf("stack size = %d, val = ", st->top);
int i = 0;
while (i < st->top) {
printf("%d ", st->buf[i]);
i++;
}
printf("\n");
}
// 判断栈是否为满
int isfull(struct Stack* st)
{
return st->top == st->maxSize;
}
// 判断栈是否为空
int isempty(struct Stack* st)
{
return st->top == 0;
}
// 入栈
int push(struct Stack* st, int val)
{
if (isfull(st)) { // 栈满，无法入栈，返回-1
return -1;
}
st->buf[st->top] = val;
return st->top++; // 返回入栈的位置
}
// 出栈
int pop(struct Stack* st)
{
if (isempty(st)) {
return -1;
}
return --st->top;
}
// 栈空：返回-1； 栈不空：返回0，pval执行的变量存储获取的栈顶元素
int getTop( struct Stack *st, int *pval )
{
if( isempty( st ) ){
return -1; // 无栈顶元素
}
*pval = st->buf[st->top - 1];
return 0;
}
int main()
{
struct Stack stack;
init(&stack, 5);
display(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
push(&stack, 50);
display(&stack);
printf("push ret = %d\n", push(&stack, 70)); // 栈满，无法入栈，返回-1
pop(&stack);
pop(&stack);
display(&stack);
printf("push ret = %d\n", push(&stack, 70));
display(&stack);
destroy(&stack);
return 0;
}
