1.栈的定义
栈（stack）是限制仅在表一端进行插入或删除操作的线性表。
（1）通常称插入或删除的一端为栈顶（Ｔｏｐ），另一端为栈底（Ｂｏｔｔｏｍ）
（2）当表中没有元素时称为空栈
（3）栈为后进先出（last in first out）线性表，也称为ＬＩＦＯ表
2.顺序栈
顺序栈的类型定义
#define stacksize 1000; //预分配的栈的空间最多为1000个元素
typedef int datatype;
struct seqstack
{
datatype data[stacksize];
int top;
};
顺序栈的基本操作
栈置空
/**
* Description:栈置空
*/
void initstack(struct seqstack *s)
{
s -> top = -1;
}
栈判空
/**
* Description:判断栈空
*/
int stackempty(struct seqstack *s)
{
int flag;
flag = (s -> top == -1)? 1 : 0;
return flag;
}
判栈满
/**
* Description:判断栈满
*/
int stackfull(struct seqstack *s)
{
int flag;
flag = (s -> top == stacksize)? 1 : 0;
return flag;
}
入栈、出栈操作
/**
* Description:进栈操作
*/
void push(struct seqstack *s,x)
{
s -> top ++;
if(stackfull)
exit("stack overflow\n"); //数组溢出
s -> data[s -> top] = x;
}
/**
* Description:出栈操作
*/
void pop(struct seqstack *s)
{
if(stackempty(s))
exit("stack is empty!\n"); //数组为空
return s -> data[s -> top --];
}
获取栈顶元素
/**
* Description:获取栈顶元素
*/
datatype stacktop(struct seqstack *s)
{
if(stackempty(s))
exit("stack is empty!\n"); //数组为空
return s -> data[s -> top];
}
3.链栈
链栈的类型定义
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
typedef struct stacknode
{
datatype data;
struct stacknode *next;
}stacknode;
typedef struct
{
stacknode *top; //栈顶指针
}linkstack;
注意：
（1）linkstack结构类型定义是为了函数体中修改top指针本身
链栈的基本运算
栈置空
/**
* Description:栈置空
*/
void initstack(linkstack *s)
{
s -> top = NULL;
}
判断栈空
/**
* Description:判断栈空
*/
int stackempty(linkstack *s)
{
int flag;
flag = (s -> top == NULL)? 0 : 1;
return flag;
}
入栈、出栈操作
/**
* Description:入栈
*/
void push(linkstack *s, datatype x)
{
struct stacknode *p;
p = malloc(sizeof(struct stacknode));
p -> data = x;
p -> next = s -> top;
s -> top = p;
}
/**
* Description:出栈
*/
datatype pop(linkstack *s)
{
datatype x;
struct stacknode *p = s -> top;
if(stackempty(s))
exit("stack is empty!\n");
x = p -> data;
s -> top = p -> next;
free(p);
return x;
}
获取栈顶元素
/**
* Description:获取栈顶元素
*/
datatype stacktop(linkstack *s)
{
if(stackempty(s))
exit("stack is empty!\n");
return s -> top -> data;
}