数据结构第四章栈

这篇具有很好参考价值的文章主要介绍了数据结构第四章栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构第四章栈,数据结构,数据结构

🚀 写在最前：这篇文章将学习栈这种结构，以及该结构的一些基本操作的实现，包括顺序存储栈和链式存储栈的基本操作的实现。
🚀：点求个关注，让我们一起探索计算机的奥秘！

一、栈的定义

所谓的栈就是一种特殊的线性表，对于栈这种逻辑结构来说他和线性表最大的区别就是栈它删除元素或者添加元素的话只能发生在表的一端，要么就是表尾部，要么就是表头。
数据结构第四章栈,数据结构,数据结构

如上图所显示的那样，这就是栈的结构，当然这是将栈这种逻辑结构使用顺序存储的方式表示出来了。

栈顶：这个特殊的线性表允许插入元素和删除元素的一端
栈底：是固定的，不允许进行插入和删除的一端

所以不难发现，由于栈的插入元素和删除元素操作都只能发生在线性表的一端，对于这种结构来说，其元素的进出是遵循后进先出的
数据结构第四章栈,数据结构,数据结构
对于先进入的元素（元素进入称为进栈），在取出的时候（元素被取出称为出栈），也会是最先被取出的。

二、栈的基本操作

在定义完一个数据的逻辑结构就应该给出相应的基本操作，来操作这个逻辑结构，对于栈这种逻辑结构，是给出了以下几种常用操作。

初始化操作
判断栈是否为空
元素进栈
元素出栈
读栈顶元素，但是不出栈
销毁栈

三、栈不同的存储结构的基本操作实现

在学习线性表时，也是学习了线性表这个逻辑结构在顺序存储下的基本操作的实现以及在链式存储下的基本操作的实现，所以存储结构不同，用代码具体实现这些操作的步骤和思想也是不同的。

①栈的顺序存储

定义好栈的逻辑结构，对于栈这个逻辑结构使用顺序存储，这里使用静态数组来实现顺序存储，定义如下结构。

#define maxsize 100
typedef int Element;

typedef struct {
	Element data[maxsize];    //存放栈元素
	int top;                  //栈顶指针（这里使用静态数组，即使用下标指向栈顶）
}SqStack;

文件结构：

包含三个文件，一个SqStack.h文件用于定义数据结构和数据结构的基本操作，一个SqStack.cpp文件，该文件用于具体实现这些基本操作，一个test.cpp用于测试实现的函数是否正确。
数据结构第四章栈,数据结构,数据结构

初始化操作

SqStack.h的内容

#pragma once
#include<stdio.h>
#include<stdlib.h>

#define maxsize 100
typedef int Element;

typedef struct {
	Element data[maxsize];    //存放栈元素
	int top;                  //栈顶指针（这里使用静态数组，即使用下标指向栈顶）
}SqStack;


// 初始化操作
bool InitStack(SqStack &SqS);

SqStack.cpp的内容

#include"SqStack.h"

// 初始化操作
bool InitStack(SqStack &SqS) {
	SqS.top = -1;         //将栈顶指向-1，为空
	return true;
}

test.cpp的内容

#include"SqStack.h"

int main() {
	SqStack SqS1;

	//初始化栈
	InitStack(SqS1);
	printf("%d\n", SqS1.top);

	return 0;
}

数据结构第四章栈,数据结构,数据结构

栈的判空操作

SqStack.h的内容

//栈的判空操作
bool IsStackEmpty(SqStack SqS);

SqStack.cpp的内容

// 判断栈是否为空
bool IsStackEmpty(SqStack SqS)
{
	if (SqS.top == -1) {
		return true;
	}
	else {
		return false;
	}
}

test.cpp的内容

#include"SqStack.h"

int main() {
	SqStack SqS1;

	//初始化栈
	InitStack(SqS1);
	printf("%d\n", SqS1.top);

	//栈判空
	bool t = IsStackEmpty(SqS1);
	if (t == true) {
		printf("栈为空！\n");
	}

	return 0;
}

数据结构第四章栈,数据结构,数据结构

进栈

SqStack.h的内容

// 元素进栈
bool Push(Element e, SqStack &SqS);

//打印栈
void PrintStack(SqStack SqS);

SqStack.cpp的内容（这里将打印栈的操作也写在其中，没有单独写这个打印操作）

// 元素进栈
bool Push(Element e, SqStack& SqS) {
	if (SqS.top == maxsize-1) {
		printf("栈满，进栈失败\n");
		return false;
	}
	else {
		SqS.top++;
		SqS.data[SqS.top] = e;
		return true;
	}
}


//打印栈
void PrintStack(SqStack SqS) {
	if (SqS.top == -1) {
		printf("栈为空！");
	}
	else {
		printf("打印顺序：栈顶<----栈底\n");
		for (int j = SqS.top; j >= 0; j--) {
			printf("<--%d", SqS.data[j]);
		}
	}
}

test.cpp的内容

#include"SqStack.h"

int main() {
	SqStack SqS1;

	//初始化栈
	InitStack(SqS1);
	printf("%d\n", SqS1.top);

	//栈判空
	bool t = IsStackEmpty(SqS1);
	if (t == true) {
		printf("栈为空！\n");
	}

	//进栈
	Push(2, SqS1);
	Push(3, SqS1);
	PrintStack(SqS1);


	return 0;
}

数据结构第四章栈,数据结构,数据结构

出栈

SqStack.h的内容

// 元素出栈
Element Pop(SqStack &SqS);

SqStack.cpp的内容

// 元素出栈
Element Pop(SqStack &SqS) {
	if (SqS.top == -1) {
		printf("栈空导致出栈失败\n");
		exit;
	}
	else {
		Element ele = SqS.data[SqS.top];
		SqS.top--;
		return ele;
	}
}

test.cpp的内容

#include"SqStack.h"

int main() {
	SqStack SqS1;

	//初始化栈
	InitStack(SqS1);
	printf("%d\n", SqS1.top);

	//栈判空
	bool t = IsStackEmpty(SqS1);
	if (t == true) {
		printf("栈为空！\n");
	}

	//进栈
	Push(2, SqS1);
	Push(3, SqS1);
	PrintStack(SqS1);
	Element tmp = Pop(SqS1);
	printf("出栈元素为%d\n", tmp);

	return 0;
}

数据结构第四章栈,数据结构,数据结构

读栈顶元素

该操作与pop操作的区别是，这个只是读出栈顶的元素，该元素并不出栈。
SqStack.h的内容

// 读栈顶元素，但是不出栈
Element GetTop(SqStack SqS);

SqStack.cpp的内容

// 读栈顶元素，但是不出栈
Element GetTop(SqStack SqS) {
	if (SqS.top == -1) {
		printf("栈顶无元素\n");
		return -1;
	}
	else {
		Element tmp = SqS.data[SqS.top];
		return tmp;
	}
}

test.cpp的内容

#include"SqStack.h"

int main() {
	SqStack SqS1;

	//初始化栈
	InitStack(SqS1);
	printf("%d\n", SqS1.top);

	//栈判空
	bool t = IsStackEmpty(SqS1);
	if (t == true) {
		printf("栈为空！\n");
	}

	//进栈
	Push(2, SqS1);
	Push(3, SqS1);
	PrintStack(SqS1);
	Element tmp = Pop(SqS1);
	printf("出栈元素为%d\n", tmp);
	printf("栈顶元素为%d\n", GetTop(SqS1));

	return 0;
}

数据结构第四章栈,数据结构,数据结构

销毁栈

这里的销毁栈，其实只需要将top的值至为-1就行，因为这个栈空间并不是由malloc函数开辟的，所以不需要free()函数来回收空间，在程序结束之后，会自动的回收空间。

②栈的链式存储

栈的初始化

SqStack.h的内容

#include<stdlib.h>

typedef int	ElementType;

typedef struct LinkStackNode {
	ElementType data;    //节点数据
	struct LinkStackNode *next;
}LinkStackNode,*LinkStack;

//栈的初始化
int InitStack(LinkStack &LinkS);

SqStack.cpp的内容

#include"LinkStack.h"

//栈的初始化
int InitStack(LinkStack &LinkS) {
	LinkS = (LinkStackNode*)malloc(sizeof(LinkStackNode)); //LinkS--->头节点 申请了一个头节点
	// printf("%p", LinkS);
	if (LinkS == NULL) {
		printf("空间申请失败导致初始化失败\n");
		return -1;
	}
	else {
		LinkS->next = NULL;  //头节点的next指向空
		return 1;
	}
}

test.cpp的内容

#include"LinkStack.h"

int main() {
	LinkStack l1;
	if (InitStack(l1)) {
		printf("初始化成功\n");
	}
	return 0;
}

数据结构第四章栈,数据结构,数据结构

栈的判空操作

SqStack.h的内容

//栈的判空操作
bool IsStackEmpty(LinkStack Links);

SqStack.cpp的内容

//栈的判空操作
bool IsStackEmpty(LinkStack Links) {
	if (Links->next == NULL) {//头节点的next为空，就其头节点后无元素
		return true;
	}
	else {
		return false;
	}
}

test.cpp的内容

#include"LinkStack.h"

int main() {
	LinkStack l1;
	if (InitStack(l1)) {
		printf("初始化成功\n");
	}
	if (IsStackEmpty(l1)) {
		printf("栈为空\n");
	}

	return 0;
}

数据结构第四章栈,数据结构,数据结构

进栈

在这一部分将打印栈的操作也写在这一部分了
SqStack.h的内容

//进栈
bool Push(LinkStack Links, ElementType e);
//打印栈
void PrintStack(LinkStack Links);

SqStack.cpp的内容

//进栈
bool Push(LinkStack Links, ElementType e) {
	LinkStackNode* node = (LinkStackNode*)malloc(sizeof(LinkStackNode));
	if (node == NULL) {
		printf("空间申请失败导致进栈失败\n");
		return false;
	}
	else {
		node->next = Links->next;
		Links->next = node;
		node->data = e;
		return true;
	}
}
//打印栈
void PrintStack(LinkStack Links) {
	if (Links == NULL) {
		printf("无效的栈，无法打印\n");
		return;
	}
	if (Links->next == NULL) {
		printf("栈为空！");
		return;
	}
	else {
		printf("打印顺序：栈顶<----栈底\n");
		LinkStackNode* tmp = NULL;
		for (tmp = Links->next; tmp != NULL; tmp = tmp->next) {
			printf("<--%d", tmp->data);
			
		}
		printf("\n");
	}
}

test.cpp的内容

#include"LinkStack.h"

int main() {
	LinkStack l1;
	if (InitStack(l1)) {
		printf("初始化成功\n");
	}
	if (IsStackEmpty(l1)) {
		printf("栈为空\n");
	}

	Push(l1, 3);
	Push(l1, 4);
	PrintStack(l1);

	return 0;
}

数据结构第四章栈,数据结构,数据结构

出栈

SqStack.h的内容

//出栈
ElementType Pop(LinkStack Links);

SqStack.cpp的内容


//出栈
ElementType Pop(LinkStack Links) {
	if (Links->next == NULL) {
		printf("栈为空\n");
		return -1;
	}
	else {
		ElementType datatmp = Links->next->data;
		LinkStackNode* tmp = Links->next;
		Links->next = Links->next->next;
		free(tmp);
		return datatmp;
	}
}

test.cpp的内容

#include"LinkStack.h"

int main() {
	LinkStack l1;
	if (InitStack(l1)) {
		printf("初始化成功\n");
	}
	if (IsStackEmpty(l1)) {
		printf("栈为空\n");
	}

	Push(l1, 3);
	Push(l1, 4);
	PrintStack(l1);
	Push(l1, 7);
	printf("此时pop的元素为%d\n", Pop(l1));
	return 0;
}

数据结构第四章栈,数据结构,数据结构

读栈顶元素

SqStack.h的内容

//读栈顶元素
ElementType GetEle(LinkStack Links);

SqStack.cpp的内容

//读栈顶元素
ElementType GetEle(LinkStack Links) {
	if (Links->next == NULL) {
		printf("此时栈顶为空\n");
		return -1;
	}
	else {
		ElementType tmp = Links->next->data;
		return tmp;
	}
}

test.cpp的内容

#include"LinkStack.h"

int main() {
	LinkStack l1;
	if (InitStack(l1)) {
		printf("初始化成功\n");
	}
	if (IsStackEmpty(l1)) {
		printf("栈为空\n");
	}

	Push(l1, 3);
	Push(l1, 4);
	PrintStack(l1);
	Push(l1, 7);
	printf("此时pop的元素为%d\n", Pop(l1));
	printf("此时栈顶的元素为%d\n", GetEle(l1));
	return 0;
}

数据结构第四章栈,数据结构,数据结构

销毁栈

SqStack.h的内容

//销毁栈
void DestoryStack(LinkStack &links);

SqStack.cpp的内容

//销毁栈
void DestoryStack(LinkStack &links) {
	LinkStackNode* tmp = links->next;
	while (tmp != NULL){
		LinkStackNode* t = tmp;
		tmp = tmp->next;
		free(t);
	}
	free(links); //free掉头节点
	links = NULL;
}

test.cpp的内容

#include"LinkStack.h"

int main() {
	LinkStack l1 = NULL;
	if (InitStack(l1)) {
		printf("初始化成功\n");
	}
	if (IsStackEmpty(l1)) {
		printf("栈为空\n");
	}

	Push(l1, 3);
	Push(l1, 4);
	PrintStack(l1);
	Push(l1, 7);
	printf("此时pop的元素为%d\n", Pop(l1));
	printf("此时栈顶的元素为%d\n", GetEle(l1));
	DestoryStack(l1);
	PrintStack(l1);
	return 0;
}