百度百科：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的抽象数据类型

来源《大话数据结构》

ADT Stack(栈)
Data同线性表。元素具有相同的类型，相邻的元素具有前驱和后驱关系。Operation:InitStack(*S);初始化操作，建立一个空栈DestroyStack(*S);若栈存在，销毁ClearStack(*S);若存在，清空StackEmpty(*S);若空栈返回true，否则falseGetTop(*S, *e);若存在，获得栈顶元素Push(*S, e);若存在，入栈Pop(*S, *e);若存在，出栈StackLength(S);若存在，返回元素个数.EndADT

栈的顺序存储结构实现——C语言描述

栈的定义：

typedef struct 
{int data[MAXSIZE];int top;
}Stack;

Operation: 初始化栈空间

//初始化栈空间
bool InitStack(Stack* s)
{s->data[MAXSIZE - 1] = { 0 };s->top = -1;return OK;
}

Operation: 入栈

//push，入栈操作
int Push(Stack* s, int e)
{//判断栈空间是否满了if (s->top == MAXSIZE - 1 || !s)return ERR;s->data[++s->top] = e;return OK;
}

Operation: 弹栈

//pop，弹栈操作
int Pop(Stack* s, int* e)
{//判断栈是否为空,或不存在if (s->top == -1 || !s)return ERR;*e = s->data[s->top--];return OK;
}

Operation: 销毁

//若栈存在，销毁
int DestroyStack(Stack* s)
{if (!s)return ERR;free(s);s = NULL;return OK;
}

Operation: 清空栈

//清空栈
bool ClearStack(Stack* s)
{if (!s || s->top == -1)return ERR;s->data[MAXSIZE - 1] = { 0 };s->top = -1;return OK;
}

Operation: 获取栈顶元素

//获取栈顶元素
int GetTopElem(Stack* s, int *e)
{if (!s || s->top == -1)return ERR;*e = s->data[s->top];return OK;
}

Operation: 返回栈的元素个数

//返回栈的元素个数
int StackLength(Stack* s, int* length)
{if (!s)return ERR;*length = s->top + 1;return OK;
}

顺序存储结构的双栈共享空间

栈的长度是固化的，是定义栈时就必须指定的。这势必造成一定栈空间得不到有效利用。例如如果一个栈能够容纳4K，而我们经常用的只是前2K，这就造成了后2K的利用率低下，而有效栈空间的内存是及其有限的且十分重要的，比如内核栈空间。因此栈空间的利用率从栈底往后延伸利用率不断降低。
为了解决这个问题也是为了提高栈空间的利用率，因此出现了同一个栈空间两个栈顶指针，分居栈空间两端。

栈的定义：

typedef struct
{int data[MAXSIZE];int topLeft;int topRight;
}Stack;

Operation: 初始化栈空间

bool InitStack(Stack* s)
{if (!s)return ERR;s->data[MAXSIZE - 1] = { 0 };s->topLeft = -1;s->topLeft = MAXSIZE - 1;return OK;
}

Operation: 入栈

int Push(Stack* s, int e, int StackNum)
{//判断栈空间是否满了,或为空if (s->topLeft + 1 == s->topRight || !s)return ERR;if (StackNum == 1){s->data[++s->topLeft] = e;}else if (StackNum == 2){s->data[--s->topRight] = e;}else{return ERR;}return OK;
}

Operation: 弹栈

int Pop(Stack* s, int* e, int StackNum)
{//判断栈是否为不存在if (!s)return ERR;if (StackNum == 1 && s->topLeft != -1){*e = s->data[s->topLeft--];}else if (StackNum == 2 && s->topRight != MAXSIZE){*e = s->data[s->topRight++];}else{return ERR;}return OK;
}

Operation: 销毁

//若栈存在，销毁
int DestroyStack(Stack* s)
{if (!s)return ERR;free(s);s = NULL;return OK;
}

Operation: 清空栈

//清空栈
bool ClearStack(Stack* s)
{if (!s)return ERR;s->data[MAXSIZE - 1] = { 0 };s->topLeft = -1;s->topRight = MAXSIZE;return OK;
}

Operation: 获取栈顶元素

int GetTopElem(Stack* s, int* e, int StackNum)
{if (!s)return ERR;if (StackNum == 1 && s->topLeft != -1){*e = s->data[s->topLeft];}else if (StackNum == 2 && s->topRight != MAXSIZE){*e = s->data[s->topRight];}else{return ERR;}return OK;
}

未完待续。