1、预备知识点
-
栈（Stack）和队列（Queue）是两种操作受限的线性表。
-
（线性表：线性表是一种线性结构，它是一个含有n≥0个结点的有限序列，同一个线性表中的数据元素数据类型相同并且满足“一对一”的逻辑关系。
“一对一”的逻辑关系指的是对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。） -
这种受限表现在：栈的插入和删除操作只允许在表的尾端进行（在栈中成为“栈顶”），满足“FIFO：First In Last Out”；队列只允许在表尾插入数据元素，在表头删除数据元素,满足“First In First Out”。
-
栈与队列的相同点：
-
1.都是线性结构。
-
2.插入操作都是限定在表尾进行。
-
3.都可以通过顺序结构和链式结构实现。
-
4.插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。
-
5.多链栈和多链队列的管理模式可以相同。
-
-
栈与队列的不同点：
-
1.删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。
-
2.应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。
-
3.顺序栈能够实现多栈空间共享，而顺序队列不能。
-
- 栈的一般操作
- empty() 堆栈为空则返回真
- pop() 移除栈顶元素
- push() 在栈顶增加元素
- size() 返回栈中元素数目
- top() 返回栈顶元素
- 栈的基本操作
- empty() 队列为空则返回真
- front() 返回队列头部元素
- back () 返回队列尾部元素
- pop() 弹出队列头部元素
- push() 将元素添加到队列
- size() 返回队列中元素数目
2.常见题目思考
- 设计一个栈，支持基本的栈操作，这个栈的内部存储数据的结构是队列。队列的方法只能包括push \ front \ pop \ size \ empty等标准的队列方法
- 设计一个队列，支持基本的队列操作，这个队列的内部存储数据结构为栈，栈的方法只能包括 push \ top \ pop \ size \empty 等标准的栈方法。
- 设计一个栈，支持如下操作，这些操作的算法复杂度需要是常数级，O(1) 1.push(x) : 将元素x压入栈中 2.pop() : 弹出(移除)栈顶元素 3.top() : 返回栈顶元素 4.getMin() : 返回栈内最小元素
- 已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法？
思路：
- 1:出栈结果存储在队列order 中。
- 2:按元素顺序，将元素push进入栈。
- 3: 每push 一个元素，即检查是否与队列首部元素相同则弹出队列首元素，弹出栈顶元素，直到两元素不同结束。
- 4: 若最终栈为空，说明序列合法，否则不合法。
二叉堆的属性
-
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
-
最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
-
已知一个未排序的数组，求这个数组中第K大的数字!
- 思路：
- 维护一个K大小的最小堆，堆中元素个数小于K时，新元素直接进入堆；否则，当堆顶小于新元素时，弹出堆顶，将新元素加入堆。
- 解释: 由于堆是最小堆，堆顶是堆中最小元素，新元素都会保证比堆顶小(否则新元素替换堆顶)，故堆中K个元素是已扫描的元素里最大的K个；堆顶即为第K大的数。
-
设计一个数据结构，该数据结构动态维护一组数据，且支持如下操作:
-
1.添加元素: void addNum(int num)，将整型num添加至数据结构中。
-
2.返回数据的中位数: double findMedian()，返回其维护的数据的中位数。 中位数定义: 1.若数据个数为奇数，中位数是该组数排序后中间的数。[1,2,3] -> 2 2.若数据个数为偶数，中位数是该组数排序后中间的两个数字的平均值。[1,2,3,4] -> 2.5
-
思路：
- 动态维护一个最大堆和一个最小堆，最大堆存储一半的数据，最小堆存储一半的数据，维持最大堆的堆顶比最小堆的堆顶小。
-
241天以来，Java架构更新了 602个主题，已经有100+位同学加入。微信扫码关注java架构，获取Java面试题和架构师相关题目和视频。上述相关面试题答案，尽在Java架构中。
网友评论