数据结构中最常用的一种结构---栈；
栈好比现实生活中的瓶子，瓶子的直径只能存放单个物品，先进后出，后进先出；
栈分为两种：一种是顺序栈，一种是链式栈
顺序栈：
typedef int ElemType;
#define MAXSIZE 100
typedef struct sequence_stack
{ ElemType data[MAXSIZE];
int top;
}SeqStack;
顺序栈相当于数组一样的存储结构，元素连续，而且操作基本上在栈顶，所以简单
由于顺序栈的操作位置基本在栈底，所以，不需要查找插入和删除的位置，也不需要移动元素，因而顺序栈的基本操作要比顺序表简单的多，其基本操作时间复杂度均为O（1）。下面给出顺序栈的部分操作的实现。
（1）初始化操作。顺序栈的初始化就是构造一个空的顺序栈S，初始分配的最大容量为maxsize，预设的需要扩容的增量为incresize。其主要操作是：申请存储控件，栈顶指针的初始值置为-1.
void InitStack_Sq(SqStack &S,intmaxsize=STACK_INIT_SIZE,intincresize=STACKINCREMENT)
{
S.stack=(ElemType *)malloc(maxsize*sizeof(ElemType));//顺序栈的初始分配最大空间
if(!S.stack)exit(1);//存储控件分配失败
S.top = -1;//置栈空
S.stacksize = maSxsize;//顺序栈的当前容量
S.incrementsize = incresize;//增补空间
} //InitStack_Sq
(2)求顺序栈的长度操作。统计顺序栈S中数据元素的个数，并返回统计结果。其主要操作是：返回顺序栈中栈顶指针的上一个位置。
intStackLength_Sq(SqStack S)
{
return S.top+1;
}//StackLength_Sq
(3)进栈操作。将一个新元素插入到顺序栈S的栈顶的上一个位置，作为新的栈顶元素。其主要操作是：先判断顺序栈是否已满，若已满，则重新分配空间，然后将栈顶指针加1，再将进栈元素插入到栈顶处。
boolPush_Sq(SqStack &S, ElemType e)
{//在顺序栈的栈顶插入元素e
if(S.top==S.stacksize-1)
{ S.stack=(ElemType *)realloc(S.stack,(S.stacksize+incrementsize)*sizeof(ElemType));//栈满，给顺序栈增补空间
if(!S.stack)
return false;//存储分配空间失败
S.stacksize+=S.incrementsize;
}
S.stack[++top]=e;//栈顶指针上移，元素e进栈
return true;}//Push_Sq
(4)出栈操作。将元素S的栈顶元素删除。其主要操作是：先判断栈顶指针书否为空，若非空，则将栈顶元素取出，然后将栈顶指针减1.
bool Pop_Sq(SqStack &S, ElemType &e)
{//删除顺序栈栈顶元素，并让e返回其值
if(S.top==-1)
return false;
e = S.stack[S.top--];
return false;
}//Pop_Sq
(5)取栈顶操作。取出顺序栈S的栈顶元素的值。其主要操作是：先判断顺序栈是否为空，若非空，则将栈顶元素取出。
bool GetTop_Sq(SqStack S,ElemType e)
{ //取顺序栈顶元素，并让e返回其值
if(S.top==-1)
return false;
e=S.stack[S.top];
return true;
}//GetTop_Sq
(6)判断栈空操作。判断顺序栈S是否为空。若S为空则返回true，否则返回false。
bool StackEmpty_Sq(SqStack S)
{
if(S.top==-1)
return true;
return false;
}
(7)撤销顺序栈操作。释放顺序栈S所占用的存储空间。
void DestroyStack_Sq(SqStack &S)
{
free(S.stack);
S.stacksize =0;
S.top = -1;
}//DestroyStack_Sq
链栈：
声明节点结构：
typedef char ElementType;
typedef structnode* LinkStack;struct node {
ElementType data;
LinkStack next;
};//初始化
初始化链栈：
void InitLinkStack(LinkStack *L) {
(*L) = NULL;
}//入栈
入栈：
void PushStack(LinkStack *L, ElementType x) {
LinkStack s;
s = (LinkStack)malloc(sizeof(struct node));
s->data = x;
s->next = (*L);//L是栈顶元素(*L) = s;//s成为新的栈顶元素}
出栈：
void PopStack(LinkStack *L, ElementType *x) {
if((*L)->next == NULL) {
printf("空栈");
} else {
LinkStack p;
*x = (*L)->data;
p = (*L);//标记栈顶(*L) = (*L)->next;
free(p);//出栈 }
}
打印栈：
void PrintNode(LinkStack L) {
while(L != NULL) {
printf("%c", L->data);
L = L->next;
}
printf("\n");
}
网友评论