【C/C++】C语言实现顺序栈

C语言实现C语言实现顺序栈

简单描述
代码
运行结果

简单描述

用codeblocks编译通过
源码参考连接

https://gitee.com/IUuaena/data-structures-c.git

代码

seq_stack.h

#ifndef SEQ_STACK_H_INCLUDED
#define SEQ_STACK_H_INCLUDED

#define STACK_INIT_CAPACITY 100   //!< 栈初始容量
#define STACK_INCREMENT 10        //!< 栈容量增量
#define STACK_ELEM int            //!< 栈结点类型

/*! @brief 函数返回值枚举 */
typedef enum Status
{
    OK, //!< 正确
    NON_ALLOCATED,  //!< 内存分配失败
    NON_EXISTENT,   //!< 不存在
    OVERFLOW,       //!< 溢出
    ERROR           //!< 其他错误
} status_t;

/*! @brief 顺序栈 */
typedef struct
{
    STACK_ELEM* elements;   //!< 栈元素数组
    STACK_ELEM* top;        //!< 栈顶指针
    int capacity;           //!< 容量
    int size;               //!< 栈当前长度
} seq_stack_t;

// 顺序栈初始化
status_t SeqStackInit(seq_stack_t* seq_stack); // 构造一个空栈S

// 顺序栈销毁
status_t SeqStackDestroy(seq_stack_t* seq_stack); // 销毁栈S, S不再存在

// 顺序栈清空
status_t SeqStackClear(seq_stack_t* seq_stack); // 把S置为空栈

// 顺序栈是否为空
status_t SeqStackIsEmpty(seq_stack_t seq_stack); // 若栈S为空栈, 则返回TRUE, 否则返回FALSE

// 顺序栈长度
int SeqStackSize(seq_stack_t seq_stack); // 返回S的元素个数, 即栈的长度

// 顺序栈取栈顶
status_t SeqStackTop(seq_stack_t seq_stack, STACK_ELEM* top_elem); //

// 顺序栈入栈
status_t SeqStackPush(seq_stack_t* seq_stack, STACK_ELEM elem);

// 顺序栈出栈
status_t SeqStackPop(seq_stack_t* seq_stack, STACK_ELEM *elem);

// 顺序栈打印
void SeqStackPrint(seq_stack_t *seq_stack);    // 打印队列


#endif // SEQ_STACK_H_INCLUDED

seq_stack.c

/*!
 * @file seq_stack.c
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief  栈 顺序栈
 * @version 1.0.0
 * @date 2022-07-10
 * @copyright Copyright (c) 2021
 *  CyberDash计算机考研
 */

#include <stdlib.h>
#include <stdio.h>
#include "seq_stack.h"


/*!
 * @brief **顺序栈初始化**
 * @param seq_stack 顺序栈(指针)
 * @return 执行结果
 * @note
 * 顺序栈初始化
 * ----------
 * ----------
 *
 * ----------
 *
 * top指向的地址并不存放栈元素, 是为了方便操作
 *
 * ----------
 * - 数组elements分配内存\n
 * &emsp; **if** 内存分配失败 :\n
 * &emsp;&emsp; 返回NON_ALLOCATED\n
 * - 栈属性初始化\n
 * &emsp; top指向elements数组首地址\n
 * &emsp; 设置栈容量\n
 * &emsp; 栈内元素数0个\n
 */
status_t SeqStackInit(seq_stack_t* seq_stack)
{

    // 为elements分配内存
    seq_stack->elements = (STACK_ELEM*)malloc(STACK_INIT_CAPACITY * sizeof(STACK_ELEM));
    if (!seq_stack->elements)    // if 内存分配失败
    {
        return NON_ALLOCATED;   // 返回NON_ALLOCATED
    }

    seq_stack->top = seq_stack->elements;       // top指向数组首地址
    seq_stack->capacity = STACK_INIT_CAPACITY;  // 栈容量
    seq_stack->size = 0;                        // 栈内元素数0个

    return OK;
}


/*!
 * @brief **顺序栈取栈顶**
 * @param seq_stack 顺序栈
 * @param top_elem 栈顶元素的保存变量(指针)
 * @return 执行结果
 * @note
 * 顺序栈取栈顶
 * ----------
 * ----------
 *
 * ----------
 *
 * 读操作, 栈顶并不出栈
 *
 * ----------
 * - 判断栈空\n
 * &emsp; **if** 栈空 :\n
 * &emsp;&emsp; 返回NON_EXISTENT\n
 * - 赋值\n
 * &emsp; 将*(seq_stack.top - 1)赋给*top_elem\n
 */
status_t SeqStackTop(seq_stack_t seq_stack, STACK_ELEM* top_elem)
{

    // ----- 判断栈空 -----
    if (seq_stack.top == seq_stack.elements)    // if 栈空
    {
        return NON_EXISTENT;    // 返回NON_EXISTENT
    }

    // ----- 赋值 -----
    *top_elem = *(seq_stack.top - 1);   // 将*(seq_stack.top - 1)赋给*top_elem

    return OK;
}


/*!
 * @brief **顺序栈入栈**
 * @param seq_stack 顺序栈(指针)
 * @param elem 入栈元素
 * @return 执行结果
 * @note
 * 顺序栈入栈
 * --------
 * --------
 *
 * --------
 * - 判断栈满\n
 * &emsp; **if** top - elements >= capacity :\n
 * &emsp;&emsp; elements重新分配内存\n
 * &emsp;&emsp; **if** 内存分配失败 :\n
 * &emsp;&emsp;&emsp; 返回NON_ALLOCATED\n
 * &emsp;&emsp; top指针重新指向最新的位置elements + capacity\n
 * &emsp;&emsp; capacity调整\n
 * - 栈属性调整\n
 * &emsp; 入栈元素赋给top指针指向的位置\n
 * &emsp; top指针向后移动一位\n
 * &emsp; 当前栈size增加1\n
 */
status_t SeqStackPush(seq_stack_t* seq_stack, STACK_ELEM elem)
{
    // 栈满, 扩充elements数组, todo: 这里的>=包含两种边界条件, 需要增加case处理
    if (seq_stack->top - seq_stack->elements >= seq_stack->capacity)
    {
        seq_stack->elements = (STACK_ELEM*)realloc(seq_stack->elements,
                              (seq_stack->capacity + STACK_INCREMENT) * sizeof(STACK_ELEM));
        if (!seq_stack->elements)
        {
            return NON_ALLOCATED;
        }

        // top指针重新指向新位置
        seq_stack->top = seq_stack->elements + seq_stack->capacity;
        // capacity调整
        seq_stack->capacity += STACK_INCREMENT;
    }

    *seq_stack->top = elem; // 入栈元素赋给top指针指向的位置
    seq_stack->top++;       // top指针向后移动一位
    seq_stack->size++;      // 当前栈size增加1

    return OK;
}


/*!
 * @brief **顺序栈出栈**
 * @param seq_stack 顺序栈(指针)
 * @param elem 栈顶元素
 * @return 执行结果
 * @note
 * 顺序栈出栈
 * --------
 * --------
 *
 * --------
 * - 判断栈空\n
 * &emsp; **if** 栈空 :\n
 * &emsp;&emsp; 返回NON_EXISTENT\n
 * - 栈顶赋给elem\n
 * - 栈属性调整\n
 * &emsp; top指针向前挪1位(减1)\n
 * &emsp; size减1\n
 */
status_t SeqStackPop(seq_stack_t* seq_stack, STACK_ELEM* elem)
{

    if (seq_stack->top == seq_stack->elements)
    {
        return NON_EXISTENT;
    }

    *elem = *seq_stack->top;

    seq_stack->top--;
    seq_stack->size--;

    return OK;
}


/*!
 * @brief **顺序栈销毁**
 * @param seq_stack 顺序栈
 * @return 执行结果
 * @note
 * 顺序栈销毁
 * ---------
 * ---------
 *
 * ---------
 * - free栈的elements\n
 * - free栈\n
 */
status_t SeqStackDestroy(seq_stack_t* seq_stack)
{
    free(seq_stack->elements);
    free(seq_stack);

    return OK;
}


/*!
 * @brief **顺序栈清空**
 * @param seq_stack 顺序栈
 * @return 执行结果
 * @note
 * 顺序栈清空
 * ---------
 * ---------
 *
 * ---------
 * **while loop** 栈不为空 :\n
 * &emsp; Pop栈顶\n
 */
status_t SeqStackClear(seq_stack_t* seq_stack)
{
    STACK_ELEM elem;
    while (SeqStackIsEmpty(*seq_stack) != OK)
    {
        SeqStackPop(seq_stack, &elem);
    }

    return OK;
}


/*!
 * @brief **顺序栈是否为空**
 * @param seq_stack 顺序栈
 * @return 执行结果
 * @note
 * 顺序栈是否为空
 * ------------
 * ------------
 *
 * ------------
 * **if** top等于elements :\n
 * &emsp; 返回OK\n
 * **else**\n
 * &emsp; 返回ERROR\n
 */
status_t SeqStackIsEmpty(seq_stack_t seq_stack)
{
    if (seq_stack.top == seq_stack.elements)
    {
        return OK;
    }

    return ERROR;   // todo: ERROR用的不好
}


/*!
 * @brief **顺序栈长度**
 * @param seq_stack 顺序栈
 * @return 长度
 * @note
 * 顺序栈长度
 * ---------
 * ---------
 *
 * ---------
 * 返回 top - elements
 */
int SeqStackSize(seq_stack_t seq_stack)
{
    return seq_stack.top - seq_stack.elements;
}


/*!
 * @brief **顺序栈打印**
 * @param seq_stack 顺序栈
 * @note
 * 顺序栈打印
 * ---------
 * ---------
 *
 * ---------
 * 遍历栈内元素, 打印
 */
void SeqStackPrint(seq_stack_t* seq_stack)
{

    STACK_ELEM* cur = seq_stack->top;

    printf("打印栈, 从栈顶到栈底\n");

    while (cur - seq_stack->elements > 0)
    {
        printf("%d ", *(cur - 1));
        cur--;
    }

    printf("\n");
}

main.c

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



#include "seq_stack.h"


/*!
 * @brief **测试顺序栈插入**
 * @note
 */
void TestSeqStackInsert()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                        Test Insert                        |\n");
    printf("|                          测试栈插入                         |\n");

    seq_stack_t *sqStack = (seq_stack_t*)malloc(sizeof(seq_stack_t));
    status_t res = SeqStackInit(sqStack);
    if (res != OK)
    {
        printf("初始化栈失败");
    }

    SeqStackPush(sqStack, 1);
    SeqStackPush(sqStack, 2);
    SeqStackPush(sqStack, 3);
    SeqStackPush(sqStack, 4);
    SeqStackPush(sqStack, 5);

    SeqStackPrint(sqStack);

    printf("|-----------------------------------------------------------|\n\n");
}


/*!
 * @brief **顺序栈清空**
 * @note
 */
void TestSeqStackClear()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                     Test SeqStackClear                    |\n");
    printf("|                          测试清除栈                         |\n");

    seq_stack_t sqStack;
    status_t res = SeqStackInit(&sqStack);
    if (res != OK)
    {
        printf("初始化栈失败");
    }

    SeqStackPush(&sqStack, 1);
    SeqStackPush(&sqStack, 2);
    SeqStackPush(&sqStack, 3);
    SeqStackPush(&sqStack, 4);
    SeqStackPush(&sqStack, 5);

    res = SeqStackClear(&sqStack);
    if (res == OK)
    {
        if (SeqStackIsEmpty(sqStack) == OK)
        {
            printf("清除栈成功\n");
        }
    }

    printf("|-----------------------------------------------------------|\n\n");
}


/*!
 * @brief **测试顺序栈长度**
 * @note
 */
void TestSeqStackLength()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                        Test Length                        |\n");
    printf("|                          测试栈长度                         |\n");

    seq_stack_t sqStack;
    status_t res = SeqStackInit(&sqStack);
    if (res != OK)
    {
        printf("初始化栈失败");
    }

    SeqStackPush(&sqStack, 1);
    SeqStackPush(&sqStack, 2);
    SeqStackPush(&sqStack, 3);
    SeqStackPush(&sqStack, 4);
    SeqStackPush(&sqStack, 5);

    printf("栈长度: %d\n", SeqStackSize(sqStack));

    printf("|-----------------------------------------------------------|\n\n");
}


/*!
 * @brief 测试顺序栈栈顶
 * @note
 */
void TestSeqStackTop()
{
    printf("\n");
    printf("|------------------------ CyberDash ------------------------|\n");
    printf("|                      Test SeqStackTop                     |\n");
    printf("|                         测试获取栈顶                        |\n");

    seq_stack_t sqStack;
    status_t res = SeqStackInit(&sqStack);
    if (res != OK)
    {
        printf("初始化栈失败");
    }

    STACK_ELEM top;

    SeqStackPush(&sqStack, 1);
    SeqStackPush(&sqStack, 2);
    SeqStackPush(&sqStack, 3);
    SeqStackPush(&sqStack, 4);
    SeqStackPush(&sqStack, 5);

    SeqStackTop(sqStack, &top);

    printf("栈顶: %d\n", top);

    printf("|-----------------------------------------------------------|\n\n");
}



int main()
{
    printf("顺序栈!\n");

    TestSeqStackInsert();

    TestSeqStackLength();

    TestSeqStackClear();

    TestSeqStackTop();
    return 0;
}

运行结果

顺序栈!

|------------------------ CyberDash ------------------------|
|                        Test Insert                        |
|                          测试栈插入                         |
打印栈, 从栈顶到栈底
5 4 3 2 1
|-----------------------------------------------------------|


|------------------------ CyberDash ------------------------|
|                        Test Length                        |
|                          测试栈长度                         |
栈长度: 5
|-----------------------------------------------------------|


|------------------------ CyberDash ------------------------|
|                     Test SeqStackClear                    |
|                          测试清除栈                         |
清除栈成功
|-----------------------------------------------------------|


|------------------------ CyberDash ------------------------|
|                      Test SeqStackTop                     |
|                         测试获取栈顶                        |
栈顶: 5
|-----------------------------------------------------------|


Process returned 0 (0x0)   execution time : 0.089 s
Press any key to continue.

Guistar~~

【C/C++】C语言实现顺序栈

C语言实现C语言实现顺序栈

简单描述

代码

运行结果