【数据结构】C++语言实现栈(详细解读)

用户11036582

发布于 2024-05-07 08:24:25

700

发布于 2024-05-07 08:24:25

什么是栈

栈的概念及结构 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。 栈的结构:

实现栈的方式:

实现栈的方式有两种: 顺序表和链表

链表的优缺点:

优点: 1、任意位置插入删除O(1) 2、按需申请释放空间缺点: 1、不支持下标随机访问 2、CPU高速缓存命中率会更低

顺序表的优缺点:

优点:1、尾插尾删效率不错。 2、下标的随机访问。 3、CPU高速缓存命中率会更高 缺点: 1、前面部分插入删除数据，效率是O(N)，需要挪动数据。 2、空间不够，需要扩容。a、扩容是需要付出代价的 b、一般还会伴随空间浪费。

综上所述,用顺序表实现栈更好。

栈的实现

a.头文件的包含

#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>

b.栈的定义

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//栈的容量
}ST;

c.接口函数

// 初始化栈
void STInit(ST* pst); 
 
// 入栈
void STPush(ST* pst, STDataType data); 
 
// 出栈
void STPop(ST* pst); 
 
// 获取栈顶元素
STDataType STTop(ST* pst); 
 
// 获取栈中有效元素个数
int STSize(ST* pst); 
 
// 检测栈是否为空，如果为空返回true,如果不为空返回false
bool STEmpty(ST* pst); 
 
// 销毁栈
void STDestroy(ST* pst);

接口函数的实现

1.栈的初始化

pst->top表示栈的顶部指针，通常情况下，它指向栈顶元素的下一个位置,而不是指向当前栈顶元素。通过 pst->top 可以确定栈中元素的个数,打印的时候记得将 top - 1。

void STInit(ST* pst)
{
	assert(pst);//防止敲代码的人传过来是NULL指针
	
    pst->a = NULL;//栈底
	
    //top不是数组下标,不能理解成数组下标,因为栈只能拿到栈顶的元素，而数组可以随机访问拿到中间元素
    //pst->top=-1;//指向栈顶元素
	
    pst->top = 0;//指向栈顶元素的下一个位置
	pst->capacity = 0;
 
}

2.销毁栈

void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
}

3.入栈

这里我们会运用到三目运算符

void STPush(ST* pst,STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
 
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;//返回的是realloc出来的内存块的地址
		pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量
	}
	pst->a[pst->top] = x;//先放值
	pst->top++;//再++
}

4.检测栈是否为空

bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{
    //写法一
	//assert(pst);
	//if (pst->top == 0)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}
	
    //写法二
    return pst->top == 0;
}

当栈为空时，表示栈中没有任何元素。此时，栈顶指针 top 的值通常被设置为特定的初始值（例如0或-1），指向栈底或栈外。在这种情况下，栈顶指针没有指向有效的元素，因此栈被认为是空的。
当栈非空时，表示栈中至少有一个元素。此时，栈顶指针top的值指向栈顶元素的位置。栈顶元素是最后一个被入栈的元素，也是最先被访问或移除的元素。只要栈中有元素存在，栈顶指针都会指向有效的位置。

5.出栈

void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}

6.获取栈顶元素

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
 
	return pst->a[pst->top - 1];
}

7.获取栈中有效元素个数

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

完整代码：

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));//栈顶元素
		STPop(&st);
	}
	STDestroy(&st);
}
void TestStack2()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	printf("%d ", STTop(&st));
	STPush(&st, 3);
	STPush(&st, 4);
	printf("\n");
	printf("%d ", STTop(&st));
	//printf("%d", STSize(&st));
	//while (!STEmpty(&st))
	//{
	//	printf("%d ", STTop(&st));//栈顶元素
	//	STPop(&st);
	//}
	STDestroy(&st);
}
void TestStack3()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	//printf("%d", STSize(&st));
 
	STDestroy(&st);
}
 
int main()
{
	TestStack1();//入栈出栈
	//TestStack2();//获取栈顶元素
	//TestStack3();//计算栈中有效元素个数 
	return 0;
}

Stack.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的位置
	int capacity;//栈的容量
}ST;
 
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool  STEmpty(ST* pst);
int STSize(ST*pst);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;//栈底
	
	//top不是下标
    //pst->top=-1;//指向栈顶元素
	pst->top = 0;//指向栈顶元素的下一个位置
	pst->capacity = 0;
 
}
 
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
}
 
 
void STPush(ST* pst,STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//true,4.false,括2倍
 
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));//返回值地址相等就是原地扩容，不同就是异地扩
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;//返回的是realloc出来的内存块的地址
		pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量
	}
	pst->a[pst->top] = x;//先放值
	pst->top++;//再++
}
 
 
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
 
 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
 
	return pst->a[pst->top - 1];
}
 
bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{
	//assert(pst);
	//if (pst->top == 0)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}
	return pst->top == 0;
}
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-05-06，如有侵权请联系 cloudcommunity@tencent.com 删除

指针