软件技术基础-栈结构(与“队列”有关文档共38张).pptx

【栈结构】 栈是一种特殊的线性数据结构，它的特点是仅允许在数据结构的一端进行插入和删除操作，这一端被称为栈顶。栈的操作遵循“后进先出”（Last In First Out，简称LIFO）的原则，即最后进入栈的元素会首先被移出栈。在计算机科学中，栈广泛应用于程序调用、表达式求值、内存管理等多个领域。 ### 数组实现栈 使用数组来实现栈，通常会设置一个固定大小的数组和一个指针top来表示栈顶的位置。当有新元素压入栈时，top指针向上移动，新元素存储在top指向的位置；弹出元素时，将栈顶元素复制出来，然后top指针向下移动。栈为空时，top等于0；栈满时，top等于数组长度减1。 ```c typedef struct stack_type{ elemtype data[MAXNUM]; int top; }stack_type; void push(stack_type *stack, elemtype new_one){ if(stack->top == MAXNUM - 1) error("Stack Overflow"); stack->data[++stack->top] = new_one; } elemtype pop(stack_type *stack){ if(stack->top < 0) error("Stack Underflow"); elemtype out = stack->data[stack->top]; stack->top--; return out; } ``` ### 链表实现栈 对于动态变化的需求，可以使用链表来实现栈。链表中的每个节点包含一个数据元素和指向下一个节点的指针。栈顶通过一个指针top指向链表的第一个元素。在链表栈中，压栈操作是向链表头部添加新的节点，弹栈操作则是删除链表的第一个节点。 ```c typedef struct lnode{ elemtype data; struct lnode *next; }node_type; typedef struct lstack_type{ node_type *top; int length; }lstack_type; void push(lstack_type *stack, elemtype new_one){ node_type *new_node = (node_type*)malloc(sizeof(node_type)); new_node->data = new_one; new_node->next = stack->top; stack->top = new_node; stack->length++; } elemtype pop(lstack_type *stack){ if(stack->top == NULL) error("Stack Underflow"); node_type *temp = stack->top; elemtype out = temp->data; stack->top = temp->next; free(temp); stack->length--; return out; } ``` ### 栈的应用 栈在程序设计中有很多实际应用，例如： 1. **递归调用**：在函数调用时，系统会使用栈来存储各个函数调用的返回地址和局部变量，形成一个函数调用栈。例如，程序A调用B，B调用C，就形成了一个栈结构。 2. **表达式求值**：在计算中缀表达式时，可以使用两个栈，一个用于存储操作数，一个用于存储运算符，根据运算符的优先级进行相应的压栈和弹栈操作。 3. **括号匹配**：在编译器设计中，可以通过栈来检查括号是否匹配，遇到左括号压栈，遇到右括号检查栈顶元素是否为其对应的左括号，如果是则弹栈，否则表示括号不匹配。 以上就是关于栈结构的基本知识，包括栈的定义、数组和链表两种实现方式，以及栈在程序设计中的应用。在实际编程中，栈是一种非常重要的数据结构，理解和熟练运用它能帮助我们解决很多复杂问题。