解析LIFO(FILO)结构栈(C语言版)
栈是计算机中超级超级常用的一种结构方式,也可以称之为思想。它的特点是对于存储的数据先进者后出,后进者先出,这种结构能够很好的保存上一次操作的状态,所以应用相当的广泛。
栈的定义:限定仅在表尾进行插入或删除操作的线性表。表尾被称为栈顶,表头被称为栈底,不含元素的空表称空栈。线性表有两种方式,对于栈来讲也是相同的两种,顺序栈和链栈。个人理解栈的功能实现是控制了对栈的使用接口,这个接口就是栈顶指针,每次出栈或入栈都只能通过栈顶指针来实现,这个限制成就了这种特点。
这个博客就当自己笔记了,写的可能随意点。
【顺序栈】
几个约定条件:
1. top=base 表示栈空 (或 int top ,top=0 )
2. top - base>=stacksize 表示栈满 (或 top==stacksize)
3. 栈顶元素表示:*(top-1)或 (base[top-1] )
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
#define SElemType int
typedef struct {
SElemType *base; // 存储空间基址
SElemType *top; // 栈顶指针也可定义为int top;
int stacksize ; // 栈的容量
} SqStack;
初始化顺序栈为空栈
Status InitStack (SqStack &S)
{ // 构造一个最大存储容量为 STACK_INIT_SIZE 的空栈S。
S.base=(ElemType*)malloc(STACK_INIT_SIZE*
sizeof(ElemType));
if (!S.base) exit (OVERFLOW); //存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
顺序栈的入栈操作
Status Push (SqStack &S, SElemType e)
{ //若栈的存储空间不满,则插入元素e为新的栈顶元素,并返回
//TRUE;否则返回FALSE。
if (S.top - S.base >= S.stacksize) //栈满,追加存储空间
{ S.base =(ElemType *) realloc ( S.base, (S.stacksize +
STACKINCREMENT) * sizeof (ElemType));
if (!S.base) exit (OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
// 追加的空间可存储元素数量为STACKINCREMENT
}
*S.top++ = e; //把e压入栈顶(先压栈,再top加一)
return OK;
}
顺序栈的出栈操作
Status Pop (SqStack &S, SElemType &e)
{ // 若栈不空,则删除S的栈顶元素,用e返回其值并返回OK;否则返ERROR
if (S.top == S.base) return ERROR; //栈空
e = *--S.top; //先top减一,再去掉栈顶元素
return OK;
}
顺序栈的取栈顶元素操作
bool GetTop (Stack S, ElemType &e)
{ // 若栈不空,则用e返回S的栈顶元素,并返回OK,否则返回ERROR
if (S.top == S.base)
return ERROR;
e = *(S.top-1); // 返回非空栈中栈顶元素
return OK;
}
以下是常用的操作
int StackLength (Stack S)
{ // 返回S的元素个数,即栈的长度。
return(S.top-S.base);
}
void ClearStack (Stack &S)
{ // 将 S 置为空栈。
S.top = S.base;
}
bool StackEmpty (Stack S){ //若栈 S 为空栈,则返回 TRUE,否则返回 FALSE。
if (S.top == S.base) return TRUE ;
else return FALSE;
}
【链栈】
结点定义:
typedef struct node
{ int data;
struct node *next;
} Lstack;
top为栈顶指针,每次插入或删除数据从栈顶开始。
链栈的入栈(压栈)操作
Status Push (Lstack *top, SElemType e)
{
Lstack *p = (Lstack*) malloc ( sizeof (Lstack));
if(!p) return ERROR; /*申请新结点失败*/
p->data = e;
p->next =top; /*top指针指向栈顶元素*/
top=p;
return OK;
}
链栈的出栈(弹栈)操作
Status Pop(Lstack *top , ElemType &e)
{
Lstack *p ;
if (top==NULL ) return ERROR ; //栈空,返回错误标志
p=top ;
e=p->data ; //取top指针所指的栈顶元素
top=p->next ; //修改栈顶指针
free(p);
return OK ;
}
上面就是两种栈的基本操作了,可以看出栈顶指针的是决定栈性质的重要因素。栈是一种常用的结构,一定要对出栈和入栈运用特别熟练。