欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之栈和队列的实现

程序员文章站 2024-01-24 17:12:40
...

1,栈

栈(stack)又叫堆栈,是一种容器,可存入数据元素、访问元素、删除元素,它的特点在于只能允许在容器的一端(称为栈顶top)进行加入数据(push)和输出数据(pop)的运算。保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作,因而按照先进后出或者后进先出(LIFO, Last In First Out)的操作顺序。

                  数据结构之栈和队列的实现

 

首先实现栈,在定义栈时可以定义静态栈,也可以定义动态栈,根据自己的需求自己定义。其中静态栈包括数组data和栈顶top,动态栈包括数组data,还有栈顶top,和栈的容量capacity。同时为了方便定义和修改数据类型,我们可以用typedef给类型重命名。然后就是栈的各个接口的实现,包括站的初始化,站的销毁,栈的插入,栈的删除,获取栈顶元素,判断栈是否为空,以及求栈的大小。

 


#pragma once
#define MAX 100
#define DEFAULT_SZ 3

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


//
//静态栈
//typedef int DataType;
//#define MAX 10
//typedef struct Stack
//{
//	DataType *data[MAX];
//	int top;//栈顶
//};

//动态栈
typedef int DataType;
typedef struct Stack
{
	DataType*data;//栈的数组
	int top;//栈顶
	int capacity;//容量

}Stack;

void InitStack(Stack *ps);//初始化栈
void DistoryStack(Stack *ps);//销毁栈
void StackPush(Stack*ps,DataType d);//入栈
void StackPop(Stack *ps);//出栈
DataType StackTop(Stack *ps);//查找栈顶的元素
int StackEmpty(Stack*ps);//栈是否为空
int StackSize(Stack *ps);//栈的大小
void PrintStack(Stack *ps);//打印栈

这一部分是栈的具体的各个函数的实现。同时栈的性质是先进后出(FILO),也就是最先进的数据,最后出。而且,栈只有栈顶在移动,增加一个数据时,栈顶加一。出一个数据时,栈顶减一

 


#include"Stack.h"
void InitStack(Stack *ps)//初始化栈
{
	assert(ps != NULL);
	ps->top = 0;//栈顶
	ps->data = (DataType*)malloc(sizeof(DataType)*DEFAULT_SZ);//开辟默认大小的空间
	ps->capacity = DEFAULT_SZ;
}
void DistoryStack(Stack *ps)//销毁栈,栈不能为空
{
	assert(ps != NULL);
	if (ps->data != NULL)
	{
		free(ps->data);
		ps->data = NULL;
		ps->top = ps->capacity = 0;
	}
	printf("栈销毁成功\n");
}
void StackPush(Stack*ps, DataType d)//入栈
{
	assert(ps != NULL);
	if (ps->top == ps->capacity)
	{
		ps->data = (DataType*)realloc(ps->data, sizeof(DataType)*(ps->capacity * 2));
		//判断增容成功的第一种写法
		assert(ps->data);
		//第二中写法
		/*if (ps == ps->capacity)
		{
		perror("use realloc");//返回错误码
		exit(EXIT_FAILURE);
		}*/
		ps->capacity *= 2;
	}
	ps->data[ps->top] = d;
	ps->top++;
}
void StackPop(Stack *ps)//出栈
{

	assert(ps);//保证栈里面有数据
	if (ps->top == 0)
	{
		return;
	}
	ps->top--;
}
DataType StackTop(Stack *ps)//
{
	assert(ps);
	assert(&ps->top > 0);
	return ps->data[ps->top-1];//返回栈顶元素
}
int StackEmpty(Stack*ps)//栈是否为空
{
	assert(ps != NULL);
	return ps->top == 0 ? 0 : 1;//比较运算,空为0,非空为1。若果栈顶ps->top==0说明栈为空
}
int StackSize(Stack *ps)//栈的大小
{
	assert(ps != NULL);
	//第一种方法,比较麻烦,不建议用
	/*int count = 0;
	Stack *cur = ps;
	while (cur->top)
	{
		count++;
		cur--;
		
	}
	return count;*/
	//第二种,直接返回栈顶的大小,建议用这种方法简单
	return ps->top;
}
void PrintStack(Stack *ps)//打印栈
{
	assert(ps!=NULL);
	Stack *cur = ps;
	while (cur->top)
	{
		printf("%d ", cur->top);
		cur->top--;
	}
	printf("\n");
}

 

2.队列

队列与栈相反,是一种先进先出(FIFO, 意思为frist in frist out ),它只允许在队头删除,在队尾插入。举例子就像在超市买东西排队一样。如下图所示,队列中的元素是按照 a1,a2,a3,a4....an的顺序进队列的,而出队列的顺序应该也和进队列的顺序一样。只有当an前面的所有数据都出队列了,an才能出队列。

数据结构之栈和队列的实现

队列的实现中,队列的节点包含两部分数据部分和保存下一个数据地址的指针,同时队列的结构里包含队头指针和队尾指针。队列主要的接口实现主要为丢列的初始化,队列的销毁,获取队头数据,获取队尾的数据,队列的插入,队列的删除,判断队列是否为空,以及求队列的大小。

 

#pragma once 

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

typedef int QUDataType;
typedef struct QueueNode //Node包含两部分,存储的数据,存储的下一个数据的地址指针next
{
	QUDataType data;//元素
	struct QueueNode *next;//保存下一个数据的地址指针

}QueueNode;
typedef struct Queue
{
	QueueNode *front;//对头
	QueueNode *rear;//队尾
	
}Queue;


void QueueInit(Queue* pq);//队列的初始化
void QueueDestory(Queue* pq);//队列的销毁
QueueNode* BuyQueueNode(QUDataType x);//创建一个队列的节点
void QueuePush(Queue* pq, QUDataType x);//队列的插入
void QueuePop(Queue* pq);//队列的删除
QUDataType QueueFront(Queue* pq);//获取队头数据
QUDataType QueueBack(Queue *pq);//获取队尾的数据
int QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//求队列的大小


 

这一部分是队列各个接口的实现。在这里我们要记住队列是先进先出的,所以在插入和删除数据分别在队头和队尾进行,同时获取队头和队尾数据也在这两部分。

 

#pragma once
#include"Queue.h"
void QueueInit(Queue* pq)//初始化队列,最开始队头和队尾实在一起的都为空
{
	assert(pq != NULL);
	pq->rear = NULL;
	pq->front = NULL;
}
void QueueDestory(Queue* pq)//销毁队列
{
	assert(pq!=NULL);
	QueueNode *cur = pq->front;//,先定义一个cur保存队头的位置
	while (cur!=NULL)
	{
		QueueNode* next = cur->next;//在定义一个next保存cur的下一个值
		free(cur);//释放cur
		cur =cur->next;
	}
	pq->front = pq->rear = NULL;//让队头和队尾都为空,防止野指针的生成
}

QueueNode* BuyQueueNode(QUDataType x)//创造一个新的结点
{
	QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
	//断言新结点是否创建成功
	assert(NewNode);
	//方法二
	//if (NewNode == NULL)//结点创建失败
	//{
	//	perror("use malloc for NewNode");
	//	exit(EXIT_FAILURE);
	//}
	NewNode->data = x;//赋值
	NewNode->next = NULL;
	return NewNode;

}
//队尾进
void QueuePush(Queue* pq, QUDataType x)
{
	assert(pq != NULL);
	if (pq->front == NULL)//队列为空
	{

		pq->front = pq->rear = BuyQueueNode(x);
	}
	else//队列不为空
	{
		QueueNode *node = BuyQueueNode(x);//创建新结点
		pq->rear->next = node;//队尾进
		pq->rear = node;//队尾等于新的node
	}

}
//删除队头结点
void QueuePop(Queue* pq)
{
	QueueNode* next = NULL;
	assert(pq != NULL);
	next = pq->front->next;//先创建一个next保存下一个值
	free(pq->front);//释放队头
	pq->front = next;
	if (next == NULL)//如果next指向的下一个节点为空,不队尾指针置空
	{
		pq->rear = NULL;
	}
}
//返回队头数据
QUDataType QueueFront(Queue* pq)
{
	assert(pq != NULL);
	return pq->front->data;
}
QUDataType QueueBack(Queue *pq)
{
	return pq->rear->data;
}
//判断队列是否为空
int QueueEmpty(Queue* pq)
{
	assert(pq != NULL);
	return pq->front == NULL ? 0 : 1;//空为0,非空1
}

//返回队列的大小
int QueueSize(Queue* pq)//利用计数的方法。
{
	assert(pq != NULL);
	QueueNode* cur = pq->front;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

 

还没写完,所以过几天还会补充相应的知识漏洞。