栈

需熟练掌握栈的定义、操作和实现方式。

定义

栈是一个元素的集合，加入元素的操作叫做“压栈”（push），而移除元素的操作叫做“出栈”（pop）。它遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后被压入栈的元素是第一个被弹出的元素。

基本操作

push(element): 将元素添加到栈的顶部。
pop(): 移除并返回栈顶的元素。如果栈为空，这个操作可能会抛出一个错误或返回特定的值（例如null或undefined），具体取决于实现。
peek() 或 top(): 返回栈顶的元素但不移除它。这只是一个查看操作，栈的内容不会改变。如果栈为空，这个操作可能会抛出一个错误或返回特定的值。
isEmpty(): 判断栈是否为空。如果栈为空，返回true；否则返回false。
size() 或 length(): 返回栈中元素的数量。

实现

栈的实现方式有两种，顺序栈和链式栈。顺序栈是在顺序表的基础上实现栈结构，链式栈是在链表的基础上实现栈结构。

顺序栈

顺序栈是使用数组来实现的栈，利用数组的索引来模拟栈的操作。与普通的线性表不同，栈的操作被限制在表的一端进行，这一端被称为栈顶 (Top)，另一端被称为栈底 (Bottom)。

顺序栈的关键在于栈顶指针，栈顶指针是一个整数变量，用于指示栈顶元素在数组中的位置。其值的变化直接反映了栈中元素的变化。当栈空时，一般将栈顶指针设置为 1，当栈满时，栈顶指针指向数组中的最后一个元素。

当元素入栈时，将栈顶指针向后移动一个位置、然后放置新元素即可。当元素出栈时，需要将栈顶指针向前移动一个位置。当然，入栈和出栈时需要保证数组不满或者不空。

#define MAX_SIZE 100 // 定义栈的最大容量

// 定义顺序栈的结构
typedef struct {
    int data[MAX_SIZE]; // 使用数组存储数据
    int top;            // 栈顶指针
} SeqStack;

// 初始化栈
SeqStack* initStack() {
    SeqStack* stack = (SeqStack*)malloc(sizeof(SeqStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    // 栈顶指针初始化为-1，表示栈为空
    stack->top = -1; 
    return stack;
}

// 入栈操作
bool push(SeqStack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full!\n");
        return false;
    }
    // 先移动栈顶指针，再存放元素
    stack->data[++stack->top] = value;
    return true;
}

// 出栈操作
bool pop(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    // 先取出元素，再移动栈顶指针
    *value = stack->data[stack->top--];
    return true;
}

// 获取栈顶元素
bool peek(SeqStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->data[stack->top];
    return true;
}

// 判断栈是否为空
// 当栈中没有元素时，栈顶指针通常指向一个特殊的位置，例如 -1。
bool isEmpty(SeqStack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
// 当栈顶指针指向数组中的最后一个元素时，说明栈已经满了
bool isFull(SeqStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

链式栈

栈的链式存储结构利用单链表来实现栈的功能。为了保证入栈（Push）和出栈（Pop）操作的时间复杂度为 O(1)，通常将链表的头部作为栈顶。

链式栈的栈顶指针指向链表的首部，如果栈为空的话，栈顶指针指向 NULL。

// 定义链式栈的节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链式栈的结构
typedef struct {
    Node* top;
} LinkedStack;

// 初始化栈
LinkedStack* initStack() {
    LinkedStack* stack = (LinkedStack*)malloc(sizeof(LinkedStack));
    if(!stack) {
        printf("Failed to allocate memory for stack\n");
        exit(1);
    }
    stack->top = NULL; // 栈顶指针初始化为NULL，表示栈为空
    return stack;
}

// 入栈操作
void push(LinkedStack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(!newNode) {
        printf("Failed to allocate memory for new node\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 出栈操作
bool pop(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    Node* temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;
    free(temp);
    return true;
}

// 获取栈顶元素
bool peek(LinkedStack* stack, int* value) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        return false;
    }
    *value = stack->top->data;
    return true;
}

// 判断栈是否为空
bool isEmpty(LinkedStack* stack) {
    return stack->top == NULL;
}