线性结构-栈
栈和队列
栈和队列都属于线性表
属于"一对一"逻辑关系
栈:“先进后出”
队列:“先进先出”
一 栈
一.什么是栈
看图理解(概念只是辅助理解_理解了才算学会)
在这里插入图片描述
- 栈只能从一端存取,另一端是封闭的
- 在栈中,无论是存还是取,都必须遵循"先进后出原则" ==>栈是一种只能从表的一端存取数据,且遵循"先进后出"原则的线性存储结构 进栈和出栈 进栈:将数据存储到站里面 出栈:将数据从栈中间取出 栈的实现方法 栈:"特殊"的线性存储结构 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
// **元素入栈
// 参数: 存储结构, 栈顶指针, 数据
// 返回值: 栈顶指针(需要知道结束入栈之后栈顶的位置)
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
#include
// 节点
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);
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/03/02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
