逻辑结构：一对一关系(1:1)
存储结构：顺序栈与链栈，顺序栈常见
运算规则：后进先出（先进后出）
操作集合：
(1)StackInitiate(S) 初始化堆栈S
(2)StackNotEmpty(S) 堆栈S非空否
(3)StackPush(S,x) 入栈
(4)StackPop(S,d) 出栈
(5)StackTop(S,d) 取栈顶数据元素
(6)Destroy(S) 销毁
顺序栈：
定义
//栈的定义
typedef struct
{
int stack[MaxStackSize];
int size;
}SequenceStack;
初始化
//栈的初始化
void StackInitialize(SequenceStack *S)
{
S->size = 0;
}
入栈（压栈）
int StackPush(SequenceStack *S, int x)
{
if(S->size >= MaxStackSize)
{
printf("栈已满，无法再插入！\n");
return 0;
}
else
{
S->stack[S->size] = x;
S->size++;
return 1;
}
}
出栈
int StackPop(SequenceStack *S, int *d)
{
if(S->size <= 0)
{
printf("栈已空，无法再出栈！\n");
return 0;
}
else
{
S->size--;//栈的下标从0开始，获取栈顶元素时得先减一
*d = S->stack[S->size];
return 1;
}
}
取顶
//取栈顶数据元素
int StackTop(SequenceStack S, int *d)
{
if(S.size <= 0)
{
printf("栈已空\n");
return 0;
}
else
{
*d = S.stack[S.size - 1];
return 1;
}
}
总结：
1、顺序堆栈的定义与初始化与顺序表一样：用数组存数据、设立最大值（MaxSize）与当前大小（Size）；
2、入栈与出栈操作要点：先压后加，先减后弹；而顺序表的插入与删除则需要移动大量元素。
测试代码：
建立一个顺序堆栈，首先依次输入数据元素1, 2, 3,......,10，然后依次出栈堆栈中的数据元素并显示。
#include<stdio.h>
#include<stdlib.h>
#define MaxStackSize 10
#include "SequenceStack.h"
void main(void)
{
SequenceStack myStack;//声明
int i, x;
StackInitialize(&myStack); //初始化
for(i = 0; i < 10; i++)
{
StackPush(&myStack, i+1); //压栈
}
StackTop(myStack, &x); //取顶
printf("当前栈顶数据元素为：%d\n", x);
while(StackIsNotEmpty(myStack)) //判空
{
StackPop(&myStack, &x); //出栈
printf("%d\n", x);
}
}
分界线
链栈：
将头指针的一段作为栈顶指针。
定义：
typedef struct linklist
{
ElemType data;
struct linklist *next;
}SingleLinkList;
StackInit 初始化
void StackInit(SingleLinkList **head)
{
*head = (SingleLinkList *)malloc(sizeof(SingleLinkList));
if(*head == NULL)
{
exit(1); //异常结束；exit(0)：正常结束
}
(*head)->next = NULL;
}
StackNotEmpty 判空
int StackNotEmpty(SingleLinkList *head)
{
if(head->next == NULL) return 0;
else return 1;
}
StackPush 入栈
int StackPush(SingleLinkList *head, ElemType x)
{
SingleLinkList *p = (SingleLinkList *)malloc(sizeof(SingleLinkList));
if(p == NULL)
{
printf("内存空间不足无法插入！\n");
return 0;
}
p->data = x;
p->next = head->next;
head->next = p;
return 1;
}
StackPop 出栈
int StackPop(SingleLinkList *head, ElemType *x)
{
SingleLinkList *p;
p = head->next;
if(p == NULL)
{
printf("栈空，无法出栈");
return 0;
}
*x = p->data;
head->next = p->next;
free(p);
return 1;
}
StackTop 取顶
int StackTop(SingleLinkList *head, ElemType *x)
{
SingleLinkList *p = head->next;
if(p == NULL)
{
printf("栈已空！");
return 0;
}
*x = p->data;
return 1;
}
DestroyStack 销毁
void DestroyStack(SingleLinkList **head)
{
SingleLinkList *p,*q;
p = *head;
while(p != NULL)
{
q = p;
p = p->next;
free(q);
}
*head = NULL;
}
总结：
1、链式栈数据的写入与读取只能在栈顶操作，即不需要遍历找对应下标，直接从头结点后插入或删除；
2、其他的操作跟单链表的一蕉样。
测试代码：
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int ElemType;
#include "LinkStack.h"
void main(void)
{
SingleLinkList *head;
StackInit(&head);
int i, x;
for(i = 0; i < 10; i++)
{
StackPush(head, i+1);
}
StackTop(head, &x);
printf("%d\n", x);
while(StackNotEmpty(head))
{
StackPop(head, &x);
printf("%d ", x);
}
DestroyStack(&head);
}
