目录
🍉引言
🍉栈的本质和特点
🍈栈的基本操作
🍈栈的特点
🍍后进先出
🍍操作受限
🍍动态调整
🍈栈的优缺点
🍍优点
🍍缺点
🍉栈的应用
栈的代码实现
代码说明
图解栈的出入过程
压栈过程
出栈过程
栈的实际应用实例
括号匹配
浏览器前进后退功能
代码说明
🍉栈的实现细节和优化
🍈数组实现栈的优化
🍉引言
栈(Stack)是一种常见的数据结构,在计算机科学中具有重要的应用价值。栈的操作受限于后进先出(LIFO, Last In First Out)的原则,这种特点使得栈在处理特定类型的问题时非常高效。本文将详细解析栈的本质和特点,并通过生活中的例子和代码实现来深入理解栈的应用。
🍉栈的本质和特点
- 栈是一种线性数据结构,只允许在一端进行插入和删除操作,这一端称为栈顶(Top)。与栈顶相对的另一端称为栈底(Bottom),栈底是固定的,不进行操作
🍈栈的基本操作
栈有几种基本操作:
- 压栈(Push):将一个元素添加到栈顶。
- 出栈(Pop):移除并返回栈顶元素。
- 取栈顶元素(Peek or Top):返回栈顶元素但不移除它。
- 检查栈是否为空(isEmpty):返回布尔值,指示栈是否为空。
- 检查栈是否已满(isFull):返回布尔值,指示栈是否已满(主要用于固定大小的栈)。
🍈栈的特点
🍍后进先出
- 栈的最主要特点是后进先出,即最新加入的元素最先被移除。这种特性使得栈特别适用于某些特定的应用场景。
🍍操作受限
- 与其他数据结构相比,栈的操作比较受限。只能在栈顶进行压栈和出栈操作,不能直接访问栈中的任意元素。
🍍动态调整
- 栈可以是固定大小的,也可以是动态调整大小的。动态栈会根据需要自动调整其容量。
🍈栈的优缺点
🍍优点
简单高效: 栈的操作简单,只需考虑栈顶元素,因此执行速度较快。
内存管理: 栈内存的分配和释放是自动进行的,不需要手动管理内存,避免了内存泄漏和垃圾回收的问题。
递归调用: 栈结构天然适合处理递归调用,函数的调用和返回都可以利用栈的特性。
🍍缺点
大小限制: 栈的大小通常是固定的,当数据量超过栈的容量时会导致栈溢出。
数据不灵活: 栈是一种后进先出(LIFO)的数据结构,只能在栈顶进行操作,不适合需要随机访问数据的场景。
局部性: 栈中的数据只能按照特定的顺序访问,缺乏灵活性,不能满足所有的数据操作需求。
🍉栈的应用
栈在现实生活和计算机科学中都有广泛的应用:
- 函数调用:计算机系统使用栈来管理函数调用。每次函数调用时,当前函数的状态(如局部变量、返回地址等)会被压入栈中。当函数返回时,状态从栈中弹出并恢复。
- 表达式求值和语法解析:栈用于将中缀表达式转换为后缀表达式或前缀表达式,并且在表达式求值过程中,栈也扮演重要角色。
- 浏览器的前进后退功能:浏览器使用两个栈来管理用户的浏览历史,一个栈存储前进的页面,另一个栈存储后退的页面。
- 撤销操作:许多软件(如文本编辑器、图像编辑器等)使用栈来实现撤销和恢复功能。
栈的代码实现
#include#include #include typedef struct Stack { int *items; int top; int capacity; } Stack; // 初始化栈 Stack* createStack(int capacity) { Stack *stack = (Stack *)malloc(sizeof(Stack)); stack->capacity = capacity; stack->top = -1; stack->items = (int *)malloc(capacity * sizeof(int)); return stack; } // 检查栈是否为空 bool is_empty(Stack *stack) { return stack->top == -1; } // 压入元素到栈 void push(Stack *stack, int item) { if (stack->top == stack->capacity - 1) { printf("栈已满,无法压入元素\n"); return; } stack->items[++stack->top] = item; } // 弹出栈顶元素 int pop(Stack *stack) { if (is_empty(stack)) { printf("栈为空,无法弹出元素\n"); exit(EXIT_FAILURE); } return stack->items[stack->top--]; } // 获取栈顶元素 int peek(Stack *stack) { if (is_empty(stack)) { printf("栈为空,无法获取栈顶元素\n"); exit(EXIT_FAILURE); } return stack->items[stack->top]; } // 获取栈的大小 int size(Stack *stack) { return stack->top + 1; } int main() { Stack *stack = createStack(100); // 创建一个容量为100的栈 push(stack, 1); push(stack, 2); push(stack, 3); printf("栈顶元素:%d\n", peek(stack)); // 输出 3 printf("出栈元素:%d\n", pop(stack)); // 输出 3 printf("栈顶元素:%d\n", peek(stack)); // 输出 2 printf("栈大小:%d\n", size(stack)); // 输出 2 // 释放分配的内存 free(stack->items); free(stack); return 0; }
代码说明
- Stack 结构体包含一个整数数组 items,一个表示栈顶索引的 top,和一个表示栈容量的 capacity。
- createStack 函数用于初始化栈并分配内存。
- is_empty 函数用于检查栈是否为空。
- push 函数用于将元素压入栈,并在栈满时打印错误信息。
- pop 函数用于弹出栈顶元素,并在栈为空时打印错误信息并退出程序。
- peek 函数用于获取栈顶元素,并在栈为空时打印错误信息并退出程序。
- size 函数用于获取栈的大小(当前存储的元素数量)。
- main 函数演示了栈的使用,类似于您提供的 Python 代码示例。
图解栈的出入过程
- 为了更直观地理解栈的操作过程,我们可以使用图解的方式来展示栈的压栈和出栈操作。
压栈过程
- 初始状态:栈为空
栈: []
- 压栈 1:
压栈 1 栈: [1]
- 压栈 2:
压栈 2 栈: [1, 2]
- 压栈 3:
压栈 3 栈: [1, 2, 3]
出栈过程
- 初始状态:栈顶元素为 3
栈: [1, 2, 3]
- 出栈 3:
出栈 3 栈: [1, 2]
- 出栈 2:
出栈 2 栈: [1]
- 出栈 1:
出栈 1 栈: []
栈的实际应用实例
括号匹配
- 括号匹配问题是栈的经典应用之一,常用于编译器和解释器的语法解析。
#include
#include #include // 栈结构定义 typedef struct Stack { int top; unsigned capacity; char* array; } Stack; // 创建栈 Stack* createStack(unsigned capacity) { Stack* stack = (Stack*) malloc(sizeof(Stack)); stack->capacity = capacity; stack->top = -1; stack->array = (char*) malloc(stack->capacity * sizeof(char)); return stack; } // 判断栈是否为空 int isEmpty(Stack* stack) { return stack->top == -1; } // 入栈 void push(Stack* stack, char item) { stack->array[++stack->top] = item; } // 出栈 char pop(Stack* stack) { if (isEmpty(stack)) return '\0'; return stack->array[stack->top--]; } // 获取栈顶元素 char peek(Stack* stack) { if (isEmpty(stack)) return '\0'; return stack->array[stack->top]; } // 判断括号是否平衡 int isBalanced(const char* expression) { Stack* stack = createStack(strlen(expression)); char pairs[256] = { 0 }; pairs[')'] = '('; pairs[']'] = '['; pairs['}'] = '{'; for (int i = 0; i < strlen(expression); i++) { char char = expression[i]; if (char == '(' || char == '{' || char == '[') { push(stack, char); } else if (char == ')' || char == '}' || char == ']') { if (isEmpty(stack) || pop(stack) != pairs[char]) { free(stack->array); free(stack); return 0; // false } } } int balanced = isEmpty(stack); free(stack->array); free(stack); return balanced; } // 测试函数 int main() { const char* expression1 = "{[()()]}"; printf("%s\n", isBalanced(expression1) ? "True" : "False"); const char* expression2 = "{[(])}"; printf("%s\n", isBalanced(expression2) ? "True" : "False"); return 0; }
浏览器前进后退功能
浏览器的前进和后退功能可以通过两个栈来实现,一个栈用于存储前进页面,另一个栈用于存储后退页面:
#include
#include #include typedef struct Node { char* data; struct Node* next; } Node; typedef struct Stack { Node* top; } Stack; // 初始化栈 void init_stack(Stack* stack) { stack->top = NULL; } // 检查栈是否为空 int is_empty(Stack* stack) { return stack->top == NULL; } // 推入元素到栈 void push(Stack* stack, const char* data) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = (char*)malloc(strlen(data) + 1); strcpy(new_node->data, data); new_node->next = stack->top; stack->top = new_node; } // 弹出栈顶元素 char* pop(Stack* stack) { if (is_empty(stack)) { return NULL; } Node* temp = stack->top; char* data = temp->data; stack->top = stack->top->next; free(temp); return data; } // 浏览器历史记录结构体 typedef struct BrowserHistory { Stack forward_stack; Stack backward_stack; char* current_page; } BrowserHistory; // 初始化浏览器历史记录 void init_browser_history(BrowserHistory* history) { init_stack(&history->forward_stack); init_stack(&history->backward_stack); history->current_page = NULL; } // 访问新页面 void visit(BrowserHistory* history, const char* page) { if (history->current_page != NULL) { push(&history->backward_stack, history->current_page); } history->current_page = (char*)malloc(strlen(page) + 1); strcpy(history->current_page, page); // 清空前进栈 while (!is_empty(&history->forward_stack)) { free(pop(&history->forward_stack)); } } // 后退 char* back(BrowserHistory* history) { if (!is_empty(&history->backward_stack)) { push(&history->forward_stack, history->current_page); history->current_page = pop(&history->backward_stack); return history->current_page; } else { return NULL; // 无法后退 } } // 前进 char* forward(BrowserHistory* history) { if (!is_empty(&history->forward_stack)) { push(&history->backward_stack, history->current_page); history->current_page = pop(&history->forward_stack); return history->current_page; } else { return NULL; // 无法前进 } } int main() { BrowserHistory history; init_browser_history(&history); visit(&history, "Page1"); visit(&history, "Page2"); visit(&history, "Page3"); printf("%s\n", back(&history)); // 输出 Page2 printf("%s\n", back(&history)); // 输出 Page1 printf("%s\n", forward(&history)); // 输出 Page2 return 0; } 代码说明
- 栈的实现:我们用 Node 结构体来表示栈中的节点,用 Stack 结构体来管理栈顶节点。提供了初始化、检查空栈、推入和弹出元素的函数。
- 浏览器历史记录:用 BrowserHistory 结构体来管理当前页面和两个栈。提供了初始化、访问新页面、后退和前进的函数。
- 内存管理:使用 malloc 和 free 来动态分配和释放内存,以避免内存泄漏。
🍉栈的实现细节和优化
- 在实际应用中,栈的实现可以有多种方式,包括使用数组(列表)或链表。每种方式都有其优缺点:
- 数组实现栈:简单高效,但需要预先确定栈的最大容量,可能会导致空间浪费或溢出。
- 链表实现栈:灵活,无需预先确定栈的容量,但每个节点需要额外的指针存储空间,操作相对复杂。
🍈数组实现栈的优化
- 为了解决数组实现栈的容量限制问题,可以使用动态数组,它会在需要时自动扩展容量:
#include
#include #include typedef struct { int *items; int capacity; int size; } DynamicArrayStack; // Initialize the stack DynamicArrayStack* createStack() { DynamicArrayStack* stack = (DynamicArrayStack*)malloc(sizeof(DynamicArrayStack)); stack->capacity = 1; stack->size = 0; stack->items = (int*)malloc(stack->capacity * sizeof(int)); return stack; } // Check if the stack is empty bool isEmpty(DynamicArrayStack* stack) { return stack->size == 0; } // Push an item onto the stack void push(DynamicArrayStack* stack, int item) { if (stack->size == stack->capacity) { stack->capacity *= 2; stack->items = (int*)realloc(stack->items, stack->capacity * sizeof(int)); } stack->items[stack->size++] = item; } // Pop an item from the stack int pop(DynamicArrayStack* stack) { if (isEmpty(stack)) { fprintf(stderr, "pop from empty stack\n"); exit(EXIT_FAILURE); } return stack->items[--stack->size]; } // Peek at the top item of the stack int peek(DynamicArrayStack* stack) { if (isEmpty(stack)) { fprintf(stderr, "peek from empty stack\n"); exit(EXIT_FAILURE); } return stack->items[stack->size - 1]; } // Get the size of the stack int stackSize(DynamicArrayStack* stack) { return stack->size; } // Free the stack void freeStack(DynamicArrayStack* stack) { free(stack->items); free(stack); } int main() { // Create and use the dynamic array stack DynamicArrayStack* dynamicStack = createStack(); push(dynamicStack, 1); push(dynamicStack, 2); push(dynamicStack, 3); printf("栈顶元素:%d\n", peek(dynamicStack)); // 输出 3 printf("出栈元素:%d\n", pop(dynamicStack)); // 输出 3 printf("栈顶元素:%d\n", peek(dynamicStack)); // 输出 2 printf("栈大小:%d\n", stackSize(dynamicStack)); // 输出 2 freeStack(dynamicStack); return 0; }
希望这些能对刚学习算法的同学们提供些帮助哦!!!
- 括号匹配问题是栈的经典应用之一,常用于编译器和解释器的语法解析。
- 出栈 1:
- 出栈 2:
- 出栈 3:
- 初始状态:栈顶元素为 3
- 压栈 3:
- 压栈 2:
- 压栈 1:
- 初始状态:栈为空