数据结构——栈与队列

时间：2024-10-12 07:01:30

目录

一、栈

1.栈的定义

 2.栈的分类与基本操作

1. 顺序栈

2.链栈

3.栈与递归的实现

1.递归的简单描述

2.递归过程及与栈的关联

3.递归过程示意图

二.队列

1.队列的定义

 2.队列的分类与基本操作

1.顺序队列

2.链队列

3.循环队列

1.假溢出

 2.循环队列

3.循环队列相关操作实现：

栈和队列是两种重要的线性结构。从数据结构的角度来看，栈与队列均属于线性表，其特殊性在于栈与队列的基本操作为线性表基本操作的子集，栈与队列为操作受限的线性表，故，栈与队列可称为限定性的数据结构，

一、栈

1.栈的定义

栈，是限定仅在表尾进行插入与删除操作的线性表。对于栈来说，表尾端具有特殊的含义，称为栈顶，相应地将表头段成为栈底。不含元素的空表称为空栈。

栈的修改是按照后进先出的原则进行的，因此将栈成为后进先出的线性表。

栈的示意图：

模拟实现出栈与入栈操作：（以顺序栈为例）

 2.栈的分类与基本操作

栈有两种存储表示方式：顺序存储方式与链式存储方式

1. 顺序栈

栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置（位置应与数据在顺序表中的下标区分理解）。

一种定义顺序栈的常用方法：先为栈分配一个初始容量，在实际应用过程中，当栈的存储空间不够时再逐段扩容。

以下为顺序栈的相关基本操作：

方法1：

#include<>
#include<>
#include<>
#include<>

#define Stack_Init_Size 10
#define Stack_Add_Size 5

//定义顺序栈的结构体
typedef int ElemType;
typedef struct Stack
{
	ElemType* base;	//定义栈底指针
	ElemType* top;	//定义栈顶指针
	int capacity;	//指明当前栈的容量
}Stack;


//栈的初始化操作
void StackInit(Stack* ps)
{
	ps->base = (ElemType*)malloc(sizeof(ElemType) * Stack_Init_Size);
	if (NULL == ps->base) //空间申请失败处理
	{
		printf("空间申请失败\n");
		exit(0);
	}
	ps->top = ps->base;
	ps->capacity = Stack_Init_Size;
}
//栈的判空操作
bool StackIsEmpty(Stack* ps)
{
	return ps->base == ps->top ? true : false;
}
//当前栈内元素数量
int StackNum(Stack* ps)
{
	return ps->top - ps->base;
}
//获取栈顶元素
void GetTop(Stack* ps, ElemType* e)
{
	assert(ps);
	if (ps->base == ps->top)
	{
		printf("当前栈中无元素\n");
		return;
	}
	*e = *(ps->top - 1);
}
//出栈
void StackPop(Stack* ps, ElemType* e)
{
	assert(ps);
	if (ps->base == ps->top)
	{
		printf("当前栈中无元素\n");
		exit(0);
	}
	*e = *(--ps->top);
}
//检查栈是否需要扩容
void StackCheckCapacity(Stack* ps)
{
	assert(ps);
	if (ps->top - ps->base >= ps->capacity)
	{
		ps->base = (ElemType*)realloc(ps->base, sizeof(ElemType) * (ps->capacity + Stack_Add_Size));
		if (NULL == ps->base)
		{
			printf("空间申请失败\n");
			exit(0);
		}
		ps->top = ps->base + ps->capacity;
		ps->capacity += Stack_Add_Size;
	}
}
//入栈
void StackPush(Stack* ps, ElemType e)
{
	assert(ps);
	StackCheckCapacity(ps);
	*(ps->top++) = e;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->base)
	{
		free(ps->base);
		ps->base = NULL;
		ps->capacity = 0;
	}
}

方法2：

#include<>
#include<>
#include<>

#define Stack_Init_Size 10
#define Stack_Add_Size 5

typedef int ElemType;
typedef struct Stack
{
	ElemType* data;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps)
{
	ps->data = (ElemType*)malloc(sizeof(ElemType) * Stack_Init_Size);
	if (NULL == ps->data)
	{
		printf("空间申请失败\n");
		exit(0);
	}
	ps->capacity = Stack_Init_Size;
	ps->top = 0;
}
//扩容判断
void CapacityCheck(Stack* ps)
{
	assert(ps);
	if (ps->top >= ps->capacity)
	{
		ps->data = (ElemType*)realloc(sizeof(ElemType) * (ps->capacity + Stack_Add_Size));
		if (NULL == ps->data)
		{
			printf("空间申请失败\n");
			exit(0);
		}
		ps->capacity += Stack_Add_Size;
	}
}
// 入栈 
void StackPush(Stack* ps, ElemType data)
{
	assert(ps);
	CapacityCheck(ps);
	ps->data[ps->top++] = data;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)
	{
		printf("当前栈中无元素\n");
		return;
	}
	ps->top--;
}
// 获取栈顶元素 
ElemType StackTop(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)
	{
		printf("当前栈中无元素\n");
		return;
	}
	return ps->data[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	return ps->top == 0 ? 1 : 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->data)
	{
		free(ps->data);
		ps->data = NULL;
		ps->capacity = 0;
		ps-

相关文章