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

栈的抽象数据类型

来源《大话数据结构》

ADT Stack(栈)
Data
	同线性表。元素具有相同的类型，相邻的元素具有前驱和后驱关系。

Operation:
	InitStack(*S);初始化操作，建立一个空栈
	DestroyStack(*S);若栈存在，销毁
	ClearStack(*S);若存在，清空
	StackEmpty(*S);若空栈返回true，否则false
	GetTop(*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;
}

未完待续。