栈
栈(Stack)是运算受限的线性表,这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶,另一端称为栈底。
栈的顺序实现
// 顺序栈的类型定义
const int Maxsize = 6; // 顺序栈的容量
typedef struct seqstack
{
DataType data[Maxsize]; // 存储栈中数据元素的数组
int top; // 标志栈顶位置的变量,范围为 0 ~ (Maxsize - 1)
} SeqStk;
// 初始化
int InitStack(SeqStk *stk)
{
stk->top = 0;
return 1;
}
// 判栈空
int EmptyStack(SeqStk *stk)
{
if (stk->top == 0)
return 1;
else
return 0;
}
// 进栈
int Push(SeqStk *stk, DataType x)
{
if (stk->top == Maxsize - 1) { // 判断栈是否满
error("栈已满");
return 0;
} else {
stk->top++;
stk->data[stk->top] = x;
return 1;
}
}
// 出栈
int Pop(SeqStk *stk)
{
if (EmptyStack(stk)) { // 判断栈是否下溢
error("下溢");
return 0;
} else {
stk->top--; // 此时数据虽然仍在数组中,但它已经不是栈的数据元素了
return 1;
}
}
// 取栈顶元素
DataType GetTop(SeqStk *stk)
{
if (EmptyStack(stk)) {
return NULLData; // 栈空,返回空元素
} else {
return stk->data[stk->top];
}
}
栈的链接实现
// 链栈的类型定义
typedef struct node
{
DataType data;
struct node *next;
} LkStk;
// 初始化
void InitStack(LkStk *LS)
{
LS = (LkStk *)malloc(sizeof(LkStk));
LS->next = NULL; // 建立一个空栈
}
// 判栈空
int EmptyStack(LkStk *LS)
{
if (LS->next == NULL)
return 1;
else
return 0;
}
// 进栈
int Push(LkStk *LS, DataType x)
{
// 在进栈操作算法中采用前插操作,新增结点始终插入到头结点之后
LkStk *temp;
temp = (LkStk *)malloc(sizeof(LkStk)); // temp 指向申请的新结点
temp->data = x;
temp->next = LS->next; // temp 的 next 域指向原来的栈顶结点
LS->next = temp; // 指向新的栈顶结点。说明:LS 指向链表的头结点,LS->next 指向栈顶结点,栈顶结点为首结点。
}
// 出栈
int Pop(LkStk *LS)
{
LkStk *temp;
if (! EmptyStack(LS)) {
temp = LS->next; // temp 指向栈顶结点
LS->next = temp->next; // 原栈顶的下一个结点成为新的栈顶
free(temp); // 释放原栈顶结点空间
return 1;
} else {
return 0;
}
}
// 取栈顶元素
DataType GetTop(LkStk *LS)
{
if (! EmptyStack(LS)) {
return LS->next->data;
} else {
return NULLData;
}
}