队列

队列的定义

 队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。
在这里插入图片描述
队头(Front):允许删除的一端,又称队首。
队尾(Rear):允许插入的一端。
空队列:不包含任何元素的空表。

队列常见的基本操作

nitQueue(&Q):初始化队列,构造一个空队列Q。
QueueEmpty(Q):判队列空,若队列Q为空返回true,否则返回false。
EnQueue(&Q, x):入队,若队列Q未满,将x加入,使之成为新的队尾。
DeQueue(&Q, &x):出队,若队列Q非空,删除队头元素,并用x返回。
GetHead(Q, &x):读队头元素,若队列Q非空,则将队头元素赋值给x。

队列的顺序存储结构

初始状态(队空条件):Q->front == Q->rear == 0。
进队操作:队不满时,先送值到队尾元素,再将队尾指针加1。
出队操作:队不空时,先取队头元素值,再将队头指针加1。
在这里插入图片描述

实现

SeqQueue.h

#pragma once
#ifndef SEQQUEUE_H
#define SEQQUEUE_H

#define MAX_SIZE 1024

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

typedef struct SEQQUEUE_H {
	void* data[MAX_SIZE];
	int size;
}SeqQueue;

//初始化 //入列//返回队头元素//出队//返回队尾元素//返回大小//清空队列//销毁
SeqQueue* Init_SeqQueue();
//入列
void Push_SeqQueue(SeqQueue* queue, void* data);
//返回队头元素
void* Front_SeqQueue(SeqQueue* queue);
//出队
void Pop_SeqQueue(SeqQueue* queue);
//返回队尾元素
void* Back_SeqQueue(SeqQueue* queue);
//返回大小
int Size_SeqQueue(SeqQueue* queue);
//清空队列
void Clear_SeqQueue(SeqQueue* queue);
//销毁
void FreeSpace_SeqQueue(SeqQueue* queue);

#endif // !SEQQUEUE_H

SeqQueue.c

#include "SeqQueue.h"

//初始化 //入列//返回队头元素//出队//返回队尾元素//返回大小//清空队列//销毁
SeqQueue* Init_SeqQueue()
{
	SeqQueue* queue = (SeqQueue*)malloc(sizeof(SeqQueue));
	for (int i = 0; i < MAX_SIZE; i++)
	{
		queue->data[i] = NULL;
	}
	queue->size = 0;

	return queue;
}

//入列
void Push_SeqQueue(SeqQueue* queue, void* data)
{
	if (!queue || !data)
	{
		return;
	}

	if (queue->size == MAX_SIZE)
	{
		return;
	}

	queue->data[queue->size] = data;
	queue->size++;
}

//返回队头元素
void* Front_SeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return NULL;
	}

	if (queue->size == 0)
	{
		return NULL;
	}

	return queue->data[0];
}

//出队
void Pop_SeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return;
	}

	if (queue->size == 0)
	{
		return;
	}

	for (int i = 0; i < queue->size - 1; i++)
	{
		queue->data[i] = queue->data[i + 1];
	}

	queue->size--;
}

//返回队尾元素
void* Back_SeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return NULL;
	}

	if (queue->size == 0)
	{
		return NULL;
	}

	return queue->data[queue->size - 1];
}

//返回大小
int Size_SeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return -1;
	}

	return queue->size;
}

//清空队列
void Clear_SeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return;
	}

	queue->size = 0;
}

//销毁
void FreeSpace_SeqQueue(SeqQueue* queue)
{
	if (!queue)
	{
		return;
	}

	free(queue);
}

main.c

#include "SeqQueue.h"

typedef struct PERXON {
	char name[64];
	int age;
}Person;

int main()
{
	//创建队列
	SeqQueue* queue = Init_SeqQueue();
	//创建数据
	Person p1 = { "aaa", 10 };
	Person p2 = { "bbb", 20 };
	Person p3 = { "ccc", 30 };
	Person p4 = { "ddd", 40 };
	Person p5 = { "eee", 50 };

	//数据入队列
	Push_SeqQueue(queue, &p1);
	Push_SeqQueue(queue, &p2);
	Push_SeqQueue(queue, &p3);
	Push_SeqQueue(queue, &p4);
	Push_SeqQueue(queue, &p5);

	//输出队尾元素
	Person* backPerson = (Person*)Back_SeqQueue(queue);
	printf("队尾元素:Name:%s, Age:%d\n", backPerson->name, backPerson->age);

	while (Size_SeqQueue(queue))
	{
		//取出队头元素
		Person* p = (Person*)Front_SeqQueue(queue);
		printf("Name:%s, Age:%d\n", p->name, p->age);
		//从队头弹出
		Pop_SeqQueue(queue);
	}

	FreeSpace_SeqQueue(queue);
	return 0; 
}

在这里插入图片描述

栈的定义

 栈(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。
在这里插入图片描述
栈顶(Top):线性表允许进行插入删除的那一端。
栈底(Bottom):固定的,不允许进行插入和删除的另一端。
空栈:不含任何元素的空表。
栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。

栈的常见基本操作

InitStack(&S):初始化一个空栈S。
StackEmpty(S):判断一个栈是否为空,若栈为空则返回true,否则返回false。
Push(&S, x):进栈(栈的插入操作),若栈S未满,则将x加入使之成为新栈顶。
Pop(&S, &x):出栈(栈的删除操作),若栈S非空,则弹出栈顶元素,并用x返回。
GetTop(S, &x):读栈顶元素,若栈S非空,则用x返回栈顶元素。
DestroyStack(&S):栈销毁,并释放S占用的存储空间(“&”表示引用调用)。

栈的顺序存储

 采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置。
若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判断条件定位top等于-1。

实现

SeqStack.h

#pragma once
#ifndef SEQSTACK_H
#define SEQSTACK_H

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

//数组去模拟栈的顺序存储
#define MAX_SIZE 1024
#define SEQSTACK_TRUE 1
#define SEQSTACK_FALSE 0

typedef struct SEQSTACK {
	void* data[MAX_SIZE];
	int size;
}SeqStack;

//初始化栈 
SeqStack* Init_SeqStack();
//入栈
void Push_SeqStack(SeqStack* stack, void* data);
//返回栈顶元素
void* Top_SeqStack(SeqStack* stack);
//出栈
void Pop_SeqStack(SeqStack* stack);
//判断是否为空
int IsEmpty(SeqStack* stack);
//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack);
//清空栈
void Clear_SeqStack(SeqStack* stack);
//销毁
void FreeSpace_SeqStack(SeqStack* stack);
#endif // !SEQSTACK_H

SeqStack.c

#include "SeqStack.h"

//初始化栈 
SeqStack* Init_SeqStack()
{
	SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));

	for (int i = 0; i < MAX_SIZE; i++)
	{
		stack->data[i] = NULL;
	}
	stack->size = 0;

	return stack;
}

//入栈
void Push_SeqStack(SeqStack* stack, void* data)
{
	if (!stack || !data)
	{
		return;
	}

	if (stack->size == MAX_SIZE)
	{
		return;
	}

	stack->data[stack->size] = data;
	stack->size++;
}
//返回栈顶元素
void* Top_SeqStack(SeqStack* stack)
{
	if (stack == NULL)
	{
		return NULL;
	}

	if (stack->size == 0)
	{
		return NULL;
	}

	return stack->data[stack->size - 1];
}
//出栈
void Pop_SeqStack(SeqStack* stack)
{
	if (stack == NULL)
	{
		return;
	}

	if (stack->size == 0)
	{
		return;
	}

	stack->data[stack->size - 1] = NULL;
	stack->size--;
}

//判断是否为空
int IsEmpty(SeqStack* stack)
{
	if (stack == NULL)
	{
		return -1;
	}

	if(stack->size == 0)
	{
		return SEQSTACK_TRUE;
	}

	return SEQSTACK_FALSE;
}

//返回栈中元素的个数
int Size_SeqStack(SeqStack* stack)
{
	return stack->size;
}

//清空栈
void Clear_SeqStack(SeqStack* stack)
{
	if(stack == NULL)
	{
		return;
	}

	for (int i = 0; i < stack->size; i++)
	{
		stack->data[i] = NULL;
	}

	stack->size = 0;
}

//销毁
void FreeSpace_SeqStack(SeqStack* stack)
{
	if (stack == NULL)
	{
		return;
	}

	free(stack);
}

main.c

#include "SeqStack.h"

typedef struct PERSON 
{
	char name[64];
	int age;
}Person;



int main()
{
	//创建栈
	SeqStack* stack = Init_SeqStack();

	//创建数据
	Person p1 = { "aaa", 10 };
	Person p2 = { "bbb", 20 };
	Person p3 = { "ccc", 30 };
	Person p4 = { "ddd", 40 };
	Person p5 = { "eee", 50 };

	//入栈
	Push_SeqStack(stack, &p1);
	Push_SeqStack(stack, &p2);
	Push_SeqStack(stack, &p3);
	Push_SeqStack(stack, &p4);
	Push_SeqStack(stack, &p5);

	//输出
	while (!IsEmpty(stack))
	{
		Person * person = (Person *) Top_SeqStack(stack);
		printf("%s->%d\n", person->name, person->age);

		Pop_SeqStack(stack);
	}

	FreeSpace_SeqStack(stack);
	return 0;
}

在这里插入图片描述

栈的链式存储

 采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点,Lhead指向栈顶元素,如下图所示。
在这里插入图片描述

实现

LinkStack.h

#pragma once
#ifndef LINKSTACK_H
#define LINKSTACK_H

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

//链式栈的结点
typedef struct LINKNODE {
	struct LINKNODE* next;
}LinkNode;
//链式栈
typedef struct LINKSTACK {
	LinkNode head;
	int size;
}LinkStack;

//初始化函数
LinkStack* Init_LinkStack();
//入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data);
//出栈
void Pop_LinkStack(LinkStack* stack);
//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack);
//返回栈元素的个数
int Size_LinkStack(LinkStack* stack);
//清空栈
void clear_LinkStack(LinkStack* stack);
//销毁栈
void FreeSpace_LinkStack(LinkStack* stack);

#endif // !LINKSTACK_H

LinkStack.c

#include "LinkStack.h"

//初始化函数
LinkStack* Init_LinkStack()
{
	LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
	stack->head.next = NULL;
	stack->size = 0;

	return stack;
}

//入栈
void Push_LinkStack(LinkStack* stack, LinkNode* data)
{
	if (!stack || !data)
	{
		return;
	}

	data->next = stack->head.next;
	stack->head.next = data;
	stack->size++;
}

//出栈
void Pop_LinkStack(LinkStack* stack)
{
	if (!stack)
	{
		return;
	}

	if (stack->size == 0)
	{
		return;
	}

	LinkNode* pCurrent = stack->head.next;
	stack->head.next = pCurrent->next;

	stack->size--;
}
//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack)
{
	if (!stack)
	{
		return NULL;
	}

	if (stack->size == 0)
	{
		return NULL;
	}

	return stack->head.next;
}

//返回栈元素的个数
int Size_LinkStack(LinkStack* stack)
{
	return stack->size;
}

//清空栈
void clear_LinkStack(LinkStack* stack)
{
	if (!stack)
	{
		return;
	}

	if (stack->size == 0)
	{
		return;
	}

	stack->head.next = NULL;
	stack->size = 0;
}

//销毁栈
void FreeSpace_LinkStack(LinkStack* stack)
{
	if (!stack)
	{
		return;
	}

	free(stack);
}

main.c

#include "LinkStack.h"

typedef struct PERSON
{
	LinkNode node;
	char name[64];
	int age;
}Person;

int main()
{
	//创建栈
	LinkStack* stack = Init_LinkStack();
	//创建数据
	Person p1, p2, p3, p4, p5;
	strcpy(p1.name, "aaa");
	strcpy(p2.name, "bbb");
	strcpy(p3.name, "ccc");
	strcpy(p4.name, "ddd");
	strcpy(p5.name, "eee");

	p1.age = 10;
	p2.age = 20;
	p3.age = 30;
	p4.age = 40;
	p5.age = 50;

	//入栈
	Push_LinkStack(stack, (LinkNode*)&p1);
	Push_LinkStack(stack, (LinkNode*)&p2);
	Push_LinkStack(stack, (LinkNode*)&p3);
	Push_LinkStack(stack, (LinkNode*)&p4);
	Push_LinkStack(stack, (LinkNode*)&p5);

	while (Size_LinkStack(stack))
	{
		//取出栈顶元素
		Person* p = (Person*)Top_LinkStack(stack);
		printf("Name:%s Age:%d\n", p->name, p->age);
		//弹出栈顶元素
		Pop_LinkStack(stack);
	}

	FreeSpace_LinkStack(stack);

	return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部