关键词：
文章目录
栈和队列
栈和队列都属于线性表
属于"一对一"逻辑关系
栈:“先进后出”
队列:“先进先出”
一 栈
一.什么是栈
看图理解(概念只是辅助理解_理解了才算学会)
-
栈只能从一端存取,另一端是封闭的
-
在栈中,无论是存还是取,都必须遵循"先进后出原则"
==>栈是一种只能从表的一端存取数据,且遵循"先进后出"原则的线性存储结构
进栈和出栈
进栈:将数据存储到站里面
出栈:将数据从栈中间取出
栈的实现方法
栈:"特殊"的线性存储结构
1 顺序表 ==> 顺序栈(顺序存储结构)
2 链表 ==> 链栈(链式存储结构)
栈的应用
例: 撤销,返回功能 …等等
二.顺序栈
入栈:
// **元素入栈
// 参数: 存储结构, 栈顶指针, 数据
// 返回值: 栈顶指针(需要知道结束入栈之后栈顶的位置)
int pushElem(int* arr, int top, int val)
arr[++top] = val; // 初始为-1 数组越界,先移动top位置,后添加数值
printf("元素%d入栈\\n", val);
return top;
出栈:
// **元素出栈
// 参数: 存储结构, 栈顶指针
// 返回值: 栈顶指针
int popElem(int* arr, int top)
// 判断
if (top <= -1)
printf("空栈!\\n");
return -1;
printf("元素%d出栈\\n",arr[top]);
top--; // 向前移动,但原来的数据还在,无需清除,在添加新元素的时候将它替换
return top;
完整代码+测试:
#include<stdio.h>
// **元素入栈
// 参数: 存储结构, 栈顶指针, 数据
// 返回值: 栈顶指针(需要知道结束入栈之后栈顶的位置)
int pushElem(int* arr, int top, int val)
arr[++top] = val; // 初始为-1 数组越界,先移动top位置,后添加数值
printf("元素%d入栈\\n", val);
return top;
// **元素出栈
// 参数: 存储结构, 栈顶指针
// 返回值: 栈顶指针
int popElem(int* arr, int top)
// 判断
if (top <= -1)
printf("空栈!\\n");
return -1;
printf("元素%d出栈\\n",arr[top]);
top--; // 向前移动,但原来的数据还在,无需清除,在添加新元素的时候将它替换
return top;
int main()
// 数组
int arr[100];
// top指针(下标)
int top = -1;
//入栈
top = pushElem(arr, top, 1); //函数返回新的top值赋给top
top = pushElem(arr, top, 2);
top = pushElem(arr, top, 3);
top = pushElem(arr, top, 4);
top = pushElem(arr, top, 5);
//出栈
top = popElem(arr, top);
top = popElem(arr, top);
top = popElem(arr, top);
top = popElem(arr, top);
top = popElem(arr, top);
top = popElem(arr, top);
// **元素入栈
// 参数: 存储结构, 栈顶指针, 数据
// 返回值: 栈顶指针(需要知道结束入栈之后栈顶的位置)
int pushElem(int* arr, int top, int val);
// **元素出栈
// 参数: 存储结构, 栈顶指针
// 返回值: 栈顶指针
int popElem(int* arr, int top);
三.链栈
一般将链表的头部作为栈顶
入栈:
// **添加元素
// 参数: 头指针,数据
// 返回值: 头指针
Node* pushElement(Node* stack, int Data)
// 1 申请内存
Node* NewNode = (Node*)malloc(sizeof(Node));
// 2 初始化节点
NewNode->data = Data;
// 3 新的节点作为新的头节点
NewNode->pnext = stack;
// 4 头指针指向新的头节点
stack = NewNode;
// 5 返回头指针
return stack;
出栈:
// **删除元素
// 参数: 头指针
// 返回值: 头指针
Node* popElement(Node* stack)
// 1 判断是否为空栈
if (stack)
// 临时指针 保存栈顶(头指针)
Node* p = stack;
// 头指针后移
stack = stack->pnext; // 与顺序栈一样,无需清除,在添加新元素的时候将它替换
// 打印数据
printf("原来栈顶元素:%d ",p->data);
// 再次判断是否到了栈顶底部
if (stack)
printf("当前栈顶元素:%d\\n",stack->data);
else
printf("栈顶已经空了!\\n");
// 释放节点
free(p);
else
printf("是一个空栈!\\n");
return stack;
完整代码+效果展示
#include<stdio.h>
#include<stdlib.h>
// 节点
typedef struct Node
int data;
struct Node* pnext;
Node;
// **添加元素
// 参数: 头指针,数据
// 返回值: 头指针
Node* pushElement(Node* stack, int Data)
// 1 申请内存
Node* NewNode = (Node*)malloc(sizeof(Node));
// 2 初始化节点
NewNode->data = Data;
// 3 新的节点作为新的头节点
NewNode->pnext = stack;
// 4 头指针指向新的头节点
stack = NewNode;
// 5 返回头指针
return stack;
// **删除元素
// 参数: 头指针
// 返回值: 头指针
Node* popElement(Node* stack)
// 1 判断是否为空栈
if (stack)
// 临时指针 保存栈顶(头指针)
Node* p = stack;
// 头指针后移
stack = stack->pnext; // 与顺序栈一样,无需清除,在添加新元素的时候将它替换
// 打印数据
printf("原来栈顶元素:%d ",p->data);
// 再次判断是否到了栈顶底部
if (stack)
printf("当前栈顶元素:%d\\n",stack->data);
else
printf("栈顶已经空了!\\n");
// 释放节点
free(p);
else
printf("是一个空栈!\\n");
return stack;
int main()
Node* p = NULL;
// 入栈
for (int i = 0; i < 10; i++)
p = pushElement(p, i);
// 出栈
for (int i = 0; i < 11; i++)
p = popElement(p);
Node* pushElement(Node* stack, int data);
Node* popElement(Node* stack);
栈!\\n");
return stack;
int main()
Node* p = NULL;
// 入栈
for (int i = 0; i < 10; i++)
p = pushElement(p, i);
// 出栈
for (int i = 0; i < 11; i++)
p = popElement(p);
Node* pushElement(Node* stack, int data);
Node* popElement(Node* stack);
线性表之栈(代码片段)
栈的定义： 一种只能在一端进行插入或删除操作的线性表被称为栈，其中允许删除或插入的一端为栈顶，另一端为栈底，栈底固定不变； 栈的特点：先进后出，例如弹夹，先装的子弹最后才能出； 按照存储结构可以... 查看详情
线性表--单调栈(代码片段)
目录前言一、单调栈简介1.1单调递增栈1.2单调递减栈二、单调栈适用场景2.1寻找左侧第一个比当前元素大的元素2.2寻找左侧第一个比当前元素小的元素2.3 寻找右侧第一个比当前元素大的元素2.4 寻找右侧第一个比当前元素小的... 查看详情
线性结构-栈(代码片段)
...方法栈的应用二.顺序栈三.链栈栈和队列栈和队列都属于线性表属于"一对一"逻辑关系栈:“先进后出”队列:“先进先出”一栈一.什么是栈看图理解(概念只是辅助理解_理解了才算学会)栈只能从一端存取,另一端是封闭的在... 查看详情
数据结构之线性表栈队列(代码片段)
温故而知新~~~~一、线性表顺序表实现（C++）1template<typenameE>2classAList34private:5intmaxSize;6intlistSize;7intcurr;8E*listArray;9public:10AList(intsize=defaultSize)1112maxSize=size;13listSize=curr=0;14listArr 查看详情
数据结构-栈(代码片段)
...与队列栈概念栈：是限定仅在表尾进行插入和删除操作的线性表。栈顶(top)：允许插入和删除的一端，即表尾称为栈顶栈底(bottom):表头称为栈底栈是LIFO结构，后进先出。与线性表相比，特殊之处在于限制了线性表的插入和删除位... 查看详情
数据结构--栈(代码片段)
一、什么是栈（Stack） 首先来说，栈是一种线性表的表现形式，其定义是只允许在栈顶进行插入或者删除的线性表，所以栈就有线性表的表现形式，链式栈和顺序栈。 栈顶（Top）：允许进行数据的插入... 查看详情
结构与算法-----栈2(代码片段)
...于存储数据的简单数据结构，类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允... 查看详情
数据结构---[栈（stack)](代码片段)
...现自定义栈的基本操作实现栈（stack）栈也是一种线性数据结构,只能从栈顶一段添加/取出元素;类似于单口试管;后进先出LastInFirstOut(LIFO)栈（stack）又名堆栈，它是一种运算受限的线性表.限定仅在表尾进行插入... 查看详情
3.基本数据结构-栈(代码片段)
一.线性数据结构 -我们从四个简单但重要的概念开始研究数据结构。栈，队列，deques（双向队列）,列表是一类数据的容器，它们数据元素之间的顺序由添加或删除的顺序决定。一旦一个数据元素被添加，它相对于前... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议... 查看详情
数据结构与算法--栈和队列(代码片段)
栈定义栈是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端有其特殊含义，称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈顶实现元素的进出，栈的修改遵循后进先出的原则。因此，栈又称为后进... 查看详情
大话数据结构栈与队列(代码片段)
栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LIFO结构。栈的插入操作，叫作进栈，也称压栈、... 查看详情
数据结构-栈(代码片段)
...基本的数据结构基本概念栈(Stack)：具有一定操作约束的线性表。只在一端(栈顶，Top)做插入、删除操作插入数据：入栈(Push)删除数据：出栈(Pop)后入先出：LastInFirstOut(LIFO)抽象数据类型描述类型名称：栈数据对象集：一个有0个或... 查看详情
线性表栈队列和优先队列(代码片段)
为一个特定的任务选择最好的数据结构和算法是开发高性能软件的一个关键。 数据结构是以某种形式将数据组织在一起的集合（collection）。数据结构不仅存储数据，还支持访问和处理数据的操作。 在面向对象思想... 查看详情
王道数据结构与算法栈(代码片段)
✍、目录导图1、栈Stack线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。栈：栈是只允许在一端进行插入(进栈)或删除操作(出栈)的线性表1.1、栈的重要术语栈的... 查看详情
数据结构：栈（c语言描述）(代码片段)
...不是很多，主要就是先进后出这种思想。栈也是一种线性表，既然是线性表那么就有线性表的两 查看详情
3）数据结构之线性表（栈与队列）(代码片段)
目录栈与队列的本质栈的基本概念栈的物理结构栈的顺序存储结构（用数组实现）静态栈的实现： Stack.h中Test/c中Stack.c中输出结果动态栈的实现 Stac.h中Test.c中Stack.c中栈的链式存储结构（使用链表实现） Stack... 查看详情