当前位置： 首页 > news >正文

【数据结构】栈（stack）

news 来源：原创 2024/4/28 13:39:17

栈的基本概念

  • 概念

栈是一个线性表，栈元素具有线性关系，即前驱后继关系，但是是一种特殊的线性表，在线性表的表尾进行插入和删除操作，表尾是指栈顶，表头是指栈底。

  • 特性

先进后出的规则

始终只进行栈顶操作，想访问栈底数据，就需要将上面数据一个一个出栈

栈的顺序存储

  • 基本概念

栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top （只是栈顶元素在顺序表的位置）

顺序存储栈栈

  • 框架及函数声明
#ifndef SEQSTACK_H
#define SEQSTACK_H

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// 数组模拟栈的顺序存储
#define MAX_SIZE 1024
#define SEQSTACK_TURE 1
#define SEQSTACK_FALSE 0

typedef struct SEQSTACK { 
    void* data[MAX_SIZE];
    int size;
}SeqStack;

// 初始化栈
SeqStack* Init_Stack();

// 入栈
void Push_Stack(SeqStack* stack, void* data);

// 返回栈顶元素
void* Top_Stack(SeqStack* stack);

// 出栈
void Pop_Stack(SeqStack* stack);

// 判断是否为空
int IsEmpty_Stack(SeqStack* stack);

//  返回栈中元素个数
int Size_Stack(SeqStack* stack);

// 清空栈
void Clear_Stack(SeqStack* stack);

// 销毁
void FreeSpace_Stack(SeqStack* stack);

#endif
  • 函数实现
#include"SeqStack.h"

// 初始化栈
SeqStack* Init_Stack(){
    //(SeqStack*)Stack = (SeqStack*)malloc(sizeof(SeqStack));
    SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    for (int i = 0; i < MAX_SIZE; i++) {
        stack->data[i] = NULL;
    }
    stack->size = 0;
    return stack;
}

// 入栈
void Push_Stack(SeqStack* stack, void* data){
    if (stack->size == MAX_SIZE) return;
    if (stack == NULL) return;
    if (data == NULL)  return;

    stack->data[stack->size] = data;
    stack->size++;
}

// 返回栈顶元素
void* Top_Stack(SeqStack* stack){
    if (stack == NULL)    return NULL;
    if (stack->size == 0) return NULL;

    return stack->data[stack->size - 1];
}

// 出栈
void Pop_Stack(SeqStack* stack){
    if (stack == NULL)    return;
    if (stack->size == 0) return;

    stack->data[stack->size - 1] = NULL;
    stack->size--;
}

// 判断是否为空
int IsEmpty_Stack(SeqStack* stack){
    if (stack->data == NULL) return -1;
    if (stack->size == 0)    return SEQSTACK_TURE;
    return SEQSTACK_FALSE;
}

//  返回栈中元素个数
int Size_Stack(SeqStack* stack){
    if (stack == NULL) return 0;
    return stack->size;
}

// 清空栈
void Clear_Stack(SeqStack* stack){
    if (stack == NULL) return;
    for (int i = 0; i < stack->size; i++) {
        stack->data[i] = NULL;
    }
    stack->size = 0;
}

// 销毁
void FreeSpace_Stack(SeqStack* stack){
    if (stack == NULL) return;
    free(stack);
}
  • 测试代码
#include"SeqStack.h"

typedef struct PERSON {
    char name[64];
    int age;
}Person;

void test() {
    SeqStack* stack = Init_Stack();

    Person p1, p2, p3, p4, p5;
    strcpy(p1.name, "张三");
    strcpy(p2.name, "李四");
    strcpy(p3.name, "王五");
    strcpy(p4.name, "李华");
    strcpy(p5.name, "赵六");
    p1.age = 10;
    p2.age = 20;
    p3.age = 30;
    p4.age = 40;
    p5.age = 50;

    // 判断栈是否为空
    if (IsEmpty_Stack(stack)) printf("栈为空\n");
    else printf("栈非空\n");

    // 入栈
    Push_Stack(stack, (void*)&p1);
    Push_Stack(stack, (void*)&p2);
    Push_Stack(stack, (void*)&p3);
    Push_Stack(stack, (void*)&p4);
    Push_Stack(stack, (void*)&p5);

    // 判断栈是否为空
    if (IsEmpty_Stack(stack)) printf("栈为空\n");
    else printf("栈非空\n");

    while (Size_Stack(stack)) {
        // 访问栈顶元素
        Person* person = (Person*)Top_Stack(stack);
        printf("name: %s age: %d\n", person->name, person->age);
        Pop_Stack(stack);
    }

    FreeSpace_Stack(stack);
}

int main() {
    test();
    return 0;
}

运行结果：

链式存储的栈

  • 框架及函数声明
#ifndef LINKSTACK_H
#define LINKSTACK_H

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 结点
typedef struct STACKNODE {
    struct STACKNODE* next;
}StackNode;

// 链式 栈
typedef struct LINKSTACK {
    StackNode head;
    int size;
}LinkStack;

// 初始化
LinkStack* Init_Stack();

// 入栈
void Push_Stack(LinkStack* stack, StackNode* data);

// 出栈
void Pop_Stack(LinkStack* stack);

// 返回栈顶
StackNode* Top_Stack(LinkStack* stack);

// 返回栈中元素个数
int Size_Stack(LinkStack* stack);

// 清空栈
void Clear_Stack(LinkStack* stack);

// 释放栈
void Free_Stack(LinkStack* stack);

#endif // !LINKSTACK_H
  • 函数实现
#include "LinkStack.h"

// 初始化
LinkStack* Init_Stack() { 
    LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
    stack->head.next = NULL;
    stack->size = 0;
    return stack;
}

// 入栈
void Push_Stack(LinkStack* stack, StackNode* data) { 
    if (stack == NULL) return;
    if (data  == NULL) return;

    data->next = stack->head.next;
    stack->head.next = data;
    stack->size++;
}

// 出栈
void Pop_Stack(LinkStack* stack) {
    if (stack == NULL) return;
    if (stack->size == 0) return;

    // 第一个有效结点
    StackNode* pNext = stack->head.next;
    stack->head.next = pNext->next;

    stack->size--;
}

// 返回栈顶
StackNode* Top_Stack(LinkStack* stack) { 
    if (stack == NULL) return NULL;
    if (stack->size == 0) return NULL;

    return stack->head.next;
}

// 返回栈元素个数
int Size_Stack(LinkStack* stack) {
    if (stack == NULL) return 0;
    return stack->size;
}

// 清空栈
void Clear_Stack(LinkStack* stack) { 
    if (stack == NULL) return;

    stack->head.next = NULL;
    stack->size = 0;
}

// 释放栈
void Free_Stack(LinkStack* stack) {
    if (stack == NULL) return;
    
    free(stack);
}
  • 测试代码
#include "LinkStack.h"

typedef struct PERSON {
    StackNode node;
    char name[64];
    int age;
}Person;

void test() {
    // 创建栈
    LinkStack* stack = Init_Stack();

    // 创建数据
    Person p1, p2, p3, p4, p5;
    strcpy(p1.name, "aaa");
    strcpy(p2.name, "bbb");
    strcpy(p3.name, "ccc");
    strcpy(p4.name, "ddd");
    strcpy(p5.name, "eee");
    p1.age = 10;
    p2.age = 20;
    p3.age = 30;
    p4.age = 40;
    p5.age = 50;

    // 入栈
    Push_Stack(stack, (StackNode*)&p1);
    Push_Stack(stack, (StackNode*)&p2);
    Push_Stack(stack, (StackNode*)&p3);
    Push_Stack(stack, (StackNode*)&p4);
    Push_Stack(stack, (StackNode*)&p5);

    // 返回栈中元素个数
    printf("栈中元素个数: %d\n", Size_Stack(stack));

    // 出栈
    while (Size_Stack(stack) > 0) {
        Person* p = (Person*)Top_Stack(stack); // 返回栈顶
        printf("name: %s age: %d\n", p->name, p->age);
        Pop_Stack(stack); // 弹出栈顶
    }
    Free_Stack(stack);
}

int main() {
    test();
    return 0;
}

运行结果：

栈的应用

就近匹配

匹配左右括号，找到字符串中不匹配的位置

  • 框架及函数声明
#ifndef LINKSTACK_H
#define LINKSTACK_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 结点
typedef struct STACKNODE {
    struct STACKNODE* next;
}StackNode;

// 链式栈
typedef struct LINKSTACK {
    StackNode head;
    int size;
}LinkStack;

// 初始化栈
LinkStack* Init_Stack();

// 入栈
void Push_Stack(LinkStack* stack, StackNode* data);

// 出栈
void Pop_Stack(LinkStack* stack);

// 获取栈顶
StackNode* Top_Stack(LinkStack* stack);

// 返回栈元素个数
int Size_Stack(LinkStack* stack);

// 清空栈
void Clear_Stack(LinkStack* stack);

// 释放栈
void Free_Stack(LinkStack* stack);

#endif // !LINKSTACK_H
  • 函数实现
#include "LinkStack.h"

// 初始化栈
LinkStack* Init_Stack() {
    LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
    stack->head.next = NULL;
    stack->size = 0;
    return stack;
}

// 入栈
void Push_Stack(LinkStack* stack, StackNode* data) { 
    if (stack == NULL) return;
    if (data == NULL)  return;

    data->next = stack->head.next;
    stack->head.next = data;
    stack->size++;
}

// 出栈
void Pop_Stack(LinkStack* stack) {
    if (stack == NULL) return;
    if (stack->size == 0) return;

    // 记录第一个有效的结点
    StackNode* pNext = stack->head.next;
    stack->head.next = pNext;
    stack->size--;
}

// 获取栈顶
StackNode* Top_Stack(LinkStack* stack) { 
    if (stack == NULL) return NULL;

    return stack->head.next;
}

// 返回栈元素个数
int Size_Stack(LinkStack* stack) {
    if (stack == NULL) return 0;
    return stack->size;
}

// 清空栈
void Clear_Stack(LinkStack* stack) {
    if (stack == NULL) return;
    stack->size = 0;
}

// 释放栈
void Free_Stack(LinkStack* stack) {
    if (stack == NULL) return;
    free(stack);
}
  • 测试代码
#include "LinkStack.h"

typedef struct MyChar {
    StackNode node;
    char* str;
    int index;
}MyChar;

int IsLeft(char c) {
    return c == '(';
}

int IsRight(char c) {
    return c == ')';
}

void ShowError(char* str, int pos) {
    printf("%s\n", str);
    for (int i = 0; i < pos; i++) {
        printf(" ");
    }
    printf("A\n");
}

void test() {
    char* str = "((1+2)+)()(())";
    char* p = str;
    
    int index = 0;
    // 创建栈
    LinkStack* stack = Init_Stack();
    while (*p != '\0') {
        // 左括号 ( 进栈
        if (IsLeft(*p)) {
            // 创建字符数据
            MyChar* mychar = (MyChar*)malloc(sizeof(MyChar));
            mychar->str = p;
            mychar->index = index;
            Push_Stack(stack, (StackNode*)mychar);
            free(mychar);
        }
        // 右括号 ) 出栈
        if (IsRight(*p)) {
            // 栈内要有括号
            if (Size_Stack(stack) > 0) {
                Pop_Stack(stack); // 弹出栈顶元素
            }
            else {
                printf("右括号没有匹配的左括号\n");
                ShowError(str, index);
                break;
            }
        }
        p++;
        index++;
    }
    if (Size_Stack(stack) > 0) {
        MyChar* mychar = (MyChar*)Top_Stack(stack);
        printf("左括号没有匹配的右括号\n");
        ShowError(str, (mychar->index) - Size_Stack(stack) + 1);
        Pop_Stack(stack);
        free(mychar);
    }
    else {
        printf("括号匹配成功\n");
    }
    Free_Stack(stack);
}

int main() {
    test();
    return 0;
}

运行结果：

中缀表达式

后缀表达式与中缀表达式

  • 将运算符放在数字后面叫后缀表达式 ---> 符合及计算机运算
  • 平时所写的数学表达式叫中缀表达式 ---> 符合直观思维逻辑

实例（中缀表达式 转化为 后缀表达式）

  • 1 + 2      --->  1 2 +
  • 1 + 2 * 3 --->  1 2 3 * +

中缀表达式算法

遍历中缀表达式中所有的数字和符号

  • 对于数字：直接输出
  • 对于符号：
  1. 左括号：直接进栈
  2. 运算符号：与栈顶符号进行优先级比较        
    • 该符号优先级高：该运算符入栈（默认栈顶为左括号，左括号优先级最低）
    • 该符号优先级不高：将栈顶符号弹出并输出（直到满足条件1），之后该符号进栈
  • 对于右括号：将栈顶符号弹出并输出，直到匹配左括号

遍历结束：将栈中的所有符号弹出并输出                        

  • 代码示例
#include "LinkStack.h"

typedef struct Mychar {
    StackNode node;
    char* str;
}MyChar;

// 创建 MyChar
MyChar* CreateMyChar(char* p) {
    MyChar* mychar = (MyChar*)malloc(sizeof(MyChar));
    if (mychar != NULL) {
        mychar->str = p;
        return mychar;
    }
    else return NULL;
}

// 数字
int Is_Number(char c) {
    return (c >= '0' && c <= '9');
}

// 数字操作
void Number_Operate(char* p) {
    printf("%c", *p);
}

// 左括号
int Is_Left(char c) {
    return (c == '(');
}

// 左括号操作
void Left_Operate(LinkStack* stack, char* p) {
    // 进栈
    Push_Stack(stack, (StackNode*)CreateMyChar(p));
}

// 右括号
int Is_Right(char c) {
    return (c == ')');
}

// 右括号操作
void Right_Operate(LinkStack* stack) {
    // 先判断栈中有没有元素
    while (Size_Stack(stack) > 0) {
        MyChar* mychar = (MyChar*)Top_Stack(stack);
        // 匹配到左括号
        if (Is_Left(*(mychar->str))) {
            // 左括号出栈
            Pop_Stack(stack);
            // 结束
            break;
        }
        // 输出
        printf("%c", *(mychar->str));
        // 弹出
        Pop_Stack(stack);
    }
}


// 运算符
int Is_Opertaor(char c) {
    return (c == '+' || c == '-' ||
        c == '*' || c == '/');
}

// 返回运算符优先级
int GetPriority(char c) {

    if (c == '*' || c == '/') {
        return 2;
    }
    if (c == '+' || c == '-') {
        return 1;
    }
    return 0;
}

// 运算符操作
void Operator_Operate(LinkStack* stack, char* p) {
    // 取出栈顶符号
    MyChar* mychar = (MyChar*)Top_Stack(stack);
    // 栈顶没有符号，该符号入栈
    if (mychar == NULL) {
        Push_Stack(stack, (StackNode*)CreateMyChar(p));
        return;
    }

    // 栈顶优先级低于当前符号优先级，该符号入栈
    if (GetPriority(*(mychar->str)) < GetPriority(*p)) {
        Push_Stack(stack, (StackNode*)CreateMyChar(p));
        return;
    }

    // 栈顶优先级不低于当前符号优先级
    else {
        while (Size_Stack(stack) > 0) {

            MyChar* mychar2 = (MyChar*)Top_Stack(stack);

            // 直到栈顶符号优先级低于该符号，该符号入栈
            if (GetPriority(*(mychar2->str)) < GetPriority(*p)) {
                Push_Stack(stack, (StackNode*)CreateMyChar(p));
                break;
            }
            printf("%c", *(mychar2->str));
            Pop_Stack(stack);
        }
    }
}

// 弹出剩余的符号
void Left_Over_Stack(LinkStack* stack) {
    while (Size_Stack(stack) > 0) {
        MyChar* mychar = (MyChar*)Top_Stack(stack);
        printf("%c", *(mychar->str));
        Pop_Stack(stack);
    }
}

void test() {
    char* str = "3+(2-1)*5/6";
    char* p = str;

    LinkStack* stack = Init_Stack();

    while (*p != '\0') {

        // 数字(输出)
        if (Is_Number(*p)) {
            Number_Operate(p);
        }

        // 左括号(入栈)
        if (Is_Left(*p)) {
            Left_Operate(stack, p);
        }

        // 右括号(出栈直到左括号)
        if (Is_Right(*p)) {
            Right_Operate(stack);
        }

        // 运算符(与栈顶比较)
        if (Is_Opertaor(*p)) {
            Operator_Operate(stack, p);
        }

        p++; // 字符指针移动
    }

    // 循环结束直接弹出所有符号
    while (Size_Stack(stack) > 0) {
        MyChar* mychar = (MyChar*)Top_Stack(stack);
        printf("%c", *(mychar->str));
        Pop_Stack(stack);
    }
    // 释放栈
    FreeStack(stack);
}

int main() {
    test();
    return 0;
}

运行结果：

后缀表达式计算

后缀转中缀

遍历后缀表达式中的数字和符号

  • 对于数字：进栈
  • 对于符号：
    • 从栈中弹出右操作数
    • 从栈中弹出左操作数
    • 根据符号进行运算
    • 将运算结果压入栈中

结束遍历：栈中的唯一数字为计算结果

图方便直接C++的 stack 和 list 

#include <iostream>
#include <stack>
#include <list>
#include <string>

using namespace std;

int isNumber(char c) {
    return (c >= '0' && c <= '9');
}

int isOperate(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

int priorityOperate(char c) {
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    return 0;
}

int isLeft(char c) {
    return (c == '(');
}

int isRight(char c) {
    return (c == ')');
}

void printList(const list<char>& clist) {
    for (list<char>::const_iterator it = clist.begin(); it != clist.end(); it++) {
        cout << *it;
    }
    cout << endl;
}

int main() {
    char str[] = "3+(2-1)*5/6";
    char* p = str;

    list<char>cList;
    stack<char>cStack;

    while (*p != '\0') {
        // 数字
        if (isNumber(*p)) {
            cList.push_back(*p);
        }
        // 操作符
        if (isOperate(*p)) {
            if (cStack.size() == 0) {
                cStack.push(*p);
            }
            else {
                if (priorityOperate(*p) > priorityOperate(cStack.top())) {
                    cStack.push(*p);
                }
                else {
                    while (cStack.size() > 0) {
                        if (priorityOperate(*p) > priorityOperate(cStack.top())) {
                            cStack.push(*p);
                            break;
                        }
                        cList.push_back(cStack.top());
                        cStack.pop();
                    }
                }
            }            
        }
        // 左括号
        if (isLeft(*p)) {
            cStack.push(*p);
        }
        // 右括号
        if (isRight(*p)) {
            // 出栈直到遇到左括号
            while (cStack.size() > 0) {
                if (cStack.top() == '(') {
                    cStack.pop();
                    break;
                }
                cList.push_back(cStack.top());
                cStack.pop();
            }
        }

        p++;
    }
    while (cStack.size() > 0) {
        cList.push_back(cStack.top());
        cStack.pop();
    }
    printList(cList);

    // 波兰表达式处理完

    // 对 cList 中处理

    // 数字压栈
    // 运算符，将栈顶数字弹出，先弹出右操作数再弹出左操作数

    // 遍历
    for (list<char>::const_iterator cit = cList.begin(); cit != cList.end(); cit++) {
        if (isNumber(*cit)) {
            cStack.push(*cit);
        }
        else {
            char right = cStack.top();
            cStack.pop();
            char left = cStack.top();
            cStack.pop();
            switch (*cit) {
            case '+':
                cStack.push(left + right);
                break;
            case '-':
                cStack.push(left - right);
                break;
            case '*':
                cStack.push(left * right);
                break;
            case '/':
                cStack.push(left / right);
                break;
            default:
                break;
            }
        }
    }
    if (cStack.size() == 1) {
        printf("ret = %c", cStack.top());
        cStack.pop();
    }
    else {
        printf("error");
        printf("%zu", cStack.size());
    }
    system("pause");
    return 0;
}

相关文章：

  • 【MyBatis笔记09】MyBatis中常用的几个动态SQL标签
  • Apache Geode＜1.15.0 不受信任的反序列化漏洞
  • GitLab 中 GitHub 导入 API 存在远程代码执行漏洞
  • 什么是生成器 — 一篇文章让你看懂
  • 国内近五年人工智能教育的研究热点及趋势——基于多维尺度和社会网络分析的方法
  • QGraphicsItem鼠标拖动旋转（五）
  • win7连接打印机0x0000011b错误的解决办法
  • 四、RocketMq本地集群搭建：多master-slaver异步
  • pcan二次开发文档 | PEAK-System Documentation
  • R语言数据分组聚合实战：使用aggregate函数对mtcars数据通过两个分类变量进行数据分组聚合、并计算分组的均值、使用na.rm删除异常值
  • Chapter15 : Artificial Intelligence in Compound Design
  • 前端HTML5 +CSS3 1. 基础认知
  • R语言替换字符串中指定字符的子串：sub函数查找字符串中第一个匹配到的子串并替换、如果要删除指定字符串子串则将替换的子符串设置为空字符串
  • java计算机毕业设计基于springboo大学生社团管理系统 vue+elementui
  • un9.2:创建springboot的两种方式。
  • JavaScript-如何实现克隆(clone)函数
  • [译]CSS 居中（Center）方法大合集
  • 【翻译】babel对TC39装饰器草案的实现
  • 10个确保微服务与容器安全的最佳实践
  • 2017-09-12 前端日报
  • Babel配置的不完全指南
  • CSS选择器——伪元素选择器之处理父元素高度及外边距溢出
  • Next.js之基础概念（二）
  • nodejs实现webservice问题总结
  • PAT A1017 优先队列
  • Promise面试题，控制异步流程
  • Spark VS Hadoop：两大大数据分析系统深度解读
  • supervisor 永不挂掉的进程 安装以及使用
  • 普通函数和构造函数的区别
  • 如何解决微信端直接跳WAP端
  • 深入浅出Node.js
  • 微信小程序开发问题汇总
  • # C++之functional库用法整理
  • #162 (Div. 2)
  • #define MODIFY_REG(REG, CLEARMASK, SETMASK)
  • #Linux（Source Insight安装及工程建立）
  • ()、[]、{}、(())、[[]]等各种括号的使用
  • （30）数组元素和与数字和的绝对差
  • （C语言）编写程序将一个4×4的数组进行顺时针旋转90度后输出。
  • （react踩过的坑）antd 如何同时获取一个select 的value和 label值
  • （附源码）spring boot校园健康监测管理系统 毕业设计 151047
  • （附源码）springboot猪场管理系统 毕业设计 160901
  • （已解决）报错：Could not load the Qt platform plugin “xcb“
  • (译) 函数式 JS #1：简介
  • （转）利用PHP的debug_backtrace函数，实现PHP文件权限管理、动态加载 【反射】...
  • （转）总结使用Unity 3D优化游戏运行性能的经验
  • (转载)hibernate缓存
  • .bat批处理（七）：PC端从手机内复制文件到本地
  • .cn根服务器被攻击之后
  • .net websocket 获取http登录的用户_如何解密浏览器的登录密码？获取浏览器内用户信息？...
  • .NET 药厂业务系统 CPU爆高分析
  • .NET/C# 避免调试器不小心提前计算本应延迟计算的值
  • .NET/C# 中设置当发生某个特定异常时进入断点（不借助 Visual Studio 的纯代码实现）
  • .Net面试题4
  • .net中调用windows performance记录性能信息