数据结构——栈

逻辑结构：在数据结构中栈只能在一段进行进栈和出栈操作的线性结构—所以满足后进先出的原则

物理结构：在存储结构上分为顺序栈和链栈

1.顺序栈

1.1顺序栈的结构体

#define MaxSize 10
typedef struct Stack
{int data[MaxSize];//数组用于存放栈中的元素int top;//栈顶指针
}SqStack;

1.2初始化顺序栈

//初始化栈
void InitStack(SqStack* S)
{S->top = -1;//栈顶指针为-1表示为空栈
}

1.3栈的判空

 //栈的判空
bool Empty(SqStack* S)
{if (S->top == -1){printf(" 这个栈是空栈\n");return true;}else{return false;}
}

1.4进栈操作

//进栈操作bool Push(SqStack* S)
{//进栈要先保证栈没有满if (S->top >= MaxSize){return false;}int x = 0;printf("请输入要进栈的元素：");scanf("%d", &x);S->data[++S->top] = x;//S->top=S->top+1;// S->data[S->top]=x;//先对指针加一，再进行赋值操作return true;
}

1.5出栈操作

//出栈操作
bool Pop(SqStack* S,int* x)
{//出栈要保证栈不空if (S->top == -1){return false;}//出栈操作只能取出栈顶元素*x = S->data[S->top--];//x=S->data[S->top];//s->top--;//这里的数据x依旧在内存当中并没有删除，只是在逻辑上删除了return true;
}

1.6读出栈顶元素

//读栈顶元素与出栈操作区别不大
bool GetTop(SqStack* S,int* x)
{//读栈顶元素要保证栈不空if (S->top == -1){return false;}*x = S->data[S->top];return true;
}

1.7完整的顺序栈代码

//顺序栈的基本操作typedef struct Stack
{int data[MaxSize];//数组用于存放栈中的元素int top;//栈顶指针
}SqStack;//初始化栈
void InitStack(SqStack* S)
{S->top = -1;//栈顶指针为-1表示为空栈
}//栈的判空
bool Empty(SqStack* S)
{if (S->top == -1){printf(" 这个栈是空栈\n");return true;}else{return false;}
}//进栈操作bool Push(SqStack* S)
{//进栈要先保证栈没有满if (S->top >= MaxSize){return false;}int x = 0;printf("请输入要进栈的元素：");scanf("%d", &x);S->data[++S->top] = x;//S->top=S->top+1;// S->data[S->top]=x;//先对指针加一，再进行赋值操作return true;
}//出栈操作
bool Pop(SqStack* S,int* x)
{//出栈要保证栈不空if (S->top == -1){return false;}//出栈操作只能取出栈顶元素*x = S->data[S->top--];//x=S->data[S->top];//s->top--;//这里的数据x依旧在内存当中并没有删除，只是在逻辑上删除了return true;
}//读栈顶元素与出栈操作区别不大
bool GetTop(SqStack* S,int* x)
{//读栈顶元素要保证栈不空if (S->top == -1){return false;}*x = S->data[S->top];return true;
}int main()
{SqStack S;int x = 0;//用于记录栈顶元素，或者读出栈顶元素InitStack(&S);//先进栈5个元素int i = 0;for (i = 0; i < 5; i++){Push(&S);}//出栈一个元素Pop(&S,&x);printf("出栈元素是%d\n", x);//读出此时的栈顶元素GetTop(&S,&x);printf("此时的栈顶元素是%d\n", x);return 0;
}

2.链栈

下面主要介绍不带头结点的链栈，并且把链表的表头当作链栈的栈顶。

2.1链栈的结构体和初始化

typedef struct LinkNode
{int data;struct LinkNode* next;
}LiStack;//初始化链栈
void InitLiStack(LiStack** L)
{(*L) = NULL;
}int main()
{LiStack* S=NULL;int x = 0;InitLiStack(&S);//这里涉及到二级指针//进栈操作,先进栈五个元素int i = 0;for (i = 0; i < 5; i++){Push(&S);}//出栈一个元素Pop(&S,&x);printf("出栈的元素是%d\n", x);//获取栈顶元素GetTop(S,&x);printf("当前栈顶元素是%d\n", x);
}

2.2入栈操作

//入栈
bool Push(LiStack** L)
{//对于链栈不存在栈满int x = 0;printf("请输入要进栈的整数:");scanf("%d", &x);LiStack* s = (LiStack*)calloc(1, sizeof(LiStack));if (s == NULL){return false;}s->data = x;s->next = (*L);(*L) = s;return true;
}

2.3出栈操作

//出栈
bool Pop(LiStack** L, int* x)
{//先判断栈是否为空 if (L == NULL){return false;}(*x) = (*L)->data;LiStack* p = (*L);(*L) = p->next;free(p);return true;
}

2.4读出栈顶元素

//获取栈顶元素
bool GetTop(LiStack* L,int* x)
{//先判断栈是否为空 if (L == NULL){return false;}(*x) = L->data;return true;
}

2.5链栈的整体代码

//不带头结点的链栈typedef struct LinkNode
{int data;struct LinkNode* next;
}LiStack;//初始化链栈
void InitLiStack(LiStack** L)
//这里涉及到二级指针
{(*L) = NULL;
}//入栈
bool Push(LiStack** L)
{//对于链栈不存在栈满int x = 0;printf("请输入要进栈的整数:");scanf("%d", &x);LiStack* s = (LiStack*)calloc(1, sizeof(LiStack));if (s == NULL){return false;}s->data = x;s->next = (*L);(*L) = s;return true;
}//出栈
bool Pop(LiStack** L, int* x)
{//先判断栈是否为空 if (L == NULL){return false;}(*x) = (*L)->data;LiStack* p = (*L);(*L) = p->next;free(p);return true;
}//获取栈顶元素
bool GetTop(LiStack* L,int* x)
{//先判断栈是否为空 if (L == NULL){return false;}(*x) = L->data;return true;
}int main()
{LiStack* S=NULL;int x = 0;InitLiStack(&S);//这里涉及到二级指针，传递的是栈顶指针的地址//进栈操作,先进栈五个元素int i = 0;for (i = 0; i < 5; i++){Push(&S);}//出栈一个元素Pop(&S,&x);printf("出栈的元素是%d\n", x);//获取栈顶元素GetTop(S,&x);printf("当前栈顶元素是%d\n", x);
}