您的位置：首页 > 新闻 > 会展 > 泉州网站建设费用_网络营销的三种方式_适合30岁女人的培训班_西安网站建设制作

泉州网站建设费用_网络营销的三种方式_适合30岁女人的培训班_西安网站建设制作

2025/8/19 12:03:07 来源：https://blog.csdn.net/2403_87794049/article/details/147164482  浏览:  次   关键词：泉州网站建设费用_网络营销的三种方式_适合30岁女人的培训班_西安网站建设制作
泉州网站建设费用_网络营销的三种方式_适合30岁女人的培训班_西安网站建设制作

一、栈：LIFO 特性的完美诠释

（一）核心概念与抽象模型

  1. 定义与特性
    栈是一种严格遵循后进先出（LIFO）原则的线性数据结构，其操作被限制在栈顶（Top）进行。形象化理解：如同堆叠的餐盘，最后放置的餐盘最先被取用。

    • 压栈（Push）：数据从栈顶插入，时间复杂度 O (1)
    • 出栈（Pop）：数据从栈顶删除，时间复杂度 O (1)
    • 典型场景：函数调用栈（保存调用上下文）、表达式求值（处理运算符优先级）、历史记录回退（如浏览器的 “后退” 功能）。

  2. 逻辑模型与物理结构
    栈的逻辑结构是线性表，但物理实现有两种选择：

    • 数组实现：利用动态数组，通过top指针记录栈顶位置（下标从 0 或 - 1 开始），适合频繁尾操作
    • 链表实现：用单链表，头节点作为栈顶，插入 / 删除在头部进行，适合内存动态分配场景

（二）数组实现的工程细节（C 语言）

1. 结构体定义与初始化
typedef int STDataType;
typedef struct Stack {STDataType* data;     // 动态数组存储数据int top;              // 栈顶下标int capacity;         // 当前最大容量
} Stack;void StackInit(Stack* stack) {stack->data = (STDataType*)malloc(4 * sizeof(STDataType));if (stack->data == NULL) {        perror("malloc fali");return; // 内存分配失败处理}stack->top = 0;stack->capacity = 4;
}
2. 核心操作实现
  • 压栈（含扩容逻辑） 
    void StackPush(Stack* stack, STDataType value) {// 检查是否需要扩容if (stack->top == stack->capacity - 1) {int newCapacity = stack->capacity * 2;STDataType* newData = (STDataType*)realloc(stack->data, newCapacity * sizeof(STDataType));if (newData == NULL) {perror("realloc fail");return; // 扩容失败处理}stack->data = newData;stack->capacity = newCapacity;}stack->data[stack->top++] = value;
}
  • 出栈（需处理栈空异常） 
    void StackPop(Stack* stack) {if (StackEmpty(stack))return; // 空栈无法出栈stack->top--; // 直接调整指针，无需物理删除（懒删除）
}
  • 获取栈顶元素 
    STDataType StackTop(Stack* stack) {if (StackEmpty(stack)) return; // 空栈访问异常return stack->data[stack->top];
}
3. 复杂度分析
  • 压栈 / 出栈：均摊 O (1)（扩容时单次 O (n)，但均摊后为常数）
  • 空间复杂度：O (n)（存储 n 个元素）

（三）典型应用：有效的括号

问题：判断字符串"()[]{}"是否括号匹配
算法步骤：

  1. 遍历字符串，遇左括号({[则压栈
  2. 遇右括号) ] }则检查栈顶是否为对应左括号：                                                                                            匹配则出栈，不匹配则直接返回 false
  3.      遍历结束后，栈空则合法，否则剩余左括号未匹配

代码关键点：用字典（或 switch）建立左右括号映射关系，处理边界情况（如字符串长度为奇数直接非法）。

二、队列：FIFO 特性的典型代表

（一）核心概念与抽象模型

  1. 定义与特性
    队列是遵循先进先出（FIFO）原则的线性结构，插入操作在队尾（Rear），删除操作在队头（Front）。形象化理解：如同排队购票，先排队的人先接受服务。

    • 入队（Enqueue）：数据从队尾插入，时间复杂度 O (1)
    • 出队（Dequeue）：数据从队头删除，时间复杂度 O (1)
    • 典型场景：操作系统进程调度（如就绪队列）、网络请求缓冲、BFS 算法（逐层访问图节点）。

  2. 逻辑模型与物理结构

    • 链表实现：用双向链表或单链表，维护头指针（队头）和尾指针（队尾），适合频繁头尾操作
    • 数组实现：普通数组实现需移动元素（头删除低效），故更适合循环队列实现

（二）链表实现的工程细节（C 语言）

1. 结构体定义与初始化
typedef int QDataType;
// 队列节点
typedef struct QueueNode {QDataType value;struct QueueNode* next;
} QueueNode;// 队列整体结构
typedef struct Queue {QueueNode* front; // 队头指针（指向第一个节点）QueueNode* rear;  // 队尾指针（指向最后一个节点）int size;         // 元素个数（优化：避免遍历计算长度）
} Queue;void QueueInit(Queue* queue) {queue->front = queue->rear = NULL;queue->size = 0;
}
2. 核心操作实现
  • 入队（处理空队列场景） 
    void QueuePush(Queue* queue, QDataType value) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL){peeror("malloc fail");return;}newNode->value = value;newNode->next = NULL;if (QueueEmpty(queue)) { // 空队列时头尾指针指向同一节点queue->front = queue->rear = newNode;} else { // 非空时尾指针的next指向新节点，尾指针后移queue->rear->next = newNode;queue->rear = newNode;}queue->size++;
}
  • 出队（处理单节点队列） 
    void QueuePop(Queue* queue) {if (QueueEmpty(queue)) return;QueueNode* temp = queue->front;queue->front = queue->front->next; // 头指针后移free(temp); // 释放内存if (queue->front == NULL) { // 若删除后队列为空，尾指针置空queue->rear = NULL;}queue->size--;
}
  • 获取队头 / 队尾元素 
    QDataType QueueFront(Queue* queue) {if (QueueEmpty(queue))return;return queue->front->value;
}
QDataType QueueBack(Queue* queue) {if (QueueEmpty(queue)) return;return queue->rear->value;
}

（三）特殊实现：设计循环队列

1. 设计目标

避免普通数组队列 “假溢出” 问题（队尾到达数组末尾但头部有空闲空间），通过环形结构复用空间。

2. 关键参数与状态判断
typedef struct {int* data;       // 存储数组int front;       // 队头下标（指向实际队头元素）int rear;        // 队尾下标（指向队尾元素的下一个空位）int capacity;    // 数组容量（含一个预留空位）
} MyCircularQueue;
  • 队空条件：front == rear
  • 队满条件：(rear + 1) % capacity == front
  • 元素个数：(rear - front + capacity) % capacity
3. 核心操作实现（入队为例）
bool MyCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (MyCircularQueueIsFull(obj)) return false;obj->data[obj->rear] = value; // 先赋值obj->rear = (obj->rear + 1) % obj->capacity; // 再移动指针return true;
}

三、深度对比：栈 vs 队列的本质差异

维度栈（Stack）队列（Queue）
数据访问原则后进先出（LIFO）先进先出（FIFO）
操作限制仅栈顶可插入 / 删除队尾插入、队头删除
典型底层实现数组（动态扩容，尾操作高效）链表（头尾指针，头删除高效）
空间特性栈顶指针移动，无需频繁内存分配节点动态创建 / 销毁，可能有碎片
适用算法深度优先搜索（DFS）、递归模拟广度优先搜索（BFS）、层次遍历
内存管理数组实现需处理扩容（均摊 O (1)）链表实现需手动释放节点内存

四、进阶应用：数据结构的 “跨界” 实现

1. 用队列实现栈 

核心思路：维护两个队列q1和q2，入栈时将元素加入非空队列，出栈时将非空队列的前 n-1 个元素转移到另一个队列，最后剩余元素即为栈顶。

  • 入栈操作：push(x) → 加入非空队列（若均空则选q1）
  • 出栈操作：pop() → 将非空队列的元素依次出队并入队到另一个队列，直到剩 1 个元素，弹出该元素

2. 用栈实现队列

核心思路：两个栈inStack和outStack，入队时压入inStack，出队时若outStack为空则将inStack全部元素倒序压入outStack（实现 FIFO）。

  • 入队操作：push(x) → inStack.push(x)
  • 出队操作：pop() → 若outStack空，先将inStack全部转移到outStack，再弹出outStack栈顶

五、工程实践中的注意事项

1. 边界条件处理

  • 栈操作需检查栈空（避免越界访问）
  • 队列操作需检查队空（避免空指针解引用）
  • 循环队列需严格区分队空与队满条件（通过预留空位或计数器）

2. 内存管理最佳实践

  • 数组实现的栈 / 队列：初始化时分配合理初始容量，扩容时使用realloc避免数据拷贝
  • 链表实现的队列：出队时必须释放节点内存，销毁队列时需遍历释放所有节点
  • 避免内存泄漏：建立 “初始化 - 使用 - 销毁” 的完整生命周期管理流程

3. 语言特性适配

  • C++：可直接使用 STL 的stack（底层 deque）和queue（底层 list/deque）
  • Python：collections.deque提供高效的头尾操作（替代原生 list 的pop(0)低效操作）
  • Java：java.util.Stack（过时，推荐用Deque实现），Queue接口有LinkedList等实现

六、总结：数据结构设计的本质

栈和队列的核心价值在于通过限制操作接口，实现特定的访问顺序。这种 “受限的数据访问” 思想是计算机科学的重要设计范式：

  • 栈的 LIFO 特性适合处理 “嵌套”“回溯” 场景（如函数调用、语法分析）
  • 队列的 FIFO 特性适合处理 “有序”“缓冲” 场景（如任务调度、数据流处理）

理解这两种结构，不仅要掌握 API 接口，更要深入底层实现（数组 vs 链表的选择、边界条件处理、内存管理），以及在算法设计中的灵活运用（如用栈模拟递归，用队列实现层序遍历）。它们是理解更复杂数据结构（如优先队列、双端队列）的基础，更是培养 “问题建模能力” 的重要切入点。

通过实际编码实现栈和队列的各个操作，处理各种边界情况，才能真正掌握其精髓 —— 这正是计算机科学 “从抽象到具体” 的工程思维体现。

附录

栈

//stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;		// 栈顶int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

//stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
// 初始化栈 
void StackInit(Stack* ps)
{ps->arr = NULL;ps->capacity = ps->top = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = data;}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}
// 出栈 
void StackPop(Stack* ps)
{assert(!StackEmpty(ps));--ps->top;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(!StackEmpty(ps));return ps->top;}
// 销毁栈 
void StackDestroy(Stack* ps)
{if (ps->arr != NULL)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}

队列

//Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* front;QNode* rear;
}Queue;// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

//Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
// 初始化队列 
void QueueInit(Queue* q)
{q->front = q->rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail1");exit(1);}newnode->data = data;newnode->next = NULL;if (q->front == NULL){q->front = q->rear = newnode;}else{q->rear->next = newnode;q->rear = newnode;}
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->front == NULL;
}
// 队头出队列 
void QueuePop(Queue* q)
{assert(!QueueEmpty(q));if (q->front == q->rear){free(q->front);q->front = q->rear = NULL;}else{QNode* tmp = q->front->next;free(q->front);q->front = tmp;}
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(!QueueEmpty(q));return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(!QueueEmpty(q));return q->rear->data;}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);int count = 0;QNode* tmp = q->front;while (tmp != NULL){count++;tmp = tmp->next;}return count;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode* pcur = q->front;while (q->front){QNode* tmp = q->front->next;free(q->front);q->front = tmp;}q->front = q->rear = NULL;
}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

利用Transformer模型提升商品检索效果 高等数学 8.5 曲面及其方程 相比于直接消费 MCP 服务，您的企业可能更需要一个专属的 MCP 服务中心 思考 增强服务器防御能力的自动化工具 Fail2Ban 5.5 with管理上下文

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989