【数据结构】栈和队列——栈

目录

  • 栈和队列
    • 栈
      • 栈的基本概念
      • 栈的顺序存储实现
        • 栈的定义与初始化
        • 入栈操作
        • 出栈操作
        • 读取栈顶元素
        • 判空和判满操作
        • 栈的销毁操作
        • 操作集合

栈和队列

栈

栈的基本概念

栈的定义：

  • 栈（Stack） 是一种线性表，它限定了数据元素的插入和删除操作只能在表的一端进行。
  • 允许操作的一端称为 栈顶（Top），另一端称为 栈底（Bottom）。

所以，栈就是 “先进后出（FILO, First In Last Out）” 的数据结构。

栈的特点：

  • 受限性：只能在栈顶进行插入（push）和删除（pop）。
  • 线性结构：元素有先后次序。
  • FILO 特性：最先入栈的元素最后出栈。

形象理解：就像一摞盘子，先放进去的盘子在最下面，拿的时候只能从最上面一个个拿走。

栈的基本操作：

  • Push（入栈）：在栈顶插入一个新元素。
  • Pop（出栈）：删除栈顶元素，并返回该元素。
  • GetTop（读栈顶元素）：仅仅读取栈顶元素，不删除。
  • InitStack（初始化栈）：建立一个空栈。
  • StackEmpty（判空）：检查栈是否为空。
  • StackFull（判满，顺序栈时需要）：判断栈是否已满。

栈的存储结构：

  1. 顺序栈：
    • 用数组存储栈元素。
    • 优点：实现简单，存取快。
    • 缺点：容量固定，可能溢出（上溢/下溢）。
      在这里插入图片描述
  2. 链式栈
    • 用链表存储，栈顶一般在链表的表头。
    • 优点：容量不受限制。
    • 缺点：需要额外指针，操作相对慢。
      在这里插入图片描述

栈的顺序存储实现

栈的定义与初始化

顺序栈是栈的一种顺序存储结构，用数组（连续内存）来存放数据元素。特点：

  1. 栈顶指针（top）指向栈顶元素的位置（或空元素的下一个位置）。
  2. 栈容量固定（静态）或可扩展（动态）。
  3. 支持的基本操作：
    • 初始化栈 InitStack
    • 入栈 Push
    • 出栈 Pop
    • 判空 IsEmpty
    • 获取栈顶元素 GetTop

顺序栈top 指针的指向在不同教材中有差异：

  1. top 指向栈顶元素（经典写法，大部分算法书和面试中用的）
    • top 是数组下标
    • 空栈时：top = -1
    • 入栈：先 top++，再存元素
    • 出栈：取 data[top]，再 top--
    • 特点：top 总是指向有效元素的位置
  2. top 指向栈顶下一个空位（部分教材/视频中用）
    • top 是指针
    • 空栈时：top = 0
    • 入栈：直接存到 data[top]，然后 top++
    • 出栈：先 top--，再取 data[top]
    • 特点：top 表示栈中元素数量，也就是下一个可用位置

两种方法逻辑不同，但功能一样，只是 top 的含义不同。

静态顺序栈：

  • 定义：
    #define MAXSIZE 100
typedef int SElemType;  // 假设存储 int 类型typedef struct {SElemType *base;   // 栈底指针，指向数组首地址SElemType *top;    // 栈顶指针，指向栈顶元素的下一个位置int stacksize;     // 栈容量
} SqStack;
  • 初始化：
    // 初始化
void InitStack(SqStack *S) {S->base = data;      // base 指向数组首地址S->top = S->base;    // 空栈，top 指向第一个空位S->stacksize = MAXSIZE;
}
    特点：
    • 容量固定，无法扩容
    • top 指向栈顶元素的下一个位置
    • 入栈/出栈时用 *(S->top++) = e / *e = *(--S->top)

动态顺序栈： 动态顺序栈可以在栈满时自动扩容。

  • 定义：
    typedef int SElemType;typedef struct {SElemType *base;   // 栈底指针SElemType *top;    // 栈顶指针，指向栈顶元素的下一个位置int stacksize;     // 当前容量
} SqStack;
  • 初始化：
    // 初始化
int InitStack(SqStack *S, int initSize) {S->base = (SElemType *)malloc(initSize * sizeof(SElemType));if (!S->base) return 0;   // 分配失败S->top = S->base;         // 空栈S->stacksize = initSize;return 1;
}

动态顺序栈可以在 Push 时判断容量是否够，如果不够就 realloc 扩容。

#include <stdio.h>
#include <stdlib.h>typedef int SElemType;  // 统一元素类型typedef struct {SElemType *base;    // 栈底指针SElemType *top;     // 栈顶指针（指向栈顶元素的下一个位置）int stacksize;      // 当前容量
} SqStack;// 初始化栈
int InitStack(SqStack *S, int initSize) {S->base = (SElemType *)malloc(initSize * sizeof(SElemType));if (!S->base) return 0;  // 分配失败S->top = S->base;        // 空栈：栈顶=栈底S->stacksize = initSize;return 1;
}// 入栈
int Push(SqStack *S, SElemType x) {// 判断栈满，需要扩容if (S->top - S->base >= S->stacksize) {int newSize = S->stacksize * 2;SElemType *newBase = (SElemType *)realloc(S->base, newSize * sizeof(SElemType));if (!newBase) return 0;  // 扩容失败// 更新指针和容量S->top = newBase + (S->top - S->base);  // 调整栈顶指针（原偏移量不变）S->base = newBase;S->stacksize = newSize;printf("栈扩容到 %d\n", newSize);}*(S->top++) = x;  // 先赋值，再移动栈顶指针return 1;
}// 出栈（将栈顶元素存入e，成功返回1，失败返回0）
int Pop(SqStack *S, SElemType *e) {if (S->top == S->base) return 0;  // 空栈*e = *(--S->top);  // 先移动栈顶指针，再取值return 1;
}int main() {SqStack S;if (!InitStack(&S, 3)) {  // 初始容量3printf("栈初始化失败\n");return 1;}// 入栈10个元素（测试扩容）for (int i = 1; i <= 10; i++) {if (Push(&S, i)) {printf("入栈: %d, 当前元素数: %d\n", i, S.top - S.base);} else {printf("入栈 %d 失败\n", i);}}// 出栈所有元素SElemType e;printf("\n出栈顺序：\n");while (Pop(&S, &e)) {printf("出栈: %d\n", e);}free(S.base);  // 释放堆内存return 0;
}
入栈操作

入栈（Push） 就是把一个新元素压入栈顶的操作。
核心逻辑：

  1. 判断栈是否已满（静态栈）或是否需要扩容（动态栈）。
  2. 栈顶指针 top 上移（或计算位置）。
  3. 将元素放到栈顶位置。
  4. 更新 top（或数组索引）。

栈遵循 后进先出（LIFO） 原则，所以新元素总是放在栈顶。

静态顺序栈入栈：

void Push(SqStack *S, int e) {// 判断是否栈满if (S->top - S->base >= S->stacksize) {return 0;   // 入栈失败}*(S->top) = e;  // 把元素放到 top 指向的位置S->top++;       // top 后移，指向下一个空位return 1;       // 入栈成功
}
  • 空栈时：top == base。
  • 入栈成功后：top 始终指向“栈顶元素的下一个位置”。
  • 栈满条件：top - base == stacksize。
  • 栈顶元素：*(top - 1)。

动态顺序栈入栈：

// 入栈
void Push(SqStack *S, int e) {if (S->top - S->base >= S->stacksize) {   // 栈满，需要扩容S->base = (ElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(ElemType));if (!S->base) exit(0); // 内存不足S->top = S->base + S->stacksize;  // 重新定位 topS->stacksize += STACKINCREMENT;   // 更新容量}*(S->top) = e;   // 把元素放到栈顶S->top++;        // top 指针上移
}

动态顺序栈入栈图示：

   初始栈（容量=3）         入栈扩容后（容量=6）
+----+----+----+        +----+----+----+----+----+----+
| 10 | 20 | 30 |        | 10 | 20 | 30 | 40 |    |    |
+----+----+----+        +----+----+----+----+----+----+↑                                ↑top                              top
出栈操作
// 出栈操作：将栈顶元素弹出并返回给 e
int Pop(SqStack *S, int *e) {if (S->top == S->base) return 0;   // 栈空S->top--;                              // 指针下移*e = *(S->top);                        // 取出元素return 1;
}

S->top--; 和 *e = *(S->top); 可以合并为 *e = *(--S->top);

有道例题：写出下列程序段的输出结果

void main(){Stack S;InitStack(S);x='c'; y='k';Push(S,x); Push(S,'a'); Push(S,y);Pop(S,x);  Push(S,'t'); Push(S,x);Pop(S,x);  Push(S,'s');While(!StackEmpty(S)) {Pop(S,y); printf(y);}printf(x);
}

Pop 会将出栈的数据返回，在这题中的重点是 Pop 操作会改变原来 x 中的数据

读取栈顶元素

核心思想：

  • 栈顶元素位于 top 的前一个位置（因为 top 指向栈顶元素的下一个空位）。
  • 不改变 top 指针的值，只是返回栈顶元素。
// 取栈顶元素，不出栈
int GetTop(SqStack S, int *e) {if (S.top == S.base) return ERROR; // 空栈*e = *(S.top - 1);                // 栈顶元素return 1;
}
  • top 指向栈顶元素的下一个位置；
  • 栈顶元素是 *(top - 1)；
  • GetTop 不改变栈结构，只返回栈顶元素；
判空和判满操作
  1. 判空操作：
    核心思想：栈空时，top == base，因为没有元素，栈顶指针就在栈底。
    // 判空
int StackEmpty(SqStack S) {if (S.top == S.base) return 1;   // 栈空else return 0;   // 栈非空
}
  2. 判满操作
    核心思想：栈满时，top - base == stacksize，因为栈顶指针指向下一个空位，减去栈底得到元素个数等于容量。
    // 判满
int StackFull(SqStack S) {if (S.top - S.base == S.stacksize)return 1;   // 栈满elsereturn 0;   // 栈未满
}
栈的销毁操作

核心思想：

  • 栈底指针 base 是动态分配的，所以只需要 free(base)。
  • 销毁后，将 base 和 top 置为 NULL，stacksize 置为 0，防止野指针。
Status DestroyStack(SqStack *S) {if (S->base) {free(S->base);   // 释放动态分配的内存S->base = NULL;S->top = NULL;S->stacksize = 0;return OK;}return ERROR;         // 栈本身为空或未初始化
}
  • 栈使用 malloc 分配内存后，必须用 free 释放，否则会 内存泄漏。
  • 销毁后把 base 和 top 置为 NULL，stacksize 置 0，避免野指针。
  • 对静态顺序栈（数组固定分配）则不需要销毁操作，因为数组在栈上分配，程序结束自动释放。
操作集合
#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100
#define OK 1
#define ERROR 0typedef int Status;
typedef int SElemType;// 顺序栈定义（老师写法）
typedef struct {SElemType *base;   // 栈底指针SElemType *top;    // 栈顶指针（指向下一个空位）int stacksize;     // 栈容量
} SqStack;// 初始化栈
Status InitStack(SqStack *S) {S->base = (SElemType *)malloc(MAXSIZE * sizeof(SElemType));if (!S->base) return ERROR;S->top = S->base;S->stacksize = MAXSIZE;return OK;
}// 入栈
Status Push(SqStack *S, SElemType e) {if (S->top - S->base == S->stacksize) return ERROR; // 栈满*(S->top) = e;S->top++;return OK;
}// 出栈
Status Pop(SqStack *S, SElemType *e) {if (S->top == S->base) return ERROR; // 空栈S->top--;*e = *(S->top);return OK;
}// 取栈顶元素（不出栈）
Status GetTop(SqStack S, SElemType *e) {if (S.top == S.base) return ERROR; // 空栈*e = *(S.top - 1);return OK;
}// 判空
Status StackEmpty(SqStack S) {return S.top == S.base ? 1 : 0;
}// 判满
Status StackFull(SqStack S) {return (S.top - S.base == S.stacksize) ? 1 : 0;
}// 销毁栈
Status DestroyStack(SqStack *S) {if (S->base) {free(S->base);S->base = NULL;S->top = NULL;S->stacksize = 0;return OK;}return ERROR;
}// 打印栈内元素（从栈底到栈顶）
void PrintStack(SqStack S) {SElemType *p = S.base;while (p < S.top) {printf("%d ", *p);p++;}printf("\n");
}// 测试顺序栈操作
int main() {SqStack S;if (InitStack(&S) == ERROR) {printf("栈初始化失败！\n");return 0;}printf("栈是否为空: %d\n", StackEmpty(S));// 入栈for (int i = 1; i <= 5; i++) {Push(&S, i);printf("入栈: %d, 栈顶元素: %d\n", i, *(S.top - 1));}printf("当前栈: ");PrintStack(S);printf("栈是否已满: %d\n", StackFull(S));// 取栈顶元素SElemType e;if (GetTop(S, &e) == OK) {printf("栈顶元素: %d\n", e);}// 出栈while (!StackEmpty(S)) {Pop(&S, &e);printf("出栈元素: %d\n", e);}printf("栈是否为空: %d\n", StackEmpty(S));// 销毁栈DestroyStack(&S);printf("销毁栈后, 栈容量: %d, base指针: %p\n", S.stacksize, S.base);return 0;
}

程序运行结果如下：
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/94323.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/94323.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

大数据管理与应用系列丛书《数据挖掘》读书笔记之集成学习(1)

大数据管理与应用系列丛书《数据挖掘》读书笔记之集成学习(1)

文章目录前言一、集成学习是什么&#xff1f;1.基本思想2.集成学习的类型3. 集成学习的结合策略3.1 为什么结合策略是集成学习的灵魂&#xff1f;3.2 经典策略(1)**投票法&#xff08;Voting&#xff09;****(2)平均法&#xff08;Averaging&#xff09;****(3) 学习法**3.3 关…
阅读更多...
嵌入式知识篇---32GUI

嵌入式知识篇---32GUI

要理解 32 位单片机的 GUI&#xff0c;咱们先从 “基础概念” 入手&#xff0c;再拆成 “为什么能跑 GUI”“核心组成”“怎么实现”“常用工具”“实际用途” 这几步讲&#xff0c;全程不用复杂术语&#xff0c;像聊日常用品一样说清楚。一、先搞懂 2 个基础概念在讲 “32 位单…
阅读更多...
【iOS】SDWebImage第三方库源码学习笔记

【iOS】SDWebImage第三方库源码学习笔记

前言之前在写项目时&#xff0c;经常用到SDWebImage这个第三方库来加载图片&#xff0c;并且了解到了这个第三方库在处理图片时自带异步下载和缓存功能&#xff0c;以及对cell复用的处理。这篇文章来系统学习一下SDWebImage第三方库的知识以及底层原理简介SDWebImage为UIImageV…
阅读更多...
Linux --网络基础概念

Linux --网络基础概念

一.网络发展独立模式&#xff1a;在早期计算机之间是相互独立的&#xff0c;机器之间的数据只能通过软硬盘来传输&#xff0c;这就代表无法同时完成任务&#xff0c;需要前面的计算机完成各自的任务经过硬盘传递数据再完成自己的任务&#xff0c;效率十分低下。网络互联&#x…
阅读更多...
教育系统搭建攻略：线上知识付费与线下消课排课全解析

教育系统搭建攻略：线上知识付费与线下消课排课全解析

作为一名资深平台测评师&#xff0c;最近我挖到了一个教育机构的 “宝藏工具”—— 乔拓云教育系统。别看它名字低调&#xff0c;用起来那叫一个顺手&#xff0c;线上知识付费、线下消课排课全给你安排得明明白白&#xff0c;简直是机构老板和教务员的 “摸鱼神器”。多端口管理…
阅读更多...
PMP项目管理知识点-①项目基本概念

PMP项目管理知识点-①项目基本概念

目录 1.项⽬的定义 概念&#xff1a; 特点&#xff1a; 项⽬与运营的区别 项⽬特点&#xff1a; 运营特点&#xff1a; 2.项⽬管理的发展 3.项⽬、项⽬集与项⽬组合 结构层次 4.项⽬的关键组成部分 项⽬⽣命周期&#xff1a; 项⽬管理过程组&#xff1a; 项⽬阶段&…
阅读更多...
Python内置函数全解析：30个核心函数语法、案例与最佳实践指南

Python内置函数全解析：30个核心函数语法、案例与最佳实践指南

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 持续学习&#xff0c;不断…
阅读更多...
数据建模怎么做？一文讲清数据建模全流程

数据建模怎么做？一文讲清数据建模全流程

目录 一、需求分析 1. 搞清楚业务目标&#xff1a;这数据是要解决啥问题&#xff1f; 2. 明确数据边界&#xff1a;哪些数据该要&#xff0c;哪些不该要&#xff1f; 3. 弄明白使用场景&#xff1a;谁用这数据&#xff0c;怎么用&#xff1f; 二、模型设计 1. 第一步&…
阅读更多...
胸部X光片数据集：健康及肺炎2类，14k+图像

胸部X光片数据集：健康及肺炎2类，14k+图像

胸部X光片数据集概述 数据集包含14090张图像，分为正常胸部X光3901张，肺炎胸部X光10189张。 标注格式：无标注，文件夹分类。 图像尺寸：640*640 正常胸部X光： 肺炎胸部X光： 数据采集： 拍摄方式：均为前后位（anterior-posterior）胸部X光，属患者常规临床护理的一部分…
阅读更多...
MySQL數據庫開發教學(二) 核心概念、重要指令

MySQL數據庫開發教學(二) 核心概念、重要指令

書接上回&#xff1a;MySQL數據庫開發教學(一) 基本架構-CSDN博客 建議工具&#xff1a; Navicat Premium (收費 / 需破解)&#xff1a;Navicat Premium | 管理和开发你的数据库 phpstudy 2018 (免費)&#xff1a;phpStudy - Windows 一键部署 PHP 开发环境 小皮出品 前言 …
阅读更多...
【40页PPT】数字工厂一体化运营管控平台解决方案（附下载方式）

【40页PPT】数字工厂一体化运营管控平台解决方案（附下载方式）

篇幅所限&#xff0c;本文只提供部分资料内容&#xff0c;完整资料请看下面链接 https://download.csdn.net/download/2501_92808811/91716541 资料解读&#xff1a;【40页PPT】数字工厂一体化运营管控平台解决方案 详细资料请看本解读文章的最后内容。该资料围绕数字工厂一体…
阅读更多...
数据产品（2）用户画像数据分析模型

数据产品（2）用户画像数据分析模型

目录 1 用户画像 2 RFM模型 (用户价值分群模型) 3 PSM 价格敏感度 4 精细化运营 1 用户画像 也称用户表标签，是基于用户行为分析获得的对用户的一种认知表达，即用户数据标签化，通过收集与分析用户的用户属性（年龄、性别、城市、职业、设备、状态）、用户偏好（购物偏好，听…
阅读更多...
03_数据结构

03_数据结构

第3课&#xff1a;数据结构 课程目标 掌握Python的基本数据结构&#xff1a;列表、元组、字典、集合学习字符串的高级操作方法理解不同数据结构的特点和适用场景 1. 列表&#xff08;List&#xff09; 1.1 列表的创建和基本操作 # 创建列表 fruits ["苹果", "香…
阅读更多...
【JavaEE】多线程 -- CAS机制(比较并交换)

【JavaEE】多线程 -- CAS机制(比较并交换)

目录CAS是什么CAS的应用实现原子类实现自旋锁ABA问题ABA问题概述ABA问题引起的BUG解决方案CAS是什么 CAS (compare and swap) 比较并交换&#xff0c;CAS 是物理层次支持程序的原子操作。说起原子性&#xff0c;这就设计到线程安全问题&#xff0c;在代码的层面为了解决多线程…
阅读更多...
The United Nations Is Already Dead

The United Nations Is Already Dead

The United Nations Is Already Dead When children in Gaza rummage through rubble for food, when UN-run schools are reduced to dust, when the Security Council cannot even pass the mildest ceasefire resolution—blocked by a single veto— we must confront a br…
阅读更多...
Kubernetes v1.34 前瞻：资源管理、安全与可观测性的全面进化

Kubernetes v1.34 前瞻：资源管理、安全与可观测性的全面进化

预计正式发布&#xff1a;2025年8月底 | 分类&#xff1a;Kubernetes 随着2025年8月底的临近&#xff0c;Kubernetes社区正紧锣密鼓地准备下一个重要版本——v1.34的发布。本次更新并非简单的功能叠加&#xff0c;而是在资源管理、安全身份、可观测性和工作负载控制等核心领域的…
阅读更多...
用 Bright Data MCP Server 构建实时数据驱动的 AI 情报系统：从市场调研到技术追踪的自动化实战

用 Bright Data MCP Server 构建实时数据驱动的 AI 情报系统：从市场调研到技术追踪的自动化实战

前言 本文通过两个真实场景&#xff08;云服务商对比与 AIGC 技术追踪&#xff09;&#xff0c;展示了如何使用 Bright Data MCP Server 与 Lingma IDE 构建一个具备实时网页数据抓取、结构化分析与自动化报告生成能力的 AI 工作流。通过简单的 API 调用与 JSON 配置&#xff…
阅读更多...
牛顿第二定律的所有表达方式：1、线性表达 2、圆形表达 3、双曲线表达 4、抛物线表达5、数列表达

牛顿第二定律的所有表达方式：1、线性表达 2、圆形表达 3、双曲线表达 4、抛物线表达5、数列表达

牛顿第二定律是经典力学中的核心定律&#xff0c;表述为&#xff1a;物体的加速度与所受合力成正比&#xff0c;与质量成反比&#xff0c;方向与合力方向相同。其基本矢量形式为&#xff1a; F⃗ma⃗ \vec{F} m \vec{a} Fma 其中&#xff0c;F⃗\vec{F}F 是合力&#xff08;单…
阅读更多...
【开发日记】SpringBoot 实现支持多个微信小程序的登录

【开发日记】SpringBoot 实现支持多个微信小程序的登录

在实际业务场景中&#xff0c;需要一个后台同时支持多个微信小程序的登录。例如&#xff0c;企业有多个不同业务的小程序&#xff0c;但希望统一在同一个后台系统里进行用户认证和数据处理。这时候&#xff0c;我们就需要一个灵活的方式来管理多个小程序的 appid 和 secret&…
阅读更多...
Docker 容器（一）

Docker 容器（一）

Docker一、Docker是什么1.什么是Docker2.Docker特点3.比较虚拟机和容器二、Docker安装1.Docker​​三大核心组件​​2.安装步骤&#xff08;Ubuntu&#xff09;3.阿里云镜像加速三、Docker镜像1.什么是镜像2.UnionFS&#xff08;联合文件系统&#xff09;3.Docker镜像加载原理4…
阅读更多...
最新文章

Copyright @ 2022~2023