目录
前言
栈
1.定义
2.栈的特点
3.栈的储存方式
3.1数组栈
3.2链栈
4.栈的基本操作(C语言)
4.1初始化
4.2判断是否满栈
4.3判断空栈
4.4 入栈
4.5 出栈
4.6获取栈顶元素
4.7遍历栈
4.8清空栈
完整代码示例
前言
大家好呀!今天我们开始学习新的线性表结构----栈,前面我们学习了链表以及链表的相关操作,那么栈跟链表有什么区别呢,操作如何呢?下面就一起来看看吧!
栈
1.定义
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
2.栈的特点
栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为出栈/退栈(POP)。栈也称为先进后出表。
3.栈的储存方式
栈的存储方式有两种:数组栈和链栈,即栈的数组存储和链式存储。
数组栈:数组栈是通过数组的形式去存放数据的,然后定义一个栈顶top指针指向当前栈顶的位置,这个位置也就是数组最后一个位置
链表栈:链表栈就是去通过链表节点的形式去储存数据,然后建立链式结构,对这个链表进行栈的相关操作,以达到栈的特点。二者的节点写法分别如下所示:
3.1数组栈
//01 数组栈
typedef struct sqstack {ElemType date[Maxsize];//数据int top;//数组栈的栈顶指针
}SqStack;
3.2链栈
//02链表栈
typedef struct linknode {ElemType date[Maxsize];//数据struct linknode* next;//指向下一个节点的指针
}* LiStack;
(本文主要讲解数组栈)
4.栈的基本操作(C语言)
栈的操作方法有以下方法:
#include<stdio.h>
#include<string.h>
#define Maxsize 10//最大空间容量//数据类型
typedef struct datatype {int age;char name[10];
}ElemType;//数组栈
typedef struct sqstack {ElemType date[Maxsize];//数据int top;//数组栈的栈顶指针
}Stack;initStack(Stack *L);//初始化栈isFull(Stack *L);//判断是否满栈isEmpty(Stack *L);//判断是否空栈push(Stack *L,ElemType date);//入栈pop(Stack *L);//出栈top_date(Stack* L);//获取栈顶元素show_stack(Stack *L);//遍历栈clear_stack(Stack *L);//清空栈元素
【注:以上均是数组栈的操作方法】
4.1初始化
让栈顶元素初始化为-1,即 L->top=-1;
//初始化
void initStack(Stack *L) {L->top = -1;
}
4.2判断是否满栈
判断满栈的方法就是看栈顶元素位置是否达到最大容量
//判断是否满了
int isfull(Stack *L) {if (L->top == Maxsize - 1) {//此时栈已满printf("The stack is full\n");return 1;}return 0;
}
4.3判断空栈
同样的判断是否空栈,只需要看栈顶top的位置是否为初始化的时候,即L->top==-1
//判断是否为空栈
int isEmpty(Stack *L) {if (L->top == -1) {printf("The stack is empty\n");return 1;}return 0;
}
4.4 入栈
进行入栈操作的时候,每次放入一个数据后,栈顶指针依次向上移动一位即可,如图所示:
//入栈
void push(Stack *L,ElemType date){if (isfull(L)) { //判断栈是否满了printf("failed to push\n");return;}else {L->date[L->top].age = date.age;strcpy(L->date[L->top].name, date.name);L->top+=1;}
}
4.5 出栈
进行出栈操作时,取出栈顶元素后,栈顶指针依次向下移动一位,如下所示:
//出栈
ElemType pop(Stack *L) {ElemType pop_date = { 0 };//先判断是不是空栈if (isEmpty(L)) {return pop_date;}pop_date = L->date[L->top];L->top--;return pop_date;
}
4.6获取栈顶元素
获取栈顶元素就不进行出栈操作,直接返回栈顶元素即可。
//获取栈顶元素(不出栈)
ElemType get_topdate(Stack* L) {return L->date[L->top];
}
4.7遍历栈
遍历栈,即当栈不为空的时候,从栈顶开始往下依次输出数据即可。
//遍历栈,输出数据
void show_stack(Stack *L) {if (!isEmpty(L)) {for (int i = L->top; i >= 0; i--) {printf("%d %s\n", L->date[i].age, L->date[i].name);}}
}
4.8清空栈
清空栈,只需要让栈顶指针回归到初始化即可,L->top=-1;
//清空栈
void clear_stack(Stack *L) {L->top = -1;//直接让栈顶回归就行了//之前的那些数据不会被删除,但是引索找不到了,下次入栈就会把这些数据给覆盖掉
}
完整代码示例
#include<stdio.h>
#include<string.h>
#define Maxsize 10//设置最大空间容量typedef struct datatype {int age;char name[10];
}ElemType;
// 数组栈
typedef struct sqstack {ElemType date[Maxsize];//数据int top;//数组栈的栈顶指针
}Stack;//初始化
void initStack(Stack *L) {L->top = -1;
}//判断是否满了
int isfull(Stack *L) {if (L->top == Maxsize - 1) {//此时栈已满printf("The stack is full\,");return 1;}return 0;
}//入栈
void push(Stack *L,ElemType date){if (isfull(L)) {printf("failed to push\n");return;}else {L->top+=1;L->date[L->top].age = date.age;strcpy(L->date[L->top].name, date.name);}
}//判断是否为空栈
int isEmpty(Stack *L) {if (L->top == -1) {printf("The stack is empty\n");return 1;}return 0;
}//出栈
ElemType pop(Stack *L) {ElemType pop_date = { 0 };//先判断是不是空栈if (isEmpty(L)) {return pop_date;}pop_date = L->date[L->top];L->top--;return pop_date;
}//获取栈顶元素(不出栈)
ElemType get_topdate(Stack* L) {return L->date[L->top];
}//清空栈
void clear_stack(Stack *L) {L->top = -1;//直接让栈顶回归就行了//之前的那些数据不会被删除,但是引索找不到了,下次入栈就会把这些数据给覆盖掉
}//遍历栈,输出数据
void show_stack(Stack *L) {if (!isEmpty(L)) {for (int i = L->top; i >= 0; i--) {printf("%d %s\n", L->date[i].age, L->date[i].name);}}
}int main() {Stack stack ;ElemType date[4] = { {15,"Jack"},{16,"Amy"} ,{15,"John"},{17,"Tom"}};initStack(&stack);for(int i=0;i<4;i++)push(&stack, date[i]);//依次入栈show_stack(&stack); //遍历栈ElemType pop_date= pop(&stack);//出栈printf("出栈元素为:%d %s\n", pop_date.age, pop_date.name);ElemType top_date = get_topdate(&stack);//获取栈顶元素printf("栈顶元素为:%d %s\n", top_date.age, top_date.name);clear_stack(&stack);//清空栈
}
//测试结果
/*17 Tom
15 John
16 Amy
15 Jack
出栈元素为:17 Tom
栈顶元素为:15 John*/
好啦,以上就是本期的全部内容了,我们下一期再见!see you!
分享一张壁纸: