队列和栈的实现

60 阅读 0 评论 0 点赞

文章目录

队列
栈

队列

队列的定义

队列（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) 打赏

本文分类：文章资讯
本文标签：队列和栈的实现
浏览次数：60 次浏览
本文链接：https://freeymw.com/article/10454.html

上一篇 > 常见排序算法，快排，希尔，归并，堆排
下一篇 > 算法学习笔记——算法和数据结构简介

评论列表共有 0 条评论

暂无评论

队列和栈的实现

文章目录

队列

队列的定义

队列常见的基本操作

队列的顺序存储结构

实现

栈

栈的定义

栈的常见基本操作

栈的顺序存储

实现

栈的链式存储

实现

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复