最大栈
具有栈的功能,并且提供O(1)的时间复杂度来获取最大值max。
思路:使用一个辅助栈assist来维护最大值,最大值为assist的栈顶元素。当入栈的值大于最大值时,将该值压入assist栈,相当于更新了最大值。当有元素出栈时,检查该元素是否为最大值,如果是,则assist出栈,即更新了最大值。
import java.util.Stack;
public class MaxStack {
private Stack<Integer> s;
private Stack<Integer> assist;
public MaxStack() {
s = new Stack<Integer>();
assist = new Stack<Integer>();
assist.push(Integer.MIN_VALUE);
}
public int pop() throws Exception {
if (isEmpty())
throw new Exception("empty stack");
int result = s.pop();
if (result == assist.peek())
assist.pop();
return result;
}
public void push(int i) {
s.push(i);
if (i > max()) {
assist.push(i);
}
}
public int peek() {
return s.peek();
}
public boolean isEmpty() {
return s.isEmpty();
}
public int max() {
return assist.peek();
}
}
最大队列
具有队列的功能,并提供O(1)的时间复杂度获取最大值。
思路:使用两个最大栈来构成一个队列。入队的元素从s1进栈,当有元素出队时,如果s2非空,则从s2出栈。否则,将s1中的元素出栈并从s2中入栈。最大值为s1的最大值和s2的最大值中的较大值。
public class MaxQueue {
MaxStack s1;
MaxStack s2;
public MaxQueue() {
s1 = new MaxStack();
s2 = new MaxStack();
}
public int max() {
int result = s1.max() > s2.max() ? s1.max() : s2.max();
return result;
}
public boolean isEmpty() {
if (s1.isEmpty() && s2.isEmpty())
return true;
return false;
}
public void enqueue(int i) {
s1.push(i);
}
public int dequeue() throws Exception {
if (isEmpty())
throw new Exception("is empty");
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
}
分享到:
相关推荐
栈实现 队列实现 双栈实现队列 双队列实现栈 栈实现O(n)求当前栈最大值 http://blog.csdn.net/ssuchange/article/details/17398007
体育课经常排在上午3、4节,一...那么,问题来了,现给定所有同学的身高(假设体育课大家修炼了一种神秘技能,改变了自己的身高,(身高最大值为2*106),要求每个人能往右侧看到的人数之和(建议使用long long存储)。
优先队列有两种常见的类型:最大优先队列和最小优先队列。在最大优先队列中,优先级最高的元素(即值最大的元素)最先出队;而在最小优先队列中,优先级最低的元素(即值最小的元素)最先出队。如果队列中有多个元素...
一个文件commom.h #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 第二个文件seqlist.h #define ElemType ...defineMAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/...
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 D ④ 栈底 分别设在这片内存空间的两端,这样,只有当 两个栈的栈顶在达栈空间的某一位置相遇 E 时,才产生上溢。
优先队列通常使用二叉堆(包括最大堆和最小堆)来实现,因为堆的性质使得插入和删除最大(或最小)元素的操作可以在对数时间内完成。这使得优先队列在处理大量数据时具有高效的性能。 总的来说,优先队列是一种非常...
车道Lane包提供队列,优先级队列,堆栈和双端队列数据结构的实现。 它的设计考虑了简单性,性能和并发使用。优先队列Pqueue是堆优先级队列数据结构的实现。 它可以是最大订购量还是最小订购量,是否已同步以及对于...
实现栈的时候有两种思维 1 顺序栈:由数组去实现 存在假溢出问题:里面的元素个没有超过它的最大值,但是看... 因此我们设计顺序队列的时候要设计循环队列:文章说明了循环队列的解决方法 2 链式栈:由链表去实现
1.堆和栈 (1)数据结构的堆和栈 ...由于堆的这个特性,常用来实现优先队列,堆的存取是随意,这就如同在图书馆的书架上取书,虽然书的摆放是有顺序的,但是想取任意一本时不必像栈一样,先取出前面所有
请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。 若队列为空,pop_front 和 max_value 需要返回 -1 示例 1: 输入: ["MaxQueue","push_...
初谈这个话题,相信许多人会有一种似有所悟,但又不敢确定的感觉。没错,这正是因为其中“单调”...它的作用很简单,就是为了维护一组单调数据,让我们在运行的过程中能够快速寻求前k个或后k个中最大或最小的值。 至于
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队...
9.1 单端优先队列和双端优先队列 9.2 左倾树 9.3 二项式堆 9.4 Fibonacci堆 9.5 配偶堆 9.6 对称最小-最大堆 9.7 区间堆 9.8 参考文献和选读材料 第10章 高效二叉查找树 10.1 最优二叉查找树 10.2 AVL树 ...
因为是尾进头出,所以和顺序栈不同的是需要将顺序队列臆造成一个环状的空间,以便在尾部添加满之后从头部空位开始插入。 2、也可以使用数组队列,也就是不能动态增长的顺序队列,这样不需要每次取模最大值来构成环形...
本源码实现了两个类,一个是带有最大值的栈和一个是带有最大值的队列。栈利用了两个C++的stack,队列利用了C++的queue。
栈和队列 ID Title JAVA 备注 1001 设计一个有getMin功能的栈 (☆) 栈 1002 由两个栈组成的队列 (☆☆) 栈、队列 1003 用递归函数和栈操作逆序一个栈 (☆☆) 栈、递归 1004 用一个栈实现另一个栈的排序 (☆) 栈 1005...
美国最大的独立食品连锁企业克罗格(Kroger)2017 年推出了二 维码自助收银,沃尔玛(Walmart)已在美国达拉斯和奥兰多等 地推出没有收银员的购物体验。日本的 JR 东日本公司也在尝试 利用人工智能技术开发无人商店...
1. 树与递归 2. 图的专项训练 3. 栈和队列 4. 最大堆
双端队列-返回滑动窗口的最大值 小顶堆-返回数据流的第k大元素 leetcode建议练习题号: 业界应用 如何实现浏览器的前进后退功能 hash 散列表即键值对的集合,js里常用{ }、new Map()表示 知识点 散列函数与散列表 ...
栈和队列,括号匹配以及素数筛的相关问题。Gcd: int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } 等经典模版。滑动窗口:先加和,后移窗的常见错误, 每次弹出的时候,比较当前要弹出的数值是否等于队列...