当前位置： 首页 > news >正文

网站开发课程教学目标wordpress 侧边栏菜单

news 2025/11/8 13:35:24
网站开发课程教学目标,wordpress 侧边栏菜单,网站建设基础知识及专业术语,织梦怎么做淘客网站目录 引言 栈的定义 栈的分类 栈的功能 栈的声明 1.顺序栈 2.链式栈 栈的功能实现 1.栈的初始化 (1)顺序栈 (2)链式栈 (3)复杂度分析 2.判断栈是否为空 (1)顺序栈 (2)链式栈 (3)复杂度分析 3.返回栈顶元素 (1)顺序栈 (2)链式栈 (3)复杂度分析 4.返回栈的大…

目录

引言

栈的定义

栈的分类

栈的功能

栈的声明

1.顺序栈

2.链式栈

栈的功能实现

1.栈的初始化

(1)顺序栈

(2)链式栈

(3)复杂度分析

2.判断栈是否为空

(1)顺序栈

(2)链式栈

(3)复杂度分析

3.返回栈顶元素

(1)顺序栈

(2)链式栈

(3)复杂度分析

4.返回栈的大小

(1)顺序栈

(2)链式栈

(3)复杂度分析

5.元素入栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

6.元素出栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

7.打印栈的元素

(1)顺序栈

(2)链式栈

(3)复杂度分析

8.销毁栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

顺序栈和链式栈的对比

完整代码

1.顺序表

2.链式表

结束语

引言

在学习完链表之后，我们接下来学习数据结构——栈的内容。

栈的定义

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的有序集合。这种数据结构只允许在栈顶进行添加（push）或删除（pop）元素的操作。换句话说，最后添加到栈中的元素将是第一个被移除的，就像一叠盘子那样，我们只能从上面开始取放盘子。

如图所示：

栈顶（Top）：栈顶是栈中最后添加（push）元素的位置，也是最先被移除（pop）或查看（peek/top）的元素所在的位置。在栈的所有操作中，无论是添加、删除还是查看元素，都是针对栈顶进行的。因此，栈顶是栈中最活跃、最频繁被访问的位置。

栈底（Bottom）：栈底是栈中最早被添加进去的元素所在的位置，也是栈中唯一一个固定不变的位置（除非整个栈被清空）。在栈的常规操作中，栈底元素不会被直接访问，除非是将整个栈的内容倒序输出或者栈被完全清空。因此，栈底在栈的操作中扮演的是一个相对静态的角色。

栈的分类

栈可以分为顺序栈与链式栈。

如下图所示：

顺序栈：

链式栈：

栈的功能

我们要实现的栈的功能如下所示：

1.栈的初始化。
2.判断栈是否为空。
3.返回队头元素。
4.返回栈的大小。
5.元素入栈。

6.元素出栈。
7.打印栈的元素。
8.销毁栈。

栈的声明

1.顺序栈

顺序栈的声明需要一个指向一块空间的指针a，指向栈顶下一个元素的top，以及标志栈空间大小的capacity。

声明如下：

typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;

2.链式栈

链式栈的声明只需要一个top指针，以及栈的容量capacity。

当然这里需要链表的声明。

代码如下：

typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;

栈的功能实现

1.栈的初始化

顺序栈和链式栈都可以先初始为NULL。

(1)顺序栈

顺序栈可以将top设置为-1，capacity设置为0。

代码如下：

//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}
(2)链式栈

链式栈将size设置为0，top设置为NULL。

代码如下：

//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

2.判断栈是否为空

判断栈是否为空只需要判断top的指向。

(1)顺序栈

当top=-1则为空。

代码如下：

//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}
(2)链式栈

判断top是否指向NULL。

代码如下：

//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

3.返回栈顶元素

(1)顺序栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);// 断言确保栈不为空（即栈顶索引不小于0）assert(st->top >= 0);return st->a[st->top];
}
(2)链式栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

4.返回栈的大小

(1)顺序栈

由于在一开始将top设置为-1，需要top+1才能符合需要。

代码如下：

//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}
(2)链式栈
//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

5.元素入栈

注意：入栈需要检查空间是否足够。

(1)顺序栈

由于top设置的是-1，因此需要先腾出空间然后再将新元素x放在栈顶。

代码如下：

//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意：由于top初始化为-1，所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满，则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail：");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引，为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}
(2)链式栈
//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}
(3)复杂度分析

时间复杂度：由于顺序栈支持下标的随机访问并且我们以单链表的头作为栈顶，因此时间复杂度为O(1)。

空间复杂度：顺序表又可能需要进行扩容处理，最坏的情况是空间复杂度为O(n)。链式表每次入栈固定为一个节点，因此空间复杂度为O(1)。

6.元素出栈

(1)顺序栈
//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}
(2)链式栈
//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针，使其指向新的栈顶节点st->top = next;st->size--;
}
(3)复杂度分析

时间复杂度：由于顺序栈还是链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

7.打印栈的元素

(1)顺序栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印，直到栈底（但不包括索引-1）for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}
(2)链式栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈打印都需要遍历整个栈，因此时间复杂度为O(N)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

8.销毁栈

(1)顺序栈
//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}
(2)链式栈
//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}
(3)复杂度分析

时间复杂度：由于顺序栈还是链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

顺序栈和链式栈的对比

顺序栈链式栈
数据结构使用动态数组实现，元素在物理内存中连续存储使用链表实现，元素通过节点和指针连接，内存空间不连续
内存管理栈空间不足时可动态扩容，释放整个栈时一次性释放内存节点内存单独分配和释放，需要遍历链表以释放所有节点内存
时间效率可以通过数组下标直接访问栈内任意位置的元素，但是这不符合栈的定义由于每次都需要扩容操作，所以效率略比顺序栈低
空间效率顺序栈的扩容较大可能会造成空间的浪费内存使用相对灵活，但每个节点需要额外存储指针

完整代码

1.顺序表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);
//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意：由于top初始化为-1，所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满，则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引，为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(st->top >= 0);return st->a[st->top];
}//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印，直到栈底（但不包括索引-1）for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}

2.链式表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针，使其指向新的栈顶节点st->top = next;st->size--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}

结束语

本篇博客简要介绍了一下栈，接下来我们将接着学习与栈有些类似的另一个数据结构——队列。

数据结构——链式队列和循环队列

感谢各位大佬们的支持！！！

求点赞收藏关注！！！

十分感谢！！！

http://www.yayakq.cn/news/534027/

相关文章：

  • 建筑学网站做地接的网站
  • 郑州诺耀科技 - 郑州高端网站建设营销推广创世做的网站源码
  • asp商业网站源码php个人网站论文
  • 如何做响应式网站视频教程wordpress生产app中文
  • 大连网站建设佳熙科技公司wordpress 主题制作视频
  • 做不好的网站违法吗信用渭南网站建设
  • 德宏北京网站建设h5页面制作软件手机版
  • 建设网站的工作微信公众号直接上传wordpress
  • 如何更改网站备案信息怎么自己免费制作app
  • 营销型网站的建设要求都有什么作用网站群发软件
  • 建设网站实训代理网课
  • 软件技术有学做网站吗网站制作怎样做
  • 深圳网站优化技巧wordpress评论显示楼层
  • 自己网站做优化的有权利卖么即墨区城乡建设局网站官网
  • 宁波网站建设策划公司排名门户网站网页设计
  • 会议显示网站开发公司做海报的网站
  • 小公司做网站的好处心悦dnf免做卡网站
  • 郑州企业网站seowordpress排版教程视频
  • 江阴青阳道路建设网站办公室局域网怎么搭建
  • 电子商务网站建设需要做好哪些准备互联网平台推广怎么做
  • 在线免费做logo印章网站wordpress支持asp
  • 柳州住房城乡建设厅官方网站办宽带需要多少钱一月
  • wordpress下载类型主题南京百度快速排名优化
  • 加强网站建设管理办法中山哪里有好网站建设公司
  • 网站开发任务分解网站的动态图怎么做的
  • 交互性强的网站百度极速版app下载
  • 网站动态和静态wordpress 评论代码
  • 班级网站的建设wordpress做商城好吗
  • 网站打开是404错误手机兼职招聘
  • 网站运营与管理的心得体会西城网站建设浩森宇特