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

【数据结构】栈各个接口的实现

article 2024/11/13 10:19:20

前言：

一、栈的概述：

1.栈的概念：

二、栈接口的实现：

1.栈的初始化：

2.压栈：

3.出栈：

4.取栈顶元素：

5.计算栈内有效数据：

6.判断栈是否为空：

7.栈的销毁：

三、完整代码：

1.Stack.h:

2.Stack.c:

总结：

前言：

前面我们已经学习了顺序表和链表的相关知识和对各个接口实现，而今天我们将对栈进行学习。

一、栈的概述：

1.栈的概念：

栈也叫栈堆，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一段被称为栈顶，相对的把另一端称之为栈底。像栈插入元素称之为进栈、入栈或压栈，它是把新元素放到栈顶的位置。从栈删除元素又称之为出栈或者退栈，它是把栈顶的元素删除掉，使相邻的元素成为新的栈顶元素。（后进后出）

我们可结合图片来理解：

进栈、入栈或压栈：

出栈或者退栈：

二、栈接口的实现：

栈可用数组或链表实现，下面我统一用数组实现栈。

1.栈的初始化：

①.初始化前需要进行非空判断，防止对空指针进行操作。

②.确认非空之后将所有元素置为初始值。

③.Top值可以为0也可以为-1.区别在于：为0表示的事Top指向栈顶数据的下一个数据；-1则表示栈顶的数据。
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;
}

2.压栈：

①.执行操作前需要进行非空判断，防止对空指针进行操作。

②.还要对栈空间进行判断，若栈中的top=capacit,则说明此时已经存满，需要进行扩容。
void STPush(ST* ps, STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDatatype* new= (STDatatype*)realloc(ps->a,sizeof(STDatatype) * (ps->capacity*2));
		if (ps->a == NULL)
		{
			perror("malloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = new;
	}
	
		ps->a[ps->top] = x;
		ps->top++;
}

3.出栈：

①.执行操作前需要进行非空判断，防止对空指针进行操作。

②.删除栈顶数据，也就是出栈，这一步操作其实很简单，只需要将指向栈顶的下标减减即可，也就top--;但是在进行操作是要注意栈内是否还有元素，若没有数据则停止删除。
void STPop(ST* ps)
{
	assert(ps);

	if(ps->top>0)
	ps->top--;
}

4.取栈顶元素：

①.执行操作前需要进行非空判断，防止对空指针进行操作。

②.同时需要判断栈内是否存在数据。

③.若判断不为空，及栈内存在数据（可以获取栈顶数据），则返回栈顶内容，
STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	
	return ps->a[ps->top-1];
}

5.计算栈内有效数据：

①.执行操作前需要进行非空判断，防止对空指针进行操作。

②.判断数据有效后，直接返回top就可以了。
int STsize(ST* ps)
{
	assert(ps);
	return ps->top;
}

6.判断栈是否为空：

①.执行操作前需要进行非空判断，防止对空指针进行操作。

②.直接对top进行判断即可，若top为初始值0，则说明栈内没有数据，返回真，不为0，则说明栈内有数据，返回假。
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;

}

7.栈的销毁：

①.执行操作前需要进行非空判断，防止对空指针进行操作。

②.直接释放ps->a并置空后，将top和capaci置为初始值0就可以了。
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

三、完整代码：

1.Stack.h:

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

typedef int STDatatype;

typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDatatype x);
void STPop(ST* ps);
int STsize(ST* ps);
bool STEmpty(ST* ps);
STDatatype STTop(ST* ps);

2.Stack.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;
}
void STPush(ST* ps, STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDatatype* new= (STDatatype*)realloc(ps->a,sizeof(STDatatype) * (ps->capacity*2));
		if (ps->a == NULL)
		{
			perror("malloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = new;
	}
	
		ps->a[ps->top] = x;
		ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);

	if(ps->top>0)
	ps->top--;
}
int STsize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;

}
STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	
	return ps->a[ps->top-1];
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}