栈
栈的概念
栈（stack）是一种特殊的线性表存储结构，其一端可以进行插入和弹出的操作，而另一端是封死的。
可以把栈想象成是一个柱状的容器。就比如一个乒乓球筒，我们只能在筒的一段进行乒乓球的放入和取出。
栈顶和栈的两种操作
栈顶就是栈的开口端，每次都是在栈顶处插入元素和删除元素。
（1）入栈：将新元素存入栈中，并作为新的栈顶元素；
（2）出栈：将栈顶元素弹出，并将其下面的元素作为新的栈顶元素。
栈的特性
栈有着先进先出的特性。假如入栈元素依次是 1、2、3 ，且中途没有元素出栈，那么最后所有元素出栈的顺序是 3、2、1 。
顺序栈
顺序栈基本概念
顺序栈是用数组来实现栈的存储结构，一般会定义一个栈顶 top，初始情况下 top 值为-1，表示栈为空，此时栈中无任何元素。
每当有元素入栈，top 就 +1 ; 有元素出栈， top 就 -1 。
顺序栈的入栈操作
顺序栈入栈操作图解
初始情况下的栈
元素1入栈
元素2入栈
元素3入栈
顺序栈入栈操作代码
//元素入栈
void push(SqStack *s, Elemtype x){
if(s->top == MAXSIZE - 1) return; //栈满
s->data[++s->top] = x;
}
顺序栈的出栈操作
顺序栈出栈操作图解
元素3出栈
元素2出栈
元素1出栈
顺序栈出栈操作代码
//元素出栈
void pop(SqStack *s, Elemtype *x){
if(s->top == -1) return; //栈空
*x = s->data[s->top--];
}
顺序栈完整程序
源代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1000
typedef int Elemtype;
typedef struct{
Elemtype data[MAXSIZE];
int top; //栈顶指针
}SqStack;
//初始化栈
void Init_SqStack(SqStack *s){
s->top = -1;
}
//判断栈是否为空
bool IsEmpty(SqStack *s){
return s->top == -1;
}
//元素入栈
void push(SqStack *s, Elemtype x){
if(s->top == MAXSIZE - 1) return;
s->data[++s->top] = x;
}
//元素出栈
void pop(SqStack *s, Elemtype *x){
if(s->top == -1) return;
*x = s->data[s->top--];
}
//取栈顶元素
Elemtype top(SqStack *s){
if(IsEmpty(s)){
printf("栈为空\n");
return -1;
}
return s->data[s->top];
}
int main(){
SqStack mystack;
Init_SqStack(&mystack);
for(int i = 1; i <= 5; i++)
push(&mystack, i);
printf("当前栈顶元素为: %d\n", top(&mystack));
int e;
pop(&mystack, &e);
printf("出栈元素为: %d\n", e);
printf("当前栈顶元素为: %d\n", top(&mystack));
printf("全部元素出栈：\n");
while(!IsEmpty(&mystack)){
printf("%d ", top(&mystack));
pop(&mystack, &e);
}
}
顺序栈运行测试
链栈
链栈基本概念
链栈是用链式存储结构实现的，在实现过程中，需要定义一个 top 指针保持指向当前栈顶。操作过程和链表有些相似。
链栈的入栈操作
链栈入栈操作图解
初始情况下的链栈
元素1入栈
元素2入栈
元素3入栈
链栈入栈操作代码
//入栈
void LinkStack_push(LinkStack *S, ElemType e){
LinkStacknode *node;
node = (LinkStacknode *) malloc(sizeof(LinkStack));
node->data = e;
node->next = S->top; //新节点的next指向此时的top
S->top = node; //top指针指向新的节点
S->length++;
}
链栈的出栈操作
链栈出栈操作图解
元素3出栈
元素2出栈
元素1出栈
链栈出栈操作代码
//出栈
void LinkStack_pop(LinkStack *S, ElemType *e){
if(IsEmpty(S)) //栈空
return;
LinkStacknode *del = S->top;
*e = del->data;
S->top = del->next; //top跳过出栈节点，指向出栈节点的下一节点
S->length--;
free(del); //释放内存
}
链栈完整程序
源代码
#include <stdio.h>
#include <stdlib.h>
//定义数据类型
typedef int ElemType;
//链栈的节点结构
typedef struct LinkStacknode
{
ElemType data; //存数据
struct LinkStacknode *next; //存下个节点的地址
} LinkStacknode;
//链栈的整体结构
typedef struct {
LinkStacknode *top;
int length;
} LinkStack;
//初始化链栈
void Create_LinkStack(LinkStack *S){
S->top = NULL;
S->length = 0;
}
//判断栈为空
bool IsEmpty(LinkStack *S){
return S->length == 0;
}
//入栈
void LinkStack_push(LinkStack *S, ElemType e){
LinkStacknode *node;
node = (LinkStacknode *) malloc(sizeof(LinkStack));
node->data = e;
node->next = S->top; //新节点的next指向此时的top
S->top = node; //top指针指向新的节点
S->length++;
}
//出栈
void LinkStack_pop(LinkStack *S, ElemType *e){
if(IsEmpty(S)) //栈空
return;
LinkStacknode *del = S->top;
*e = del->data;
S->top = del->next; //top跳过出栈节点，指向出栈节点的下一节点
S->length--;
free(del); //释放内存
}
//取栈顶
ElemType LinkStack_getTop(LinkStack *S){
if(IsEmpty(S)){
printf("栈为空\n");
return -1;
}
return S->top->data;
}
int main(){
LinkStack S;
Create_LinkStack(&S);
ElemType e;
ElemType a[5] = {3,6,7,9,10};
for(int i = 0; i < 5; i++)
LinkStack_push(&S, a[i]);
printf("栈顶元素：%d\n", LinkStack_getTop(&S));
LinkStack_pop(&S, &e);
printf("出栈元素：%d\n", e);
printf("全部元素出栈：\n");
while(!IsEmpty(&S)){
printf("%d ", LinkStack_getTop(&S));
LinkStack_pop(&S, &e);
}
return 0;
}
链栈运行测试
标签：LinkStack,出栈,入栈,top,元素,C语言,链栈,数据结构 From： https://www.cnblogs.com/MAKISE004/p/17062088.html