C/C++顺序栈和链栈详解(附代码)_Smallc.的博客-程序员宝宝_栈的top与bottom

技术标签: 算法  C++  C  链表    指针  数据结构  


前言

栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。(队列为FIFO)

本文目的:
1.掌握栈的特点及其描述方法
2.掌握链式存储结构实现一个栈
3.掌握链栈的各种基本操作
4.掌握栈的典型应用的算法
栈子系统题目要求:
1.设计一个选择式菜单。
2.设计一个整型数据元素的链栈。
3.编写入栈、出栈和显示栈中全部元素的程序。
4.编写一个把十进制数转换成八进制数的应用程序。

一、栈的顺序结构及其实现

1:顺序栈概念理解

既然栈是线性表的特例,那么栈的顺序存储其实就是线性表的顺序存储的简化,也叫顺序栈。线性表是用数组实现的,那么顺序栈也可以用数组来实现。接下来我们来模拟数组存放数据的情况。

最初,栈是"空栈",即数组是空的,top 值为初始值 -1(这样当存放数据时top的值总是与其对应的数组角标相等),如下图所示
在这里插入图片描述
首先向栈中添加元素 1,我们默认数组下标为 0 一端表示栈底,因此,元素 1 被存储在数组 a[1] 处,同时 top 值 +1,如下图所示
在这里插入图片描述
采用以上的方式,依次存储元素 2、3 和 4,最终,top 值变为 3,如下图所示
在这里插入图片描述

2:入栈(压栈)实现方法

根据上面的概念我们可以得出,顺序栈可以简化为一个存放数据的数组,以及指向栈顶位置的top指针(不是真的指针,而是代表一个指向栈顶位置)。

#pragma once
#include<iostream>
#include <cstdio>
#include<cstdlib>
typedef int Status;
typedef int ElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 10
#define make (struct student*)malloc(sizeof(struct student));
using namespace std;
typedef struct
{
    
	ElemType stack[MAXSIZE];//构建一个顺序栈存储元素
	int top;		//默认值为-1而不是0 -1代表代表的是栈空
}Stack;

Status push_stack(Stack* s, ElemType e) //入栈
{
    
	if (s->top >= MAXSIZE - 1) //栈满退出
		return ERROR;
	s->top++;   //增加一位
	cout << "要插入的数据是" << e << endl;
	s->stack[s->top] = e;//赋值
	return OK; //返回成功结果
}

3:出栈(弹栈)及其实现方法

其实,top 变量的设置对模拟数据的 “入栈” 操作没有实际的帮助,它是为实现数据的 “出栈” 操作做准备的。
比如,将 下1图 中的元素 2 出栈,则需要先将元素 4 和元素 3 依次出栈。需要注意的是,当有数据出栈时,要将 top 做 -1 操作。因此,元素 4 和元素 3 出栈的过程分别如 下1图下2图 所示:
在这里插入图片描述
在这里插入图片描述


Status pop_stack(Stack* s, ElemType* e) //出栈
{
    
	if (s->top == -1) //空栈
		return ERROR;
	*e = s->stack[s->top]; //取得要删除的值 这里没有-1是因为栈的起始数量是-1哦
	cout << "要删除的数据是" << *e << endl;
	s->top--;  //弹栈
	return OK;
}

4:顺序栈输出其数据

void show_stack(Stack s)
{
    
	int j;
	j = s.top;  //得到目前已有的数据个数
	while (j > -1)
	{
    
		cout << "第"<<j<<"个元素是" << s.stack[j] << endl;
		j--;
	}
	cout << "栈已空" << endl;
}

5:主函数

int main()
{
    
	Stack* head=(Stack*)malloc(sizeof(Stack));//初始化一个栈
	head->top = -1;//初始top指针为-1 代表空栈
	ElemType e;	
	push_stack(head, 10);
	push_stack(head, 20);
	push_stack(head, 30);
	push_stack(head, 40);
	show_stack(*head);
	pop_stack(head, &e);
	show_stack(*head);
}

二、栈的链式存储结构

1.链栈概念理解

链栈的实现思路同顺序栈类似,顺序栈是将数顺序表(数组)的一端作为栈底,另一端为栈顶;链栈也如此,通常我们将链表的头部作为栈顶,尾部作为栈底,如下图在这里插入图片描述

将链表头部作为栈顶的一端,可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶,意味着:
在实现数据"入栈"操作时,需要将数据从链表的头部插入;
在实现数据"出栈"操作时,需要删除链表头部的首元节点;

2.初始化链栈

链栈的初始化与链表的初始化类似,直接上代码

#pragma once
#include<iostream>
#include <cstdio>
#include<cstdlib>
typedef int Status;
typedef int ElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 10
#define make (struct student*)malloc(sizeof(struct student));
using namespace std;

typedef struct StackNode
{
    
	ElemType data;  //数据
	int count; //记录当前栈内数据个数
	struct StackNode* next; //指向下一个节点指针
}StackNode;

StackNode* init_stack(ElemType e)
{
    
	StackNode* head = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针
	head->next = NULL;
	head->data = e;
	cout << "栈底元素为" << e << endl;
	head->count = 1;	//初始化数据数量为1,头指针自身也算一个数据
	return head; 
}

3.链栈元素入栈

例如,将元素 1、2、3、4 依次入栈,等价于将各元素采用头插法依次添加到链表中,每个数据元素的添加过程如图所示
在这里插入图片描述
也就是头指针先指向空,之后随着数据的插入,先插入的数据存在于栈底,而头指针永远指向着栈顶,也就是最新插入的数据。其实和链表的数据插入差不多,只不过不能随意插入位置,而只能插在栈头,当然这样相对于链表反而更简单了。


StackNode* push_stack(StackNode* head, ElemType e)//入栈 在栈L中插入数据e
{
    
	//StackNode* p=head;//临时指针p
	StackNode* s = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针
	s->data = e; //添加数据e
	cout << "插入元素" << e << endl;
	s->count = ++head->count;//元素数量增加
	cout <<"当前元素个数为" << s->count << endl;
	s->next = head; //指向上一元素
	head = s; //头指针指向栈顶
	return head;//成功返回
}

4.链表元素出栈

下图所示的链栈中,若要将元素 3 出栈,根据"先进后出"的原则,要先将元素 4 出栈,也就是从链表中摘除,然后元素 3 才能出栈,整个操作过程如图所示:
在这里插入图片描述
链栈删除元素的情况也就是栈顶的数据被删除,类似于链表元素的头指针指向下一个数据,然后释放原有头指针指向的数据。即head直接指向下一个节点,然后直接释放原先节点指向的数据。

StackNode* pop_stack(StackNode* head, ElemType* e)
{
    
	StackNode* p;	//临时指针
	if (head == NULL) //判断链栈非空
		return ERROR;
	*e = head->data; //取得要删除元素 也就是栈顶元素
	cout << "要删除的元素是" << *e << endl;//输出要删除的元素
	p = head->next; //p指向将被删除数据的下一个节点,以便头指针移位
	free(head); //释放被删除数据的空间
	head = p;	//头指针指向新位置
	head->count--;	//头指针指向的数据减少
	cout << "当前元素个数为" << head->count << endl;
	return head;
}

5.显示链栈元素

我们在链栈里通过count来记录了链栈中当前元素的数量,一次可以通过count来判断是否还有数据可以输出。

void show_stack(const StackNode *head)
{
    				//使用const可以确保head指向的数据不被修改
	int num = head->count;//取得元素个数
	for (int i = 1; i <= num; i++)
	{
    
		cout << "第" << i << "个元素是" << head->data<<endl;//输出数据 从上至下输出
		head = head->next; //指向下一个数据
	}
}

6.主函数


int main()
{
    
	StackNode* head;
	ElemType e;
	head = init_stack(1);
	head = push_stack(head, 2);
	head = push_stack(head, 3);
	head = push_stack(head, 4);

	head = pop_stack(head, &e);
	head = pop_stack(head, &e);
	head = pop_stack(head, &e);
	//head = pop_stack(head, &e); //再删除一次就会报错 这是由于head不存在
	show_stack(head);
}

三、栈子系统

链栈的出栈和入栈上面已经交代清楚了比较难的就是如何把十进制的数据用八进制形式来输出。接下来提供一种方法。
在这里插入图片描述
可以发现当数据不能再被整除时,此时形成的数据,就是十进制转换为八进制的结果,例如1201%8=2···2···6··1,也就是2261,通过计算器可以发现这是正确的。那么如何得到每一次数据的最简余数呢------递归。下面来看代码:

void change(int m) //用递归来将十进制换为八进制
{
    
	if (0 == m)
		return;
	int tmp = m % 8;
	m = m / 8;
	change(m);
	printf("%d", tmp);

}

比较简单,不解释了。
那么解决了这个进制转换问题后,栈子系统的代码便直接可以轻松写出。

#include <algo.h>
typedef struct StackNode
{
    
	ElemType data;  //数据
	int count; //记录当前栈内数据个数
	struct StackNode* next; //指向下一个节点指针
}StackNode;

StackNode* init_stack(ElemType e)
{
    
	StackNode* head = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针
	head->next = NULL;
	head->data = e;
	cout << "栈底元素为" << e << endl;
	head->count = 1;	//初始化数据数量为1,头指针自身也算一个数据
	return head; 
}
StackNode* push_stack(StackNode* head, ElemType e)//入栈 在栈L中插入数据e
{
    
	//StackNode* p=head;//临时指针p
	StackNode* s = (StackNode*)malloc(sizeof(StackNode));//s是指向结构体StackNode的指针
	s->data = e; //添加数据e
	cout << "插入元素" << e << endl;
	s->count = ++head->count;//元素数量增加
	cout <<"当前元素个数为" << s->count << endl;
	s->next = head; //指向上一元素
	head = s; //头指针指向栈顶
	return head;//成功返回
}
StackNode* pop_stack(StackNode* head, ElemType* e)
{
    
	StackNode* p;	//临时指针
	if (head == NULL) //判断链栈非空
		return ERROR;
	*e = head->data; //取得要删除元素 也就是栈顶元素
	cout << "要删除的元素是" << *e << endl;//输出要删除的元素
	p = head->next; //p指向将被删除数据的下一个节点,以便头指针移位
	free(head); //释放被删除数据的空间
	head = p;	//头指针指向新位置
	head->count--;	//头指针指向的数据减少
	cout << "当前元素个数为" << head->count << endl;
	return head;
}
void show_stack(const StackNode *head)
{
    				//使用const可以确保head指向的数据不被修改
	int num = head->count;//取得元素个数
	cout << "元素总个数为" << num << endl;
	for (int i = 1; i <= num; i++)
	{
    
		cout << "第" << i << "个元素是" << head->data<<endl;//输出数据 从上至下输出
		head = head->next; //指向下一个数据
	}
	
} 
void change(int m) //用递归来将十进制换为八进制
{
    
	if (0 == m)
		return;

	int tmp = m % 8;
	m = m / 8;
	change(m);
	printf("%d", tmp);

}
void transformation_stack(StackNode* head)
{
    
	int times = 1;
	cout << "元素个数" << head->count << endl;
	int num = head->count;//取得当前元素个数
	for(times;times<=num;times++)
	{
    
		change(head->data);//调用转换函数
		cout << endl;//输出换行符
		head = head->next;//指向下一个数据
	}
}
int main()
{
    
	int choose;
	ElemType e;
	cout << "输入栈底元素" << endl;
	cin >> e;
	StackNode* head = init_stack(e);//初始化链栈
	cout << "*******************" << endl;
	cout << "*1 ……入栈       *" << endl;
	cout << "*2 ……出栈       *" << endl;
	cout << "*3 ……显示       *" << endl;
	cout << "*4 ……数制转换   *" << endl;
	cout << "*0 ……返回       *" << endl;
	cout << "*******************" << endl;
	while (1)
	{
    
		cout << "请选择功能" << endl;
		scanf("%d", &choose);
		switch (choose)
		{
    
		case 1:
		{
    
			ElemType e;
			cout << "输出要插入的数据" << endl;
			cin >> e;
			head = push_stack(head, e);
			cout << "插入成功" << endl;
			break;
		}
		case 2:
		{
    			
			ElemType e;
			head = pop_stack(head,&e);
			cout << "删除成功" << endl;
			break;
		}
		case 3:
		{
    
			show_stack(head);
			break;
		}
		case 4:
		{
    
			transformation_stack(head);
			break;
		}
		case 0:
		{
    
			cout << "程序结束" << endl;
			system("pause");
			exit(0);
			//return 0;
		}
		default:
			break;
		}
	}
}

完整代码下载:
栈子系统完整代码

四、链栈与顺序栈优缺点对比

对比顺序栈和链栈,它们的时间复杂度是一样的,都是O(1)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间的浪费问题,但是它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些的内存开销,但对于栈的长度无限制。所以题目的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预测,有时候小,有时候很大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会好一些。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Zhangsama1/article/details/119581560

智能推荐

用UBuntu开发OpenGL程序1_炫_愛羊的博客-程序员宝宝

开发环境:UBuntu9.10 Desktop x86,NetBeans6.8,OpenGL2.1安装开发需要的库在Mesa网站上,目前最新的版本是7.7,支持OpenGL2.1,但是受限制于具体驱动程序,并不能保证完全支持所有的API.可以下载源代码编译安装,不过先从简单的开始,在UBuntu上面安装已经编译好的Mesa库和开发文件。首先确保编译器等库已经

c#——转义符"\""_刘海燕的博客-程序员宝宝

转义符"\""一、转义符的表示:\二、转义符的作用:下面我们看两个例子:例1:输出abnamespace ConsoleApplication2{ class Program { static void Main(string[] args) { string s = "ab";

wide-dhcpv6的dhcp6c配置_普朗克常量的博客-程序员宝宝_dhcp6c

源码里面已经有man文档,直接打开用如下命令打开就好man -l wide-dhcpv6/dhcp6c.conf.5DHCP6C.CONF(5)                                           BSD File Formats Manual                                           DHCP6C.CO

Sequelize 大于_记一次线上Sequelize连接池“ResourceRequest timed out”排查历程_weixin_39901943的博客-程序员宝宝

问题描述线上服务不定时出现“ResourceRequest timed out”错误,导致部分用户无法正常使用业务洗系统,每次重新启动服务之后问题消失,若干小时之后又会出现同样的问题。服务器错误日志如下图所示:问题排查过程第一步,尝试线上复现问题,最终失败,因为一重启服务问题就消失,无法在线上稳定复现,所以尝试在本地复现问题。第二步,通过查看线上错误日志,初步估计是连接池问题,所以阅读Sequel...

福建师范大学计算机科学与技术研究生复试,2020福建师范大学考研复试内容及复试方式 考研复试流程..._weixin_39731107的博客-程序员宝宝

2020福建师范大学考研复试内容及复试方式是什么样的?根据福建师范大学2019年硕士研究生招生复试录取办法中提到,福建师范大学研究生复试学院根据学科(类别)、专业(领域)特点及办学特色确定复试内容和复试方式。福建中公教育小编给考生整理如下:(一)主要内容1.专业素质和能力(1)大学本科阶段学习情况及成绩。(2)全面考核考生对本学科(类别)、专业(领域)理论知识和应用技能的掌握程度,利用所学理论发现...

Java Web 发送和接收数据servlet中文乱码问题 pageEncoding与charset的作用,response和request的setCharacterEncoding 的作用。_蓝盒子itbluebox的博客-程序员宝宝

Java Web 发送数据中文乱码问题 pageEncoding与charset的作用,response和request的setCharacterEncoding 的作用。在jsp代码中的头部往往有这两行代码&lt;%@ page language="java" contentType="text/html; charset=UTF-8" pageEncoding="UTF-8"%&g...

随便推点

AJAX框架汇总_yanick的博客-程序员宝宝

 引此文原出于AJAX Patterns网站的一篇《Ajax Frameworks》的wiki文章,很早前我就注意到,后来在国内也有人翻译了,不过最近发现此wiki还是在不断添加维护中,截止此文发布前,作者又添加了好几个新诞生的AJAX开发工具,所以我决定重新翻译一遍,并且时常注意原文发布状态,一有新的内容立马也翻译过来,做到同步:)此翻译稿很大一部分内容出自国内出现的那个先前版本,我

深度学习系列(八):自编码网络多层特征学习_on2way的博客-程序员宝宝_深层自编码器

上节我们谈到了三层自编码网络的特征学习,并将其学习到的特征用于实际分类实验中,并与传统的PCA特征提取方法作了实验对比,发现在三层网络下自编码学习的特征能更好用于分类,达到分类准确率更高,本节我们将再一次探索自编码网络的特征学习问题,并且是深层网络的自编码学习。首先来探索四层网络的自编码问题,还是以手写体为例,网络抽象成下面这样子: 假设我们第一层隐含层用200个神经元,第二层K个(可以固定也可

如何在 Ubuntu 中管理和使用逻辑卷管理 LVM_qwfys200的博客-程序员宝宝_ubuntu查看逻辑卷

如何在 Ubuntu 中管理和使用逻辑卷管理 LVMhttps://linux.cn/article-5954-1.html

Android控制软键盘的弹出和隐藏_Android-kongqw的博客-程序员宝宝

弹出软键盘 前提:必须要有一个可以编辑的控件(我知道的只有EditText),并且当前已经获取焦点/** * 弹出软键盘 */public void openKeyboard(View view) { // 获取焦点 editText2.setFocusable(true); editText2.setFocusableInTouchMode(true);

java fx 给按钮加颜色_JavaFx:9、Button按钮以及简单介绍设置背景颜色和外边框等问题..._sxtybzwm的博客-程序员宝宝

package fx.com;import javafx.application.Application;import javafx.event.ActionEvent;import javafx.event.EventHandler;import javafx.geometry.Insets;import javafx.scene.Group;import javafx.scene.Scene;...

MySql安装异常解决:1130 - Host ‘11*.17*.6*.23*‘ is not allowed to connect to this MysQL server_JavaPub-rodert的博客-程序员宝宝_安装mysql报错1130

这个问题是因为在数据库服务器中的mysql数据库中的user的表中没有权限(也可以说没有用户),下面将记录我遇到问题的过程及解决的方法。  在搭建完LNMP环境后用Navicate连接出错  遇到这个问题首先到mysql所在的服务器上用连接进行处理  1、连接服务器: mysql -u root -p  2、看当前所有数据库:show databases;  3、进入mysql数据库:use mysql;  4、查看mysql数据库中所有的表:show tables;  5、查看

推荐文章

热门文章

相关标签