下载文档原格式
栈的应用场景栈是一种常见的数据结构，它的特点是后进先出（Last In First Out，LIFO）。
栈的应用场景非常广泛，从计算机科学到日常生活都可以见到其身影。
本文将介绍栈在不同领域的应用场景。
1.计算机算法在计算机算法中，栈经常被用于实现递归函数、表达式求值、括号匹配等操作。
递归函数的调用过程实际上是一个栈的过程，每当一个函数调用另一个函数时，系统会将当前函数的状态信息压入栈中，待调用的函数执行完毕后再从栈中弹出上一个函数的状态信息继续执行。
表达式求值中，栈可以用于存储操作数和运算符，通过弹出栈中的元素进行计算，最终得到表达式的结果。
括号匹配中，栈可以用于判断左右括号是否匹配。
2.编译器和操作系统编译器和操作系统也是栈的常用应用场景。
在编译器中，栈用于存储函数调用的参数、局部变量和返回地址等信息。
每当函数调用时，编译器会将相关信息压入栈中，函数执行结束后再从栈中弹出相关信息。
操作系统中的函数调用、中断处理等过程也经常使用栈来保存现场信息，保证程序的正确执行。
3.网络协议在网络协议中，栈被广泛应用于网络数据的传输和处理。
TCP/IP协议栈是一个典型的例子，它将网络层、传输层、应用层等不同的协议通过栈的形式依次封装，完成数据的传输和处理。
数据包从应用层一直传输到网络层，以栈的形式不断压入和弹出，确保数据的准确传递和处理。
4.浏览器的前进后退功能在浏览器中，前进和后退功能是栈应用的典型场景。
当我们浏览网页时，每当点击一个链接或者输入一个网址，浏览器会将当前的URL 压入栈中。
当我们点击“后退”按钮时，浏览器会从栈中弹出上一个URL，完成页面的后退操作。
同样地，当我们点击“前进”按钮时，浏览器会从栈中弹出下一个URL，完成页面的前进操作。
5.撤销和恢复操作在各种应用程序中，栈可用于实现撤销和恢复操作。
例如，在文字编辑器中，当我们对文字进行修改后，可以将修改前的状态信息压入栈中，以备将来的撤销操作。
数据结构经典案例在计算机科学领域，数据结构是组织和存储数据的方式，以便能够高效地访问、操作和管理数据。
数据结构的选择对于算法的性能和程序的效率有着至关重要的影响。
下面将为您介绍几个数据结构的经典案例。
一、栈（Stack）栈是一种遵循“后进先出”（Last In First Out，LIFO）原则的数据结构。
想象一下一叠盘子，最后放上去的盘子总是最先被拿走，栈就是这样的工作原理。
一个常见的栈的应用是表达式求值。
比如我们要计算数学表达式“3 ＋ 4 2”。
首先，将数字和运算符依次压入栈中。
当遇到运算符时，从栈中弹出相应数量的操作数进行计算，然后将结果压回栈中。
通过这种方式，能够按照正确的运算顺序得出最终的结果。
在编程语言中，函数调用也用到了栈。
当一个函数被调用时，其相关的信息（如参数、返回地址等）被压入栈中。
当函数执行完毕后，这些信息被弹出，程序回到之前的执行点继续执行。
二、队列（Queue）队列遵循“先进先出”（First In First Out，FIFO）原则。
就像排队买东西，先排队的人先得到服务。
在操作系统中，打印任务通常使用队列来管理。
多个打印任务按照提交的先后顺序排列在队列中，打印机依次处理队列中的任务。
另外，在消息传递系统中，队列也被广泛应用。
发送方将消息放入队列，接收方从队列中取出消息进行处理。
三、链表（Linked List）链表是一种动态的数据结构，其中的元素通过指针连接在一起。
在需要频繁进行插入和删除操作的场景中，链表表现出色。
比如，在一个学生管理系统中，如果需要不断地添加或删除学生信息，使用链表可以方便地在任意位置进行操作，而不需要像数组那样移动大量的元素。
四、树（Tree）树是一种分层的数据结构，具有根节点、子节点和叶节点。
二叉搜索树（Binary Search Tree）是一种常见的树结构。
在二叉搜索树中，左子树的所有节点值都小于根节点的值，右子树的所有节点值都大于根节点的值。
数据结构（⼀）——线性表、栈和队列数据结构是编程的起点，理解数据结构可以从三⽅⾯⼊⼿：1. 逻辑结构。
逻辑结构是指数据元素之间的逻辑关系，可分为线性结构和⾮线性结构，线性表是典型的线性结构，⾮线性结构包括集合、树和图。
2. 存储结构。
存储结构是指数据在计算机中的物理表⽰，可分为顺序存储、链式存储、索引存储和散列存储。
数组是典型的顺序存储结构；链表采⽤链式存储；索引存储的优点是检索速度快，但需要增加附加的索引表，会占⽤较多的存储空间；散列存储使得检索、增加和删除结点的操作都很快，缺点是解决散列冲突会增加时间和空间开销。
3. 数据运算。
施加在数据上的运算包括运算的定义和实现。
运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
因此，本章将以逻辑结构（线性表、树、散列、优先队列和图）为纵轴，以存储结构和运算为横轴，分析常见数据结构的定义和实现。
在Java中谈到数据结构时，⾸先想到的便是下⾯这张Java集合框架图：从图中可以看出，Java集合类⼤致可分为List、Set、Queue和Map四种体系，其中：List代表有序、重复的集合；Set代表⽆序、不可重复的集合；Queue代表⼀种队列集合实现；Map代表具有映射关系的集合。
在实现上，List、Set和Queue均继承⾃Collection，因此，Java集合框架主要由Collection和Map两个根接⼝及其⼦接⼝、实现类组成。
本⽂将重点探讨线性表的定义和实现，⾸先梳理Collection接⼝及其⼦接⼝的关系，其次从存储结构（顺序表和链表）维度分析线性表的实现，最后通过线性表结构导出栈、队列的模型与实现原理。
主要内容如下：1. Iterator、Collection及List接⼝2. ArrayList / LinkedList实现原理3. Stack / Queue模型与实现⼀、Iterator、Collection及List接⼝Collection接⼝是List、Set和Queue的根接⼝，抽象了集合类所能提供的公共⽅法，包含size()、isEmpty()、add(E e)、remove(Object o)、contains(Object o)等，iterator()返回集合类迭代器。
/* *题目：设计一个字符型的链栈。 * 编写进栈、出栈、显示栈中全部元素的程序。 *题目：编写一个把十进制整数转换为二进制数的应用程序 *题目：编写一个把中缀表达式转换为后缀表达式（逆波兰式）的应用程序 *题目：设计一个选择式菜单，以菜单方式选择上述操作。 * 栈 子 系 统 * ******************************* * * 1------进 栈 * * * 2------出 栈 * * * 3------显 示 * * * 4------数值转换 * * * 5------逆波兰式 * * * 0------返 回 * * ******************************* * 请选择菜单号（0--5）： */
#include #include
#define STACKMAX 50 typedef struct sta //栈的存储结构 { int data; struct sta *next; }stackNode; typedef struct //指向栈顶的指针 { stackNode *top; }linkStack;
void conversion(int n); void push(linkStack *p, int x); int pop(linkStack *p); void showStack(linkStack *p); void sufflx();
/************************************************* Function: main() Description: 主调函数 Calls: push() pop() showStack() conversion() Input: NULL Return: void Others: NULL *************************************************/ void main() { int x, choice, i = 1;
linkStack p; p.top = NULL; //置空栈
while (i) { printf("\n 栈 子 系 统\n"); printf("*******************************\n"); printf("* 1------进 栈 *\n"); printf("* 2------出 栈 *\n"); printf("* 3------显 示 *\n"); printf("* 4------数值转换 *\n"); printf("* 5------逆波兰式 *\n"); printf("* 0------返 回 *\n"); printf("*******************************\n"); printf("请选择菜单号（0--5）："); fflush(stdin); //清空输入的缓存区 choice = getchar();
switch(choice) { case '1': while (1) { printf("请输入一个整数（‘0’表示结束）并按回车："); scanf("%d", &x);
if (x != 0) { push(&p, x); //入栈 } else { break; } } break; case '2': x = pop(&p); //出栈 if (x > 0) { printf("出栈元素为：%d\n", x); } else { printf("栈为空，没有元素可以出栈！\n"); } break; case '3': showStack(&p); //显示栈元素 break; case '4': printf("请输入十进制数："); scanf("%d", &x);
conversion(x); //数值转换 break; case '5': sufflx(); break; case '0': i = 0; break; default: i = 1; break; } } }
/************************************************* Function: conversion() Description: 十进制数转换二进制数 Calls: push() pop() Input: n :输入的要转换的数 Return: void Others: NULL *************************************************/ void conversion(int n) { linkStack s; int x, i = 1;
s.top = NULL; //置空栈 do { x = n%2; //求余数 n = n/2; //求新商 push(&s, x); //入栈 }while (n);
printf("转化的二进制为："); while (i) { x = pop(&s); //出栈 if (x != -1) //判断是否全部出栈 { printf("%d", x); } else { i = 0; } } printf("\n"); }
void sufflx() { char str[STACKMAX]; //存储中缀表达式 char exp[STACKMAX]; //存储后缀表达式 char stark[STACKMAX]; //顺序栈来存放运算符 int top = 0; //顺序栈置空 int sum, t, i = 0; char ch;
printf("请输入一个算术表达式（运算符只能包含+，-，*，/），以#结束：\n"); fflush(stdin);
do { i++; scanf("%c", &str[i]); } while (str[i] != '#' && i != STACKMAX); //存储用户输入的中缀表达式
sum = i; //保存表达式的长度 i = t = 1; ch = str[i]; i++; while (ch != '#') { switch (ch) { case '(': //读取到‘（’时，入栈 top++; stark[top] = ch; break; case ')': //读取到‘）’时 while (stark[top] != '(') { exp[t++] = stark[top--]; //出栈并赋值给输出数组 exp[t++] = ','; //添加分割符号 } top--; //栈顶元素为‘（’时，出栈 break; case '+': //读取到‘+’时 while (top != 0 && stark[top] != '(') //判断符号优先级 { exp[t++] = stark[top--]; exp[t++] = ','; } stark[++top] = ch; //栈为空时入栈 break; case '-': //读取到‘-’时 while (top != 0 && stark[top] != '(') { exp[t++] = stark[top--]; exp[t++] = ','; } stark[++top] = ch; //栈为空时入栈 break; case '*': //读取到‘*’时 while (stark[top] == '*' || stark[top] == '/') //*、/运算级最高 { exp[t++] = stark[top--]; exp[t++] = ','; } stark[++top] = ch; //运算符优先级高的入栈 break; case '/': //读取到‘/’时 while (stark[top] == '*' || stark[top] == '/') { exp[t++] = stark[top--]; exp[t++] = ','; } stark[++top] = ch; //运算符优先级高的入栈 break; case ' ': //读取到空格时忽略 break; default: //不是运算符号时 while (ch >= '0' && ch <= 'z') //限制输入的变量 { exp[t++] = ch; ch = str[i++]; } i--; //上面多加的要去掉 exp[t++] = ','; break; } ch = str[i++]; }
while (top != 0) //顺序栈中仍有数值时 { exp[t++] = stark[top--]; if (top != 0) { exp[t++] = ','; } }
printf("中缀表达式为："); //输出 for (i = 1; i < sum; i++) { printf("%c", str[i]); } printf("\n后缀表达式为："); for (i = 1; i < t; i++)
