数据结构----线性表（栈及其栈的实现）C语言学习笔记

栈：线性逻辑结构

栈的分类

顺序栈：顺序存储结构实现的栈

链式栈：链式存储结构实现的栈

栈的性质

性质：先进后出或后进先出。

栈顶“指针”和栈底“指针”

栈底“指针”：标记栈底位置
栈顶“指针”：标记栈顶位置
这里的“指针”并非真的的指针，这里这是为了方便描述。

应用场景

1.函数调用的实现（递归）
2.业务需求，倒着的逻辑。比如：撤销，网页页面，历史记录
3.物理上的堆栈：先进后出
4.c++ STL库stack

溢出的概念（为什么要判空和判满？）

1.上溢：栈满之后，继续入栈。
2.下溢：栈空之后，继续出栈。

栈的实现

1.顺序栈

栈底“指针”指向下标为0的位置。
栈顶“指针”指向位置，有两个位置指向：

1）指向真正栈顶元素的位置

操作：

I.初始化

II.入栈

III.出栈

IV.得到栈顶元素

2）指向真正栈顶元素的下一位置

I.初始化 top=0；

//定义一个顺序栈
typedef struct {int* data;  //指针模拟开数组int top;    //栈顶“指针”
}stack;
//初始化
stack initstack(){stack s;s.data= (int*)malloc(sizeof(int*) * maxsize);if (s.data == NULL) {printf("分配空间失败。\n");}else {s.top = -1;    //指向真正的栈顶元素的位置//s.top=0;     指向真正栈顶元素的下一位置}return s;
}

II.入栈 s->data[s->top]=k; s->top++;

//入栈
void PushStack(stack* s,int k) {//判满if (s->top == maxsize - 1) {printf("栈满。\n");}else {//指向真正的栈顶元素的位置/*s->top++;s->data[s->top] = k;*///指向真正栈顶元素的下一位置s->data[s->top] = k;s->top++;}
}

III.出栈 s->top--;

//出栈
void PopStack(stack* s) {//判空if (s->top == -1) {printf("空栈，无法出栈。\n");}else {s->top--;int x = s->data[s->top];printf("删除了栈顶元素%d \n", x);}
}

IV.得到栈顶元素 top--；s->data[s->top];

//得到栈顶元素
int GetStack(stack* s) {/*指向真正的栈顶元素的位置return s->data[s->top];*///指向真正栈顶元素的下一位置s->top--;return s->data[s->top];
}

2.链栈------基于单链表实现的

I.初始化：初始化一个带头结点的的单链表

//定义一个链栈
struct stack{int data;struct stack* next;
};
typedef stack* LinkStack;
//初始化
LinkStack initStack() {LinkStack s = (stack*)malloc(sizeof(stack));if (s == NULL) {printf("空间分配失败。\n");}else {s->next = NULL;}return s;
}

II.入栈：头插法

//入栈
LinkStack PushStack(LinkStack s,int k) {stack* p = (stack*)malloc(sizeof(stack));if (p == NULL) {printf("入栈时，空间分配失败。\n");}else {//头插p->data = k;p->next = s->next;s->next = p;}return s;
}

III.出栈：删除首元结点

//出栈
LinkStack PopStack(LinkStack s) {if (s->next == NULL) {printf("空栈，无法出栈。\n");}else {s->next= s->next->next;}return s;
}

IV.得到栈顶元素：首元结点的元素

//得到栈顶元素
LinkStack GetStack(LinkStack s) {if (s->next == NULL) {printf("空栈，无栈顶元素。\n");}else {int a=s->next->data;printf("栈顶元素是%d \n", a);}return s;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/89376.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/89376.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！