顺序栈算法库构建

学习贺利坚老师,顺序栈,构建顺序栈算法库

数据结构之自建算法库——顺序栈_设计一个主函数实现对顺序栈进行操作测试，测试方法，依次把元素-CSDN博客文章浏览阅读4.9k次，点赞10次，收藏10次。本文针对数据结构基础系列网络课程(2)：线性表中第3课时栈的顺序存储结构及其基本运算实现。按照“0207将算法变程序”[视频]部分建议的方法，建设自己的专业基础设施算法库。顺序栈算法库采用程序的多文件组织形式，包括两个文件： 　　 　　1.头文件：sqstack.h，包含定义顺序栈数据结构的代码、宏定义、要实现算法的函数的声明；#ifndef SQSTACK_H_INCLUDED#defi_设计一个主函数实现对顺序栈进行操作测试，测试方法，依次把元素https://blog.csdn.net/sxhelijian/article/details/48463527本人详细解析博客:

顺序栈文章浏览阅读4.1k次，点赞4次，收藏20次。栈和队列主要用于计算过程中保存的临时数据，如果数据在编程时就可以确定，那么使用几个变量就可以临时存储，但是如果存储的数据项数不能确定，就需要复杂的存储机制。这样的存储机制称为缓存。栈和队列就是使用最多的缓存结构。我们在调用方法的时候 , 时常调用别的成员方法, 递归循环调用 , 那调用到最后,又从最后一个函数,依次返回值 , 我们熟悉这个机制.但是我们却不知道 , 编译器是如何把这些调用信息存储起来的,用什么方法存储起来的, 这里就需要我们用到栈了,先进后出还有生活中 , 我们往木桶里放球 ,_栈的应用https://blog.csdn.net/qq_57484399/article/details/127185102版本更新日志:

v1.0: 完成基本功能

V1.0

功能函数:

//(1)初始化顺序栈
void Init_Sequential_stack(Sequential_stack *&s);
//(2)销毁顺序栈
void Destroy_Sequential_stack(Sequential_stack *&destroy_Stack);
//(3)输出展示顺序栈
void Display_Sequential_stack(Sequential_stack *show_Stack);
//(4) 将一个元素入栈
bool Push_Sequential_stack(Sequential_stack *&push_Stack, ElemType push_value);
//(5) 将一个元素出栈
bool Pop_Sequential_stack(Sequential_stack *&pop_Stack, ElemType &pop_value);
//(6)判断栈是否为空
bool Empty_Sequential_stack(Sequential_stack *judge_Stack);
//(7)求顺序栈中元素个数--栈长度
int Length_Sequential_stack(Sequential_stack *Quantity_length_Stack);
//(8) 访问获得栈顶元素
bool GetTop_Sequential_stack(Sequential_stack *visited_Stack, ElemType &get_value);

Sequential_stack.h

#ifndef SEQUENTIAL_STACK_H_INCLUDE
#define SEQUENTIAL_STACK_H_INCLUDE

#include "stdio.h"
#include <malloc.h>

#define MaxSize 100

typedef char ElemType;

typedef struct
{
    ElemType data[MaxSize]; //顺序栈用来存储数据的数组
    int top;            //定义栈顶指针

}Sequential_stack;  //顺序栈定义

//(1)初始化顺序栈
void Init_Sequential_stack(Sequential_stack *&s);
//(2)销毁顺序栈
void Destroy_Sequential_stack(Sequential_stack *&destroy_Stack);
//(3)输出展示顺序栈
void Display_Sequential_stack(Sequential_stack *show_Stack);
//(4) 将一个元素入栈
bool Push_Sequential_stack(Sequential_stack *&push_Stack, ElemType push_value);
//(5) 将一个元素出栈
bool Pop_Sequential_stack(Sequential_stack *&pop_Stack, ElemType &pop_value);
//(6)判断栈是否为空
bool Empty_Sequential_stack(Sequential_stack *judge_Stack);
//(7)求顺序栈中元素个数--栈长度
int Length_Sequential_stack(Sequential_stack *Quantity_length_Stack);
//(8) 访问获得栈顶元素
bool GetTop_Sequential_stack(Sequential_stack *visited_Stack, ElemType &get_value);

#endif // SEQUENTIAL_STACK_H_INCLUDE

Sequential_stack.cpp

#include "Sequential_stack.h"

/**************************************************
(1)函数名: Init_Sequential_stack
功  能: 初始化顺序栈
参  数: Sequential_stack *&init_Stack:要进行初始化的栈
返回值: 无
**************************************************/
void Init_Sequential_stack(Sequential_stack *&init_Stack)
{
      init_Stack = (Sequential_stack *)malloc(sizeof(Sequential_stack));
      init_Stack->top = -1;  //毕竟是数组, 栈顶指针序号具有权威,序号之上默认空(可替换)
}

/**************************************************
(2)函数名: Destroy_Sequential_stack
功  能: 销毁释放顺序栈空间
参  数: Sequential_stack *&destroy_Stack:要销毁的栈
返回值: 无
**************************************************/
void Destroy_Sequential_stack(Sequential_stack *&destroy_Stack)
{
    free(destroy_Stack);
}

/**************************************************
(3)函数名: Display_Sequential_stack
功  能: 输出展示栈内元素
参  数: Sequential_stack *show_Stack:要输出展示的栈
返回值: 无
**************************************************/
void Display_Sequential_stack(Sequential_stack *show_Stack)
{
    //从栈顶开始 , 从上往下,输出栈内元素
    int counter;
    printf("\n");
    for(counter = show_Stack->top; counter >= 0;  counter--)
    {
        printf("%c ",show_Stack->data[counter]);
    }
    printf("\n");
}
/**************************************************
(4)函数名: Push_Sequential_stack
功  能: 把一个元素,压入栈顶
参  数: (1)Sequential_stack *&push_Stack:要进行压入元素的顺序栈
        (2)ElemType push_value:要压入的元素值
返回值:bool: 是否压入成功? true(栈不满,压入成功):false(栈满压入失败)
**************************************************/

bool Push_Sequential_stack(Sequential_stack *&push_Stack, ElemType push_value)
{
    bool finished;
    if(push_Stack->top == MaxSize-1)
    {
        finished = false;
    }
    else
    {
        //栈不满代表可以入栈
        push_Stack->top++;
        push_Stack->data[push_Stack->top] = push_value;
        finished = true;
    }
    return finished;//单一出口
}

/**************************************************
(5)函数名: Pop_Sequential_stack
功  能: 出栈顶内元素
参  数: (1)Sequential_stack *&pop_Stack:要弹出栈顶元素的栈
        (2)ElemType &pop_value: 存储要弹出的栈顶元素的变量
返回值: bool:是否出栈成功? true(栈非空,出栈成功):false(栈空,失败)
**************************************************/
bool Pop_Sequential_stack(Sequential_stack *&pop_Stack, ElemType &pop_value)
{
    bool finished;//完成标志
    if(pop_Stack->top == -1)
    {
        finished = false;
    }
    else
    {
        //返回出栈元素
        pop_value = pop_Stack->data[pop_Stack->top];
        pop_Stack->top--;
        finished = true;
    }
    return finished;//单一出口
}

/**************************************************
(6)函数名: Empty_Sequential_stack
功  能: 判断顺序栈是否为空
参  数: Sequential_stack *judge_Stack:要进行判断的顺序栈
返回值: bool: 栈是否为空? true(栈为空):false(栈不空)
**************************************************/
bool Empty_Sequential_stack(Sequential_stack *judge_Stack)
{
    return (judge_Stack->top == -1);//true则空,false则非空
}

/**************************************************
(7)函数名: Length_Sequential_stack
功  能: 判断顺序栈栈内元素个数
参  数: Sequential_stack *Quantity_Stack:要进行判断元素个数的顺序栈
返回值: int: 栈内元素个数
**************************************************/
int Length_Sequential_stack(Sequential_stack *Quantity_Stack)
{
    return(Quantity_Stack->top+1);//数组--栈顶序号加一即为长度
}

/**************************************************
(8)函数名: GetTop_Sequential_stack
功  能: 得到栈顶元素值
参  数: (1)Sequential_stack *visited_Stack:要访问的顺序栈
        (2)ElemType &get_value:传回栈顶元素值
注  意:     ElemType &get_value:加地址符,需要传回数值
返回值: bool: 是否得到栈顶元素值? true(栈不空,得到栈顶元素):false(栈空)
**************************************************/
bool GetTop_Sequential_stack(Sequential_stack *visited_Stack, ElemType &get_value)
{
    bool finished;
    if(visited_Stack->top == -1)
    {
        finished = false;
    }
    else
    {
        get_value = visited_Stack->data[visited_Stack->top];//只访问
        finished = true;
    }
    return finished; //单一出口
}

main.cpp

#include <stdio.h>
#include "Sequential_stack.h"

int main()
{
    ElemType elem;
    Sequential_stack *test_stack;
    printf("\n(1)初始化栈test_stack\n");
    Init_Sequential_stack(test_stack);
    printf("\n(2)栈为%s\n",(Empty_Sequential_stack(test_stack)?"空":"非空"));
    printf("\n(3)依次进栈元素 a, b, c, d, e\n");
    Push_Sequential_stack(test_stack,'a');
    Push_Sequential_stack(test_stack,'b');
    Push_Sequential_stack(test_stack,'c');
    Push_Sequential_stack(test_stack,'d');
    Push_Sequential_stack(test_stack,'e');
    printf("\n(4)栈为%s\n",(Empty_Sequential_stack(test_stack)?"空":"非空"));
    printf("\n(5)栈的长度为:%d\n",Length_Sequential_stack(test_stack));
    printf("\n(6)从栈顶到栈底元素:\n");Display_Sequential_stack(test_stack);
    printf("\n(7)出栈序列:\n");
    while(!Empty_Sequential_stack(test_stack))
    {
        Pop_Sequential_stack(test_stack,elem);
        printf("\n%c\n",elem);
    }
    printf("\n(8)栈为%s\n",(Empty_Sequential_stack(test_stack)?"空":"非空"));
    printf("\n(9)释放栈\n");
    Destroy_Sequential_stack(test_stack);
    return 0;
}

运行结果演示: