C语言基础（二十四）

堆栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构。堆栈的主要操作包括压栈（Push）、弹栈（Pop）、查看栈顶元素（Peek/Top）等。C语言标准库并没有直接提供堆栈的实现，但可以使用数组或者链表手动实现堆栈。

测试代码1：

#include "date.h" 
#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  
  
#define MAX_SIZE 100 // 定义堆栈的最大容量  
  
typedef struct {  
    int items[MAX_SIZE];  
    int top;  
} Stack;  
  
// 初始化堆栈  
void initStack(Stack *s) {  
    s->top = -1;  
}  
  
// 判断堆栈是否为空  
bool isEmpty(Stack *s) {  
    return s->top == -1;  
}  
  
// 判断堆栈是否已满  
bool isFull(Stack *s) {  
    return s->top == MAX_SIZE - 1;  
}  
  
// 入栈  
bool push(Stack *s, int item) {  
    if (isFull(s)) {  
        printf("Stack overflow\n");  
        return false;  
    }  
    s->items[++s->top] = item;  
    printf("Pushed: %d\n", item);  
    return true;  
}  
  
// 出栈  
bool pop(Stack *s, int *item) {  
    if (isEmpty(s)) {  
        printf("Stack underflow\n");  
        return false;  
    }  
    *item = s->items[s->top--];  
    printf("Popped: %d\n", *item);  
    return true;  
}  
  
// 查看栈顶元素  
bool peek(Stack *s, int *item) {  
    if (isEmpty(s)) {  
        printf("Stack is empty\n");  
        return false;  
    }  
    *item = s->items[s->top];  
    printf("Top element is: %d\n", *item);  
    return true;  
}  
  
int main() {  

    int time = getTime();
    Stack s;  
    initStack(&s);  
  
    // 入栈操作  
    push(&s, 50);  
    push(&s, 2);  
    push(&s, 30);  
    push(&s, 10); 
    push(&s, 88); 
    // 查看栈顶元素  
    int topElem;  
    peek(&s, &topElem);  
  
    // 出栈操作  
    int poppedElem;  
    while (!isEmpty(&s)) {  
        pop(&s, &poppedElem);  
    }  
  
    return 0;  
}

运行结果如下：

测试代码2：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  
  
typedef struct Node {  
    int data;  
    struct Node* next;  
} Node;  
  
typedef struct {  
    Node* top;  
} Stack;  
  
// 初始化堆栈  
void initStack(Stack *s) {  
    s->top = NULL;  
}  
  
// 判断堆栈是否为空  
bool isEmpty(Stack *s) {  
    return s->top == NULL;  
}  
  
// 入栈  
void push(Stack *s, int item) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    if (newNode == NULL) {  
        printf("Memory allocation failed\n");  
        exit(1); // 或者其他错误处理  
    }  
    newNode->data = item;  
    newNode->next = s->top;  
    s->top = newNode;  
    printf("Pushed: %d\n", item);  
}  
  
// 出栈  
bool pop(Stack *s, int *item) {  
    if (isEmpty(s)) {  
        printf("Stack is empty\n");  
        return false;  
    }  
    Node* temp = s->top;  
    *item = temp->data;  
    s->top = temp->next;  
    free(temp);  
    printf("Popped: %d\n", *item);  
    return true;  
}  
  
// 查看栈顶元素  
bool peek(Stack *s, int *item) {  
    if (isEmpty(s)) {  
        printf("Stack is empty\n");  
        return false;  
    }  
    *item = s->top->data;  
    printf("Top element is: %d\n", *item);  
    return true;  
}  
  
// 清理堆栈
void clearStack(Stack *s) {  
    Node* current = s->top;  
    Node* next;  
    while (current != NULL) {  
        next = current->next;  
        free(current);  
        current = next;  
    }  
    s->top = NULL;  
}  
  
int main() {  

    int time = getTime();
    Stack s;  
    initStack(&s);  
  
    // 入栈操作  
    push(&s, 11);  
    push(&s, 80);  
    push(&s, 35);  
    push(&s, 38);
    push(&s, 62);
    // 查看栈顶元素  
    int topElem;  
    peek(&s, &topElem);  
  
    // 出栈操作  
    int poppedElem;  
    while (!isEmpty(&s)) {  
        pop(&s, &poppedElem);  
    }  
  
    // 如果不再需要堆栈，应该调用clearStack释放内存 
	// clearStack(&s); 
    // 本例中，程序将在main函数结束时自动结束，操作系统会回收所有内存。 
  
    return 0;  
}

运行结果如下：