数据结构初阶：栈的概念和如何模拟栈？

用户11290664

发布于 2024-09-25 13:33:13

670

发布于 2024-09-25 13:33:13

文章被收录于专栏：学习

每日一问。今天学习了吗?

一.栈 1.栈的概念及结构

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

为了更形象地了解栈的形象我们要了解2个概念压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

如图我们先录入数据1在栈底，然后再录入2，3和新的数据最新录入的数据就是栈顶的位置。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

此时我们要移除数据就只能从栈顶先移除。

这一步严格对应了前面的LIFO（Last In First Out）先进后出的原则。

2.模拟栈的实现那么我们如何来实现模拟栈的实现呢？

有两种结构和次类似，链表和数组，但是相比较来说数组的结构更加优良，因为。因为数组在尾上插入数据的代价比较小。

直接来写代码

sq.h

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

typedef int SLTypeDate;
typedef struct Stack
{
	SLTypeDate* a;
	int top;
	int capacity;

}SL;

首先我们先定义一个Stack结构体，里面存放了a指针，栈顶位置top方便操作，以及空间大小以便存放数据。然后把他改为SL方便操作。

下面是方法

void SLInite(SL* pst);//初始化
void SLDestroy(SL* pst);//销毁
void SLPush(SL* pst,SLTypeDate x);//插入数据
void SLPop(SL* pst);//删除栈顶数据
SLTypeDate SLTop(SL* pst);//返回栈顶数据
bool SLEmpty(SL* pst);//判断为空
int  SLSize(SL* pst);//获取数据大小

下面是方法的具体实现

sq,c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sq.h"
void SLInite(SL* pst) {//初始化
	assert(pst);
	pst->a = NULL;
	pst->capacity = pst->top = 0;




}
void SLDestroy(SL* pst) {//销毁

	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;



}
void SLPush(SL* pst, SLTypeDate x) {//插入数据

	if (pst->top==pst->capacity) {

		int newdate = pst->capacity==0?4:pst->capacity*2;
		SLTypeDate* tem = (SLTypeDate*)realloc(pst->a, sizeof(SLTypeDate) * newdate);
		if (tem == NULL) {


			perror("fail");
			return;
		}
		pst->a = tem;
		pst->capacity = newdate;


	}

	pst->a[pst->top] = x;
	pst->top++;

}
void SLPop(SL* pst) {//删除栈顶数据

	assert(pst);
	pst->top--;

}
SLTypeDate SLTop(SL* pst) {//返回栈顶数据
	
	assert(pst);

		return pst->a[pst->top-1];	

}
 bool SLEmpty(SL* pst) {//判断为空

	 assert(pst);
	 return pst->top == 0;

}
int  SLSize(SL* pst) {//获取数据大小
	assert(pst);
	return pst->top;

}

下面是测试

test,c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sq.h"





int main() {
	SL aa;
	SLInite(&aa);
	SLPush(&aa, 1);
	SLPush(&aa, 2);
	SLPush(&aa, 3);
	SLPush(&aa, 4);

	SLPush(&aa, 4);
	SLPush(&aa, 1);


	printf("这个栈帧的大小是%d ", SLSize(&aa));
	printf("栈顶元素是%d\n", SLTop(&aa));
	while (!SLEmpty(&aa))
	{
		printf("%d ",SLTop(&aa));
		aa.top--;
	}


	SLDestroy(&aa);



	return 0;
}