数据结构：栈

栈的原理与应用

大家学习数据结构的目的是为了更好的处理和存储数据，对于顺序表而言改查比较容易，增删比较麻烦，对于链式表而言，增删比较简单，改查比较麻烦，所以每种数据结构都有不同的特点，用户需要选择合适的数据结构。

思考：数据结构中有一种结构称为栈，而linux内存中的栈空间就是基于此设计的，请问栈应该如何设计？

之前学习linux内存分区的时候，已经知道栈内存自顶向下进行递增，其实栈和顺序表以及链式表都一样，都属于线性结构，存储的数据的逻辑关系也是一对一的。

只不过栈是一种特殊的线性表，特殊在栈的一端是封闭的，数据的插入与删除只能在栈的另一端进行，也就是栈遵循“后进先出”的原则。也被成为“LIFO”结构，意思是“last input first output”。

栈（stack）,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈（PUSH）、出栈（POP）的说法。

栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新书开始取。

闭合的一端被称为栈底（Stack Bottom），允许数据的插入与删除的一端被称为栈顶（Stack Top），不包含任何元素的栈被称为空栈。

把数据插入到栈空间的动作被称为入栈或者压栈

从栈空间中删除数据的动作被称为出栈或者弹栈

由于栈也是一种线性结构，所以可以以数组或者链表作为基础，在此基础上实现栈的操作。

以数组作为基础实现栈空间（顺序栈）

数组在内存中占用一块连续的空间，也就是数组元素的内存地址是连续的。为了实现栈，一般是把数组头作为栈底，数组头部到数组尾部作为栈的增长方向，也就是用户只在数组尾部对数据进行插入和删除。

为了方便管理顺序栈所以需要构造管理顺序栈信息的结构体类型，用于记录重要参数，如下：

// 指的是顺序栈中的元素的数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造记录顺序栈SequenceStack各项参数（栈底地址+栈容量+栈顶元素的下标）的结构体
typedef struct SequenceStack
{
    DataType_t * Bottom;    // 记录栈底地址
    unsigned int Size;      // 记录栈容量
    int          Top;       // 记录栈顶元素的下标
}SeqStack_t;

创建一个空的顺序栈，并为记录顺序栈信息的结构体申请堆内存，并进行初始化即可！

// 创建顺序栈并对顺序栈进行初始化
SeqStack_t *SeqStack_Create(unsigned int size)
{
    // 1. 利用 calloc 为顺序栈的管理结构体申请一块堆内存
    SeqStack_t *Manager = (SeqStack_t *)calloc(1, sizeof(SeqStack_t));
    if (NULL == Manager)
    {
        perror("calloc memory for manager is failed");
        exit(-1); // 程序异常终止
    }

    // 2. 利用 calloc 为所有元素申请堆内存
    Manager->Bottom = (DataType_t *)calloc(size, sizeof(DataType_t));
    if (NULL == Manager->Bottom)
    {
        perror("calloc memory for Stack is failed");
        free(Manager);
        exit(-1); // 程序异常终止
    }

    // 3. 对管理顺序栈的结构体进行初始化（元素容量 + 最后元素下标）
    Manager->Size = size;  // 对顺序栈中的容量进行初始化
    Manager->Top = -1;     // 由于顺序栈为空，则栈顶元素的下标初值为-1

    return Manager;
}

根据栈的特性，把新元素从栈顶入栈，也就是从数组的尾部进行元素插入，操作如下：

// 入栈
bool SeqStack_Push(SeqStack_t *Manager, DataType_t Data)
{
    // 1. 判断顺序栈是否已满
    if (SeqStack_IsFull(Manager))
    {
        printf("SeqStack Full is Full!\n");
        return false;
    }

    // 2. 如果顺序栈有空闲空间，则把新元素添加到顺序栈的栈顶
    Manager->Bottom[++Manager->Top] = Data;

    return true;
}

根据栈的特性，把元素从栈顶出栈，也就是把元素从数组的尾部把元素删除，操作如下：

// 出栈
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
    DataType_t temp = 0;  // 用于存储出栈元素的值

    // 1. 判断顺序栈是否为空
    if (SeqStack_IsEmpty(Manager))
    {
        printf("SeqStack is Empty!\n");
        return temp; // 空栈返回默认值，需结合实际逻辑调整
    }

    // 2. 由于删除了一个元素，则需要让顺序栈的栈顶元素下标-1
    temp = Manager->Bottom[Manager->Top--];

    return temp;
}

对顺序栈中的元素进行遍历，只需要从顺序栈的栈底开始向栈顶进行遍历，操作如下：

// 遍历顺序栈的元素
void SeqStack_Print(SeqStack_t *Manager)
{
    for (int i = 0; i <= Manager->Top; ++i)
    {
        printf(" Stack Element[%d] = %d\n", i, Manager->Bottom[i]);
    }
}

以链表作为基础实现栈空间（链式栈）

如果打算实现链式栈，一般是以链表作为基础，一般是把链表头部作为栈顶，方便数据的插入和删除（头插+头删），链式栈相当于是一个单向不循环的链表。

答案：C 

A选项：6、5进栈，5出栈；4进栈，4出栈；3进栈，3出栈；6出栈；2进栈，1进栈，1出栈；2出栈。合法。 

B选项：6、5、4进栈，4出栈；5出栈；3进栈，3出栈；2进栈，1进栈，1出栈；2出栈；6出栈。合法。 

C选项：6、5、4、3进栈，3出栈；4出栈；6出栈（此时栈内有5 ，按规则6不能在5前出栈 ），不合法。 

D选项：6、5、4、3、2进栈，2出栈；3出栈；4出栈；1进栈，1出栈；5出栈；6出栈。合法。 所以选C。

要解决这个问题，我们需要根据栈“后进先出”的特点，分析以d开头的出栈序列的可能情况。 元素 `a, b, c, d, e` 依次进栈，要使出栈序列以 `d` 开头，那么 `d` 进栈后必须马上出栈（因为 `d` 是第 4 个进栈的元素，要让它第一个出栈，前面的 `a`、`b`、`c` 必须都在栈中）。此时栈内情况是：栈底到栈顶为 `a`、`b`、`c`、`d`（`d` 刚进栈就出栈 ），`d` 出栈后，栈内剩下 `a`、`b`、`c`，接下来要考虑 `c`、`b`、`a`、`e` 的出栈顺序。 `d` 出栈后，后续出栈顺序由剩下元素（`a`、`b`、`c` 在栈内，`e` 未进栈 ）决定，`e` 可以在任意时刻进栈再出栈，具体可能的序列为： - `d c b a e` - `d c b e a` - `d c e b a` - `d e c b a` 所以以 `d` 开头的出栈序列有 4 种，答案选 B 。

栈是后进先出结构，进栈序列为p₁,p₂,p₃,…,pₙ，出栈序列是1,2,3,…,n且p₃ = 1 。这意味着p₁、p₂、p₃进栈后，p₃（即 1）最先出栈，说明p₁、p₂都在栈中且在p₃之后入栈，所以p₁不可能是 2，选 C。

设计一个进制转换程序，使用顺序栈设计一个把十进制数转换为十六进制数的接口，实现当通过键盘输入一个非负的十进制数，可以在终端输出对应的十六进制数。

// 十进制转换为十六进制
void SeqStack_Dec2Hex(SeqStack_t *Manager, unsigned int Data)
{
    int remainder; // 用于存储求余之后的余数

    // 1. 循环对非负整数进行求余 Data % 16
    do
    {
        remainder = Data % 16;

        // 分析余数的范围 0~9  10~15 -->A~F
        if (remainder < 10)
        {
            SeqStack_Push(Manager, remainder + '0');
        }
        else
        {
            SeqStack_Push(Manager, remainder + 'A' - 10);
        }

        Data /= 16;
    } while (Data != 0);

    // 2. 把顺序栈中的元素依次出栈
    printf("0x");
    while (!SeqStack_IsEmpty(Manager))
    {
        printf("%c", SeqStack_Pop(Manager));
    }
    printf("\n");
}

通过键盘输入一个包括  '(' 和 ')' 的字符串string ，判断字符串是否有效。要求设计算法实现检查字符串是否有效，有效的字符串需满足以下条件：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

bool SeqStack_IsStringVaild(SeqStack_t *Manager, const char *Str)
{
    char *Pstr = Str; // 备份地址，防止地址丢失
    // 1.循环遍历字符串，寻找'('
    while (*Pstr)
    {
        // 判断当前地址下的字符是否为'(', 如果是则入栈
        if (*Pstr == '(')
        {
            SeqStack_Push(Manager, '(');
        }
        if (*Pstr == ')')
        {
            // 判断空栈
            if (SeqStack_IsEmpty(Manager))
            {
                return false;
            }
            SeqStack_Pop(Manager);
        }

        Pstr++;
    }
    // 2.判断栈是否为空
    if (!SeqStack_IsEmpty(Manager))
    {
        return false;
    }

    return true;
}