栈与队列（概念与实现）

#pragma once
#include<stdio.h>
#include<assert.h>
#include <stdlib.h> 
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack//动态
{
	STDataType* val;//底层数组
	int top;      //有效数据
	int capacity; //可用容量
}Stack;

//初始化
void StackInit(Stack*ps);
//入栈/压栈/进栈
void StackPush(Stack* ps,STDataType x );
//判断栈空
bool StackEmpty(Stack*ps);
//出栈
void StackPop(Stack* ps);
//取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//栈的销毁
void StackDestory(Stack* ps);

源文件，操作实现文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化
void StackInit(Stack* ps)
{
	assert(ps);//为什么要判空？
	ps->val = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->val, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc faill!\n");
			exit(1);
		}
 		ps->val = tmp;
		ps->capacity = newCapacity;
	}
		ps->val[ps->top++] = x;
	
}
bool StackEmpty(Stack*ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackPop(Stack* ps)
{
	assert(ps);
	ps->top--;
}
STDataType StackTop(Stack* ps)
{
	assert(!StackEmpty(ps));//assert(ps);为什么不可以？这里是判断是否有数据
	return ps->val[ps->top-1];
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
void StackDestory(Stack* ps)
{
	if (ps->val != NULL)
		free(ps->val);
	ps->val = NULL;
	ps->top = ps->capacity = 0;
}

3，栈的用途

栈（Stack）是一种后进先出（Last In First Out, LIFO）的数据结构，它在计算机科学中有着广泛的应用。以下是栈的一些主要用途：

函数调用：操作系统使用栈来管理函数调用。当函数被调用时，当前函数的状态会被保存在栈上，包括局部变量、返回地址等。当函数执行完毕后，可以从栈中恢复状态，并返回到调用点。
表达式求值：编译器在解析和求值表达式时，经常使用栈来存储操作数和操作符，特别是对于逆波兰表示法（后缀表达式）。
内存分配：在许多编程语言中，局部变量的内存分配是在栈上进行的。这些变量在函数调用结束时自动从栈中释放。
后进先出的操作：任何需要后进先出逻辑的场景都可以使用栈，例如撤销操作（如撤销在文本编辑器中的更改）、浏览器的后退功能等。
算法中的辅助结构：在许多算法中，栈被用作辅助数据结构，例如深度优先搜索（DFS）、图的遍历、迷宫解决算法等。
括号匹配：在编译器设计中，栈常用来检查表达式中的括号是否匹配。
程序调用的上下文切换：在多任务操作系统中，当任务切换发生时，当前任务的状态会被保存在栈上，当任务再次运行时，可以从栈中恢复其状态。
递归：递归算法通常依赖栈来存储每一层递归调用的状态。
表达式转换：例如，将中缀表达式转换为后缀表达式或前缀表达式。
缓存和缓冲：栈可以用来实现简单的缓存机制，例如在深度优先搜索中存储路径。
错误处理：在某些系统中，错误处理和异常处理的信息被推送到一个错误栈中，以供后续处理。

栈由于其简单而有效的数据管理方式，成为了计算机科学中非常基础且重要的工具之一。

二，队列

1，队列（Queue）

队列也属于线性表，其特点就是，只允许在一端插入数据，在另一端删除数据，因此，其内数据存入的就先取出，即先进先出（First In First Out）。

队列中，插入的一端称为队尾，删除的一端成为对头。

在其中，插入称为入队，删除称为出队。

队列的特点，就像你买早餐排的队伍，先排的就先买到早餐，而后来的就后买到早餐

2，队列的实现

同样，队列也可以由链表和数组构成，进行比较得知，链表更优。

基本结构：

同样，总结一下大致实现步骤：

初始化，判空，赋值

入队，判空，创节点，判断链表是否为空，再进行头尾指针的相关操作。

出队，判断指针与队列是否为空，看队列中数据个数是否大于一，只有一个就free，判空；多于一个就正常操作。

查询队头队尾元素，判空（指针与队列），返回相应指针对应的数值。

查询有效元素数目，返回size，在实现中·新创建的，用于记录元素个数。

销毁，判空，遍历链表，逐个free，头尾节点置空，size置为零。

头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QListNode//链表节点
{
	struct QListNode* next;
	QDataType val;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* rear;
	int size;
}Queue;
//初始化
void QueueInit(Queue* ps);
//插入/入队
void QueuePush(Queue* ps, QDataType x);
//出队列
void QueuePop(Queue* ps);
//判空
bool QueueEmpty(Queue* ps);
//取队列有效元素
int QueueSize(Queue* ps);
//获取队列头部元素
int QueueHead(Queue* ps);
//获取队尾元素
int QueueRear(Queue* ps);
//队列的销毁
void QueueDestory(Queue* ps);

源文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void QueueInit(Queue* ps)
{
	assert(ps);
	ps->head = ps->rear = NULL;
	ps->size = 0;
}
void QueuePush(Queue* ps, QDataType x)
{
	assert(ps);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	if (ps->head == NULL)//判断链表为空
	{
		ps->head = ps->rear = newnode;
	}
	else
	{
		ps->rear->next = newnode;
		ps->rear = newnode;
	}
	ps->size++;
}
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));
	if (ps->size == 1)
	{
		free(ps->head = ps->rear);
		ps->head = ps->rear = NULL;
	}
	else {
		QNode* tmp = ps->head;
		ps->head = ps->head->next;
		free(tmp);
		tmp = NULL;
	}
	ps->size--;
}
bool QueueEmpty(Queue* ps)
{
	assert(ps);
	return ps->head == NULL;
}
int QueueSize(Queue* ps)
{
	return ps->size;
}
int QueueHead(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));
	return ps->head->val;
}
int QueueRear(Queue* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));
	return ps->rear->val;
}
void QueueDestory(Queue* ps)
{
	assert(ps);
	QNode* pcur = ps->head;
	while (pcur)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	ps->head = ps->rear = NULL;
	ps->size = 0;
}

3，队列的用途

队列（Queue）是一种先进先出（First In First Out, FIFO）的数据结构，它在计算机科学和实际应用中有着广泛的使用。以下是队列的一些主要用途：

任务调度：操作系统使用队列来管理待处理的任务和进程。例如，在多任务操作系统中，就绪队列用来存储所有准备好运行的进程。
缓冲：在输入/输出操作中，队列常用来作为缓冲区，以匹配不同速度的设备或组件。例如，打印机队列管理打印任务，确保它们按顺序打印。
消息传递：在并发编程和网络通信中，队列常用于进程或线程间的消息传递，确保消息按照发送顺序被处理。
数据结构：队列可以用于实现其他数据结构，如优先队列（通过优先级来管理元素）和堆栈（通过限制操作来实现后进先出）。
算法：在算法中，队列用于广度优先搜索（BFS）等算法，以层序遍历图或树。
资源管理：在网络中，队列用于管理网络资源，比如在拥塞控制中，队列可以用来存储等待发送的数据包。
事件处理：在图形用户界面（GUI）和游戏开发中，队列用于管理事件，如鼠标点击和键盘输入，确保它们按顺序被处理。
后台处理：在Web开发中，队列可以用于管理后台任务，比如邮件发送、图片处理等，这些任务可以异步执行，不干扰主线程。
数据缓冲：在数据流处理中，队列用于平滑数据流，尤其是在数据到达速度不均匀时。
负载均衡：在分布式系统中，队列可以帮助平衡负载，通过分配任务到不同的服务器或节点。

队列因其简单和高效的特点，在许多不同的场景下都非常有用。它们有助于管理和控制数据的流动，确保操作的顺序性和一致性。

4，环形队列

扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统中生产者消费者模型就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

下面用数组来实现：

要注意的几点，

1，如何判断队列满了？

我们默认rear指针指向的那个位置为空，且一直为空，当head+1=rear时队列就满了。

2，如何实现数组循环？

我们可以对下标取模操作： ( rear + 1 ) % capacity 。

typedef struct {
    int* data; // 存储循环队列的数组
    int head;  // 队列头部索引
    int tail;  // 队列尾部索引
    int size;  // 循环队列的容量
} MyCircularQueue;

// 构造器，设置队列长度为 k
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->data = (int*)malloc(sizeof(int) * (k + 1));
    obj->head = 0;
    obj->tail = 0;
    obj->size = k + 1; // 实际分配 k+1 个空间
    return obj;
}

// 检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}

// 检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail + 1) % obj->size == obj->head;
}

// 向循环队列插入一个元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) {
        return false;
    }
    obj->data[obj->tail] = value;
    obj->tail = (obj->tail + 1) % obj->size;
    return true;
}

// 从循环队列中删除一个元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
    obj->head = (obj->head + 1) % obj->size;
    return true;
}

// 从队首获取元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    return obj->data[obj->head];
}

// 获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    // 由于 tail 指向下一个插入的位置，所以需要减一才是队尾元素
    return obj->data[(obj->tail - 1 + obj->size) % obj->size];
}

// 释放循环队列占用的内存
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->data);
    free(obj);
}

5，环形队列的用途

环形队列（也称为循环队列）非常有用，它在很多场景下都是一种高效的数据结构。以下是环形队列的一些用途和优点：

内存效率：环形队列通常使用固定大小的数组实现，与动态扩容的队列相比，它可以更有效地使用内存，因为它不需要在队列满时重新分配内存。
避免数据搬移：在普通的队列实现中，当队头元素被移除时，所有其他元素都需要向前移动一个位置。环形队列通过循环使用数组来避免这种数据搬移，从而提高性能。
固定大小：环形队列的大小是固定的，这使得它在需要固定资源分配的系统中非常有用，比如嵌入式系统或实时操作系统。
实时系统：在实时系统中，环形队列常用于任务调度和消息传递，因为它们提供了确定性的时间和空间复杂度。
缓冲区管理：在处理流数据（如音频、视频流）时，环形队列可以用作缓冲区，以平滑数据流，避免因数据到达速度不均匀导致的处理问题。
网络通信：在网络通信中，环形队列常用于管理数据包，特别是在实现网络协议时，比如TCP/IP协议栈中的缓冲区管理。
生产者-消费者模型：在多线程编程中，环形队列是生产者-消费者模型的一个常用实现，因为它可以高效地处理并发访问。

以下是环形队列的一些具体优点：

常数时间操作：插入（入队）和删除（出队）操作通常可以在常数时间内完成，因为它们不需要移动队列中的其他元素。
空间重用：环形队列通过循环使用数组空间，使得空间利用率更高。
无锁队列：在某些实现中，环形队列可以设计为无锁队列，进一步提高并发环境下的性能。

总之，环形队列由于其高效性和确定性，在需要高效数据管理和处理的场景中非常有用

标签：ps,head,obj,队列,Queue,概念,int,实现
From： https://blog.csdn.net/2301_80001281/article/details/143255857

栈与队列（概念与实现）

前言

一，栈

1，栈（Stack）

2，栈的实现