基础级问题
基础级问题
栈的概念、性质、应用
栈的基本概念
栈（Stack） 是一种基本的数据结构，它遵循 先进后出 （Last In, First Out，LIFO）的原则。这意味着最后进入栈的元素将首先被移除。
栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。
栈的基本操作
push：将元素插入栈顶，栈顶元素被移除。
pop：将栈顶元素移除。
Peek：查看栈顶元素，但不移除。
isEmpty：判断栈是否为空。
size：返回栈中元素的个数。
toString：返回栈中元素的字符串表示。
栈的性质
后进先出（Last In, First Out，LIFO）： 栈中最后进入的元素是第一个被访问或移除的。这是栈最基本的性质，决定了栈的操作顺序。
只能在栈顶操作： 栈的操作限定在栈顶进行。元素的添加（压栈）、访问（查看栈顶元素）、移除（弹栈）都只能在栈顶进行，而不能在栈的中间或底部进行操作。
限定操作： 栈的操作通常包括压栈（Push）和弹栈（Pop）。压栈是将元素添加到栈顶，弹栈是从栈顶移除元素。其他可能的操作包括查看栈顶元素（Peek）和判空（isEmpty）。
逻辑上的一维性： 栈的结构是一维的，只有一个方向，即从栈底到栈顶。这简化了栈的实现和理解。
栈的应用
实现浏览器的回退和前进功能
反转字符串
维护函数调用：最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。
表达式求值：编译器和解释器使用栈来跟踪表达式的运算顺序。
递归：递归函数的调用也可以通过栈来实现，每次递归调用都会将参数和返回地址压栈。
深度优先遍历（DFS）：在深度优先搜索过程中，栈被用来保存搜索路径，以便回溯到上一层。
Undo操作：许多应用程序使用栈来实现撤销（Undo）操作，将用户的操作按照顺序压栈，撤销时则弹栈还原状态。
队列的概念、性质、应用
队列的基本概念
队列（Queue） 是一种常见的数据结构，属于线性数据结构，具有 先进先出（First In, First Out，FIFO） 的特性。在队列中，元素按照加入队列的顺序排列，最先进入队列的元素最先被取出。
队列的基本操作
压入元素(添加)：add()、offer()
相同：未超出容量，从队尾压入元素，返回压入的那个元素。
区别：在超出容量时，add()方法会对抛出异常，offer()返回false弹出元素(删除)：remove()、poll()
相同：容量大于0的时候，删除并返回队头被删除的那个元素。
区别：在容量为0的时候，remove()会抛出异常，poll()返回false获取队头元素(不删除)：element()、peek()
相同：容量大于0的时候，都返回队头元素。但是不删除。
区别：容量为0的时候，element()会抛出异常，peek()返回null。
队列的性质
先进先出（FIFO）： 队列中最先进入的元素将被最先取出，保持了元素的顺序性。
只能在队尾插入元素（入队）： 新元素只能添加到队列的尾部，保持了元素的顺序性。
只能在队头删除元素（出队）： 队列中的元素只能从队列的头部移除，保持了元素的顺序性。
先入先出的操作是原子性的： 在队列上的插入和删除操作都是原子性的，不会发生交叉干扰。
队列的应用
任务调度： 操作系统中的任务调度通常使用队列来管理待执行的任务，确保按照先进先出的顺序执行任务。
广度优先搜索（BFS）： 在图的广度优先搜索过程中，队列被用于存储待访问的节点，保证按照层次顺序遍历图的节点。
消息队列： 在分布式系统中，消息队列用于在不同组件或服务之间传递消息，保持消息的有序传递。
缓冲区： 队列常用于实现缓冲区，例如在生产者-消费者模型中，通过队列来平衡生产者和消费者之间的速度差异。
网络数据包处理： 网络路由器和交换机使用队列来处理输入和输出的数据包，保持按照先进先出的原则进行数据传输。