12-数据结构_栈

た入场券 2021-12-13 01:17 191阅读 0赞

线性结构的常见应用之一 栈

# 一, 定义 #

一种可以实现"先进后出"的存储结构(存储方式)  
 只能在一端入和出

# 二, 分类 #

如图 06-静态栈-动态栈.jpg  
1, 静态栈  
底层 以 静态数组 实现  
2, 动态栈  
底层 以 链表 实现

![SouthEast][]

![SouthEast 1][]

![SouthEast 2][]

![SouthEast 3][]

# 三, 算法 #

## 1, 节点 Node, 栈 Stack ##

// 结点
    typedef struct Node
    {
        int data;
        struct Node * pNext;
    } NODE, * PNODE;
    
    // 栈
    typedef struct Stack
    {
        PNODE pTop;     // 栈顶
        PNODE pBottom;  // 栈底
    } STACK, * PSTACK;

## 2, 初始化 栈, 即造出空栈  ##

void initStack(PSTACK pStack)
    {   
        // "头结点"
        pStack->pBottom = (PNODE) malloc( sizeof(NODE) ); 
        checkMemoryAllocat(pStack->pBottom);
    
        pStack->pBottom->pNext = NULL;  // "头结点"指针域与空
    
        // 栈底指针 和 栈顶指针 都指向 "头结点"
        pStack->pTop = pStack->pBottom;
        return;
    }

## 3, 压栈 ##

// 压栈
    void push(PSTACK pStack, int value)
    {
        // 新结点
        PNODE pNew = (PNODE) malloc( sizeof(NODE) );
        checkMemoryAllocat(pNew);
        pNew->data = value;
    
        pNew->pNext = pStack->pTop; // 新结点的指针域 指向 栈顶
        pStack->pTop = pNew; // 栈顶 上移, 指向 新结点
    
        return;
    }

## 4, 弹栈, 出栈失败(空栈), pValue保存出栈的数据 ##

// 弹栈
    bool pop(PSTACK pStack, int * pValue)
    {   
        if ( isEmpty(pStack) )
        {
            return false;
        }    
        
        PNODE pTemp = pStack->pTop;     // 指向要删除的结点
    
    
        *pValue = pTemp->data;          // 记录删除结点的数据域
        
        pStack->pTop = pTemp->pNext;    // 栈顶指针 下移
        
        free(pTemp);    // 释放删除的结点
        pTemp = NULL;
    
    
        return true;
    }

## 5, 遍历 ##

// 遍历
    void traverse(PSTACK pStack)
    {
        printf("遍历-由顶到底:\n");
        PNODE p = pStack->pTop;
    
        for (; p != pStack->pBottom; p = p->pNext)
        {
            printf("%3d\n", p->data);
        }
    
        return;
    }

## 6, 检查动态内存是否分配失败, 是则终止 ##

void checkMemoryAllocat(PNODE pNode)
    {
        if (NULL == pNode)
        {
            printf("动态内存分配失败,结束程序!");
            exit(-1);
        }
    }

## 7, 栈是否为空 ##

// 栈是否为空
    bool isEmpty(PSTACK pStack)
    {   
        if (pStack->pTop == pStack->pBottom)
        {
            return true;
        }
        return false;
    }

## 8, 清空, 删除所有有效数据 ##

// 清空, 删除所有有效数据, 先下移栈顶, 后释放
    void clear(PSTACK pStack)
    {
        PNODE pTemp = pStack->pTop; // 用于指向要释放的 结点
    
        // 释放所有 有效结点
        while (pStack->pTop != pStack->pBottom)
        {
            pTemp = pStack->pTop;
            pStack->pTop = pTemp->pNext;    // 栈顶下移
            // 释放 刚才出栈的结点的内存
            free(pTemp);
            pTemp = NULL;
        }
    
       return;
    }

## 9, 完整代码 ##

#include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    // 结点
    typedef struct Node
    {
        int data;
        struct Node * pNext;
    } NODE, * PNODE;
    
    // 栈
    typedef struct Stack
    {
        PNODE pTop;     // 栈顶
        PNODE pBottom;  // 栈底
    } STACK, * PSTACK;
    
    // 初始化 栈, 即造出空栈
    void initStack(PSTACK pStack);
    // 压栈
    void push(PSTACK pStack, int value);
    // 弹栈, 出栈失败(空栈), pValue保存出栈的数据
    bool pop(PSTACK pStack, int * pValue);
    // 遍历
    void traverse(PSTACK pStack);
    // 检查动态内存是否分配失败, 是则终止
    void checkMemoryAllocat(PNODE pNode);
    // 栈是否为空
    bool isEmpty(PSTACK pStack);
    // 清空, 删除所有有效数据
    void clear(PSTACK pStack);
    
    int main(void)
    {
        STACK stack;
    
        // 初始化 栈
        initStack( &stack );
    
        // 压栈
        push(&stack, 1);
        push(&stack, 2);
        push(&stack, 3);
        push(&stack, 4);
    
        // 遍历
        traverse(&stack);
    
        // 弹栈
        int value;
        int i, count;
        printf("请输入要出栈的元素个数 : ");
        scanf("%d", &count);
        for (i = 0; i < count; ++i)
        {
            if (pop(&stack, &value))
            {            
                printf("出栈: %3d\n", value);
                continue;
            }
            printf("已到栈底, 出栈失败!!!\n");
        }
       
        // 遍历
        traverse(&stack);
    
        // 清空
        clear(&stack);
        traverse(&stack);
    
    
        return 0;
    }
    
    void initStack(PSTACK pStack)
    {   
        // "头结点"
        pStack->pBottom = (PNODE) malloc( sizeof(NODE) ); 
        checkMemoryAllocat(pStack->pBottom);
    
        pStack->pBottom->pNext = NULL;  // "头结点"指针域与空
    
        // 栈底指针 和 栈顶指针 都指向 "头结点"
        pStack->pTop = pStack->pBottom;
        return;
    }
    
    // 压栈
    void push(PSTACK pStack, int value)
    {
        // 新结点
        PNODE pNew = (PNODE) malloc( sizeof(NODE) );
        checkMemoryAllocat(pNew);
        pNew->data = value;
    
        pNew->pNext = pStack->pTop; // 新结点的指针域 指向 栈顶
        pStack->pTop = pNew; // 栈顶 上移, 指向 新结点
    
        return;
    }
    
    // 遍历
    void traverse(PSTACK pStack)
    {
        printf("遍历-由顶到底:\n");
        PNODE p = pStack->pTop;
    
        for (; p != pStack->pBottom; p = p->pNext)
        {
            printf("%3d\n", p->data);
        }
    
        return;
    }
    
    // 弹栈
    bool pop(PSTACK pStack, int * pValue)
    {   
        if ( isEmpty(pStack) )
        {
            return false;
        }    
        
        PNODE pTemp = pStack->pTop;     // 指向要删除的结点
    
        *pValue = pTemp->data;          // 记录删除结点的数据域
        
        pStack->pTop = pTemp->pNext;    // 栈顶指针 下移
        
        free(pTemp);    // 释放删除的结点
        pTemp = NULL;
    
        return true;
    }
    
    void checkMemoryAllocat(PNODE pNode)
    {
        if (NULL == pNode)
        {
            printf("动态内存分配失败,结束程序!");
            exit(-1);
        }
    }
    
    // 栈是否为空
    bool isEmpty(PSTACK pStack)
    {   
        if (pStack->pTop == pStack->pBottom)
        {
            return true;
        }
        return false;
    }
    
    // 清空, 删除所有有效数据, 先下移栈顶, 后释放
    void clear(PSTACK pStack)
    {
        PNODE pTemp = pStack->pTop; // 用于指向要释放的 结点
    
        // 释放所有 有效结点
        while (pStack->pTop != pStack->pBottom)
        {
            pTemp = pStack->pTop;
            pStack->pTop = pTemp->pNext;    // 栈顶下移
            // 释放 刚才出栈的结点的内存
            free(pTemp);
            pTemp = NULL;
        }
    
       return;
    }

# 四, 应用 #

1, 函数调用  
2, 中断  
3, 表达式求值(操作数栈, 操作符栈)  
4, 内存分配  
5, 缓冲处理  
6, 迷宫

[SouthEast]: /images/20211210/d5361964f9af49ebbb179b3edd25cf9e.png
[SouthEast 1]: /images/20211210/3d32096887be4341be54822568dbcda1.png
[SouthEast 2]: /images/20211210/74d3a8d6fca44a62a20a76f87da31e37.png
[SouthEast 3]: /images/20211210/4b2adfac218646f9a834b5dab48d0c3f.png