栈原理及实现
1.栈的定义
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶 （Top），另一端称为栈底 （Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为 LIFO 表。
2.图示
1，初始化
实现思路：用指定大小的length实例化一个SeqStack<T>，然后使top指针指向-1。
2，进栈
实现思路：将top指针加1，然后将新结点插入到top指针指向的位置。
3，出栈
实现思路：消灭top指向的结点，并使top指针减1。
4，获取栈顶元素
实现思路：与出栈相似，只是不改变栈的状态而已。
5，判断是否栈空
实现思路：如果top指针是否等于-1，如果是则返为空栈。
6，判断是否栈满
实现思路：检查top指针的值是否等于数组的长度，如果是则为栈满。
#define MAXSIZE<栈最大元素数>
typedef struct
{ datatype data [MAXSIZE];
int top;
}SeqStack;
SeqStack*Init_SeqStack()
{ SeqStack *s;
s = malloc( sizeof(SeqStach) );
s - > top = -1;
return s;
}
int Empty_SeqStack(SeqStack *s)
{
return (s->top == -1 ? 1 : 0 );
}
int Full_SeqStack( SeqStack *s)
{
return (s->top == MAXSIZE - 1 ? 1 : 0 );
}
int Push_SeqStack ( SeqStack*s, datatype x)
{
if ( ! Full_SeqStack( s) )
return 0; // 栈满不能入栈
s-> data [ ++ s-> top ]= x ;
return 1 ;
}
int Pop_SeqStack ( SeqStack*s, datatype *x)
{
if( ! Empty_SeqStack(s) )
return 0 ; //栈空不能再出栈
*x = s -> data [ s -> top -- ] ;
return 1;
}
int Top_SeqStack ( SeqStack *s)
{
if( ! Empty_SeqStack(s) )
return 0 ; //栈空无元素
*x = s -> data [ s -> top ] ;
return 1;
}