栈

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

定义

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

基本操作

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

实现

顺序栈

顺序栈是使用数组来实现的栈，利用数组的索引来模拟栈的操作。

#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);
    }
    stack->top = -1;  // 栈顶指针初始化为-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;
}

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

// 判断栈是否已满
bool isFull(SeqStack* stack) {
    return stack->top == MAX_SIZE - 1;
}

链式栈

栈的链式存储结构通常是使用单链表来实现。在这种实现中，链表的头部代表栈顶，这样可以确保入栈和出栈操作的时间复杂度为O(1)。

// 定义链式栈的节点结构
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;
}