数据结构之栈和队列的实现
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;
}
还没写完,所以过几天还会补充相应的知识漏洞。
上一篇: bmp转rgb565在framebuffer中显示
下一篇: 数据结构:栈的应用实现