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(" ");

}

// 判断栈是否为满

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 ", push(&stack, 70));   // 栈满，无法入栈，返回-1

pop(&stack);

pop(&stack);

display(&stack);

printf("push ret = %d ", push(&stack, 70));

display(&stack);

destroy(&stack);

return 0;

}