数据结构-栈

栈即后进先出（LIFO）的线性表。

栈的常用算法有置栈空、判栈空、进栈、出栈、取栈顶等。

1.顺序栈

结构如下：

typedef struct

{

DataType data[MAXSIZE];

int top;

}SeqStack;

即，它需要一个栈顶top。

相关算法的关键步骤如下

//置栈空

void Initial(SeqStack *S)

{ S->top=-1; }

//判栈空

int IsEmpty(SeqStack *S)

{ return S->top==-1; }

//进栈

void Push(SeqStack *S,DataType x)

{ S->data[++S->top]=x; }

//出栈

DataType Pop(SeqStack *S)

{ return S->data[S->top--]; } //栈顶减1，返回已经出栈的元素

2. 链栈

结构如下：

typedef struct node

{

DataType data;

struct node *next; //知道结构名称的作用了吧，这里就要用到node

}LinkStack;

typedef struct

{

LinkStack *top;

}TopNode;

我们需要一个专门指向栈顶的指针（注意不是栈顶指针，而是指向栈顶的指针）。所以我们定义一个结构体TopNode，T.top就是指向栈顶的指针。或者我们用一个数组也行：

LinkStack * TopNode[1];

那么TopNode[0]就用来作指向栈顶的指针，函数的形参写成LinkStack * TopNode[]，传实参的时候用数组名TopNode，在函数内部就可以使用TopNode[0]。这种方面类似于函数形参是一个结构体TopNode *T，那么传实参的时候传&T，在函数内部使用T->top。

至于用数组和用结构哪个好，我觉得用结构还要用typedef定义类型，效率可能稍低。所以，用结构含义清楚，用数组效率更高。

/*头插法特点:无头结点，top指针始终指向最后插入的那个元素*/

LinkStack *CreListTou()

{ int x; LinkStack *S; TopNode T;

T.top=NULL;

scanf("%d",&x);

while(x!=-1) //输入-1代表结束

{

S=malloc(sizeof(LinkStack));

S->data=x;

/*关键代码: S->next等于T.top ，然后T.top反转来等于S*/

S->next=T.top;

T.top=S; //修改top指向

scanf("%d",&x);

}

return T.top;

}

//置栈空

void Initial(TopNode *T)

{ T->top=NULL; }

//进栈

void Push(TopNode *T,DataType x)

{

LinkStack *S;

S=malloc(sizeof(LinkStack));

S->data=x;

//与建栈时相同，将S的后继设置为原栈顶,S成为新的栈顶

S->next=T->top;

T->top=S;

}

//出栈

DataType Pop(TopNode *T)

{

LinkStack *p;

DataType x;

/*关键算法：先把T.top指向原栈顶的next，然后free掉原栈顶*/

p=T->top;

x=p->data;

T->top=p->next;// T.top指向原栈顶的next

free(p);

return x;

}

注意上面列出的只是算法的关键部分，并不完整，删减了一些“栈空”“栈满”的判断。