栈的定义

1、栈是一种重要的线性结构

2、栈(stack)是一个后进先出(LIFO)的线性表，要求只在表尾进行删除和插入等操作

//定义
typedef struct{
    ElemType *base;
    ElemType *top;
    int stacksize;
}sqStack;

包含三个数据项：base、top、stacksize。其中，base是指向栈底的指针变量，top是指向栈顶的指针变量。

创建一个栈

创建一个栈的步骤：

1、在内存中开辟一段连续的空间，用做栈的物理存储空间；

2、将栈顶、栈底地址赋值给sqStack类型变量(对象)的top和base域，并设置stacksize值，以便通过这个变量(对象)对栈进行各种操作。

#define STACK_INIT_SIZE 100
initStack(sqStack *s)
{
    //内存中开辟一段连续空间作为栈空间，首地址赋值给s->base
    s->base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s -> base) exit(0);                //分配空间失败
    s->top = s->base;           //最开始，栈顶就是栈底
    s->stacksize = STACK_INIT_SIZE;     //最大容量为STACK_INIT_SIZE
}

首先通过malloc()函数开辟一段内存空间，大小为预定义的存储空间初始分配量STACK_INIT_SIZE与每个栈元素类型ElemType大小的乘积。由于开始没有任何内容，因此栈顶与栈底相同，s->top=s->base。同时可用空间大小为STACK_INIT_SIZE，即s->stacksize=STACK_INIT_SIZE。