栈

基本定义

栈是一种基本的数据结构，它遵循“先进后出”的原则，即最后压入栈的元素最先弹出。栈可以用数组或链表来实现，常见的栈操作包括：

1. 压栈（Push）：将一个元素放入栈顶，成为新的栈顶。

2. 弹栈（Pop）：将栈顶元素取出，并将其从栈中删除。

3. 获取栈顶元素（Top）：返回当前栈顶元素，但不删除它。

4. 判断栈是否为空（IsEmpty）：判断栈中是否有元素。

Stack Data Structure

栈可以由顺序和链式两种存储结构实现

顺序栈

采用顺序存储的栈称为顺序栈，利用一组地址连续的存储单元存放自栈底到栈顶的数据元素。设置一个栈顶指针top指示当前栈顶元素的位置。

/**
 * @file array_stack.cpp
 * @author icecreamovo (www.icecreamovo.top)
 * @brief 顺序栈：使用数组实现的栈
 * @version 0.1
 * @date 2023-04-23
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <bits/stdc++.h>
#define N 5
#define MAX_SIZE 5
using namespace std;
typedef struct
{
    int data[MAX_SIZE];
    int top; // 栈顶指针
} Stack;
void initStack(Stack *stack)
{
    stack->top = -1;
}
/**
 * 函数“push”将一个整数值添加到堆栈数据结构中，并打印一条消息指示操作是否成功。
 *
 * @param stack 指向 Stack 结构的指针，它包含一个整数数组和一个指示堆栈顶部索引的变量。
 * @param val val 是需要压入堆栈的整数值。
 *
 * @return 如果条件 `stack->top == MAX_SIZE - 1` 为真，函数返回而不将值压入堆栈。否则，该函数会将值压入堆栈并打印一条成功消息，但不会显式返回任何内容。
 */
void push(Stack *stack, int val)
{
    if (stack->top == MAX_SIZE - 1)
    {
        cout << "栈满，无法入栈" << endl;
        return;
    }
    stack->data[++(stack->top)] = val;
    cout << "入栈成功" << endl;
}
/**
 * 如果栈为空，则打印错误信息并返回-1；否则，返回栈顶元素并递减栈顶指针
 *
 * @param stack 要操作的栈
 *
 * @return 栈顶元素。
 */
int pop(Stack *stack)
{
    if (stack->top == -1)
    {
        cout << "栈空，无法出栈" << endl;
        return -1;
    }
    return stack->data[(stack->top)--];
}
/**
 * 如果栈顶等于-1，则栈为空
 *
 * @param stack 要检查的堆栈。
 *
 * @return 栈顶
 */
bool empty(Stack *stack)
{
    return stack->top == -1;
}
void destroy(Stack *stack)
{
    free(stack);
}
int main()
{
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    initStack(stack);
    for (int i = 0; i < 10; i++)
    {
        push(stack, i + 1);
    }
    while (!empty(stack))
    {
        cout << pop(stack) << endl;
    }
    destroy(stack);
    system("pause");
    return 0;
}

共享栈

如果利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间。将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

Shared-Stack Diagram

#include <bits/stdc++.h>
#define MAX_SIZE 100
using namespace std;
// 实现共享栈
/**
 * 定义了一个名为 ShareStack 的结构，它表示一个具有两个顶部的共享堆栈。
 * @property {int} data - 存储堆栈元素的整数数组。
 * @property {int} top1 - 共享堆栈实现中第一个堆栈的顶部索引。
 * @property {int} top2 - “ShareStack”结构中的“top2”属性是共享堆栈实现中第二个堆栈的顶部指针。
 * 在共享堆栈中，两个堆栈共享同一个底层数组，“top1”和“top2”指针跟踪每个堆栈的顶部元素
 */
typedef struct Stack
{
    int data[MAX_SIZE];
    int top1;
    int top2;
} ShareStack;

/**
 * 该函数通过将顶部指针设置为 -1 和 MAX_SIZE 来初始化共享堆栈。
 *
 * @param stack 指向 ShareStack 结构的指针，其中包含两个整数变量 top1 和 top2。
 */
void initStack(ShareStack *stack)
{
    stack->top1 = -1;
    stack->top2 = MAX_SIZE;
}

void push(ShareStack *stack, int val, int stackNumber)
{
    if (stack->top1 + 1 == stack->top2)
    {
        cout << "栈满，无法入栈" << endl;
        return;
    }
    if (stackNumber == 1)
    {
        stack->data[++stack->top1] = val;
    }
    else if (stackNumber == 2)
    {
        stack->data[--stack->top2] = val;
    }
    else
    {
        cout << "请输入正确的栈号" << endl;
    }
}

void pop(ShareStack *stack, int stackNumber)
{
    if (stackNumber == 1)
    {
        if (stack->top1 == -1)
        {
            cout << "栈1空，无法出栈" << endl;
            return;
        }
        cout << "栈1出栈元素：" << stack->data[stack->top1--] << endl;
    }
    else if (stackNumber == 2)
    {
        if (stack->top2 == MAX_SIZE)
        {
            cout << "栈2空，无法出栈" << endl;
            return;
        }
        cout << "栈2出栈元素：" << stack->data[stack->top2++] << endl;
    }
    else
    {
        cout << "请输入正确的栈号" << endl;
    }
}

int main()
{
    ShareStack *stack = (ShareStack *)malloc(sizeof(ShareStack));
    initStack(stack);
    for (int i = 0; i < 10; i++)
    {
        push(stack, i, 1);
    }
    for (int i = 0; i < 10; i++)
    {
        push(stack, i, 2);
    }
    for (int i = 0; i < 10; i++)
    {
        pop(stack, 1);
    }
    for (int i = 0; i < 10; i++)
    {
        pop(stack, 2);
    }
    system("pause");
    return 0;
}

链栈

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，并且不存在栈满上溢的情况。

/**
 * @file linked_stack_head.cpp
 * @author icecreamovo (www.icecreamovo.top)
 * @brief 带头结点的单链表实现的链栈
 * @version 0.1
 * @date 2023-04-23
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <bits/stdc++.h>
#define N 100
using namespace std;

/**
 * 上述类型定义了一个堆栈节点结构，其中包含整数数据和指向下一个节点的指针。
 * @property {int} data - 一个整型变量，存储栈中节点的数据。
 * @property next - “next”是指向链表中下一个节点的指针。在这种情况下，它指向堆栈中的下一个节点。
 */
typedef struct StackNode
{
    int data;
    struct StackNode *next;
} StackNode, LinkStack;

/**
 * 初始化堆栈。
 *
 * @param stack 要初始化的栈
 */
void initStack(LinkStack *stack)
{
    stack->next = NULL;
}

/**
 * 将值压入堆栈。
 *
 * @param stack 要压入的栈
 * @param val 要压入堆栈的值
 */
void push(LinkStack *stack, int val)
{
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    p->data = val;
    p->next = stack->next;
    stack->next = p;
    cout << "元素：" << val << "入栈成功" << endl;
}

/**
 * 函数“pop”从链接的堆栈中删除顶部元素，如果堆栈为空则返回错误消息。
 *
 * @param stack 指向链接堆栈的顶部节点的指针。
 *
 * @return 什么都没有（无效）。
 */
void pop(LinkStack *stack)
{
    if (stack->next == NULL)
    {
        cout << "栈空，无法出栈" << endl;
        return;
    }
    StackNode *p = stack->next;
    stack->next = p->next;
    free(p);
}

bool empty(LinkStack *stack)
{
    return stack->next == NULL;
}

/**
 * 该函数通过释放其所有节点来销毁链接堆栈。
 *
 * @param stack 指向 LinkStack 结构的指针，它表示堆栈的链表实现。
 */
void destroy(LinkStack *stack)
{
    while (stack->next != NULL)
    {
        StackNode *p = stack->next;
        stack->next = p->next;
        free(p);
    }
}
int main()
{
    LinkStack *stack = (LinkStack *)malloc(sizeof(LinkStack));
    initStack(stack);
    for (int i = 0; i < 10; i++)
    {
        push(stack, i);
    }
    while (!empty(stack))
    {
        cout << stack->next->data << endl;
        pop(stack);
    }
    destroy(stack);
    system("pause");
    return 0;
}