`
easyhaohao
  • 浏览: 13697 次
  • 性别: Icon_minigender_1
  • 来自: 上海
最近访客 更多访客>>
社区版块
存档分类
最新评论

栈实现队列(维护最大值)

阅读更多
package alogrithm;

import java.util.EmptyStackException;

public class MyStack {
	
	private int stackTop ;
	
	private int maxStackItemIndex ;
	
	private final int MAX = 20;
	
	private int data[];
	
	private int nextMaxItem[];
	public MyStack(){
		stackTop = -1;
		maxStackItemIndex = -1;
		data = new int[MAX];
		nextMaxItem  = new int[MAX];
	}
	
	public void push(int x){
		stackTop ++;
		if(stackTop>=MAX)
			;
		else{
			data[stackTop] = x;
			if(x > max()){
				nextMaxItem[stackTop] = maxStackItemIndex;
				maxStackItemIndex = stackTop;
			}
			else
				nextMaxItem[stackTop] = -1;
		}
	}
	
	public int pop(){
		int ret;
		if(stackTop<0)
			throw new EmptyStackException();
		else{
			ret = data[stackTop];
			if(stackTop==maxStackItemIndex){
				maxStackItemIndex = nextMaxItem[stackTop];
			}
			stackTop--;
		}		
		return ret;
	}
	
	public boolean isEmpty(){
		return stackTop==-1?true:false;
	}
	
	public int max(){
		if(maxStackItemIndex >=0)
			return data[maxStackItemIndex];
		else
			return Integer.MIN_VALUE;
	}
}



package alogrithm;

public class MyQueue {
	
	private MyStack stackA;
	private MyStack stackB;
	
	
	public MyQueue(){
		stackA = new MyStack();
		stackB = new MyStack();
	}
	
	
	public int maxValue(int x,int y){
		return x>y?x:y;
	}
	
	public int max(){
		return maxValue(stackA.max(), stackB.max());
	}
	
	public void enQueue(int x){
		stackA.push(x);
	}
	
	public int Dequeue(){
		if(stackA.isEmpty()){
			while(!stackB.isEmpty())
				stackA.push(stackB.pop());
		}
		
		return stackA.pop();
	}
}
分享到:
评论

相关推荐

    数据结构 第三章 栈与队列 数据结构 第三章 栈与队列

    数据结构中的栈与队列是两种非常...学习栈和队列,重点在于理解它们的特点,掌握不同存储结构下的基本操作实现,以及在实际问题中如何选择合适的数据结构。熟练运用栈和队列,能够有效提高编程效率和解决问题的能力。

    04-栈和队列-21

    通过维护一个辅助栈heap,每次压入元素时更新heap中的最大值,这样可以在O(1)的时间复杂度内获取到栈内的最大值。 接着,介绍了如何使用两个栈来模拟一个队列,这通常称为“双栈模拟队列”。队列是一种先进先出...

    数据结构栈和队列.ppt

    总结,栈和队列作为基本数据结构,在程序设计和算法实现中扮演着重要角色。理解它们的性质和操作,对于编写高效的代码至关重要。通过熟练掌握栈和队列,可以解决多种复杂问题,如图形遍历、任务调度和缓存管理等。在...

    第3章_栈和队列.zip

    - 栈的变种:最小栈(每次push新元素时,同时维护一个辅助栈保存当前栈中的最小元素),最大栈等。 - 队列的变种:优先队列(根据优先级决定元素出队顺序,如最小堆实现的优先队列)。 理解并熟练掌握栈和队列的...

    第3章栈和队列第8讲-小结.pptx

    栈通常用于实现递归、函数调用、表达式求值等场景。对于题目中提到的Catalan数,它与栈有关,是一种组合数学的概念,在计算特定序列的个数时会用到。 栈的实现通常有两种方式:顺序栈和链栈。顺序栈通常使用数组...

    第三章 栈和队列(1).pdf

    随着元素的入栈和出栈,top的值相应地增加或减少,直到达到数组的最大索引值表示栈满,此时top等于数组的最大索引,而在栈为空时,top的值为0。链栈则通过链表实现,每个节点包含数据域和指向下一个节点的指针,使得...

    单调栈和单调队列.pdf

    - **解法:**维护两个单调队列,一个用于计算最大值,另一个用于计算最小值。通过在队尾入队新元素时保持队列的单调性,即可在O(n)时间内解决问题。 **实现代码片段:** ```cpp void get_min() { deque&lt;int&gt; q; ...

    线性结构- 单调栈与单调队列.rar

    1. 滑动窗口最大值/最小值:在给定数组和窗口大小的情况下,单调队列可以帮助我们动态维护窗口内的最大值或最小值,而无需遍历整个数组。 2. 二叉树的最近公共祖先(LCA)问题:在某些情况下,单调队列可以辅助处理...

    栈队列堆试题.pdf

    3. **堆**:堆是一种特殊的树形数据结构,分为最大堆和最小堆,其根节点的值总是大于或小于所有子节点的值。在"tallest"和"juice"题目中,都可以使用最大堆来解决问题。"tallest"题目中,可以维护一个最大堆来快速...

    队列 堆 栈 堆栈的区别

    堆常用于实现优先队列。 2. **作为内存管理的堆:**指在程序运行期间动态分配的内存空间。堆上的内存分配通常通过函数如 `malloc`(C语言)、`new`(C++和Java)来进行。堆内存由操作系统管理,并且通常比栈内存...

    基础数据结构(简单的数据结构,主要有链表、栈、队列以及常见的排序算法).pdf

    栈在编程中有着广泛的应用,如递归、表达式求值和回溯算法等。 队列是一种“先进先出”(FIFO)的数据结构,类似现实生活中的排队。队列的基本操作包括入队(在队尾添加元素)和出队(移除队首元素)。队列常用于...

    CJ2-05-数据结构-单调栈和单调队列.pdf

    - 例如,在给定一个长度为\(k\)的滑动窗口内寻找最大值的问题中,单调队列可以保证队列头部始终是最优解。 **单调队列的维护**: - **单调递增队列**:当新元素\(x\)入队时,若队尾元素小于等于\(x\),则队尾元素出...

    数据结构队列用C语言描述.rar

    当队尾达到数组最大值时,它会回到数组的起始位置,形成一个循环。 3. **链表实现**:使用链表可以更灵活地处理队列的动态扩展。每个节点包含元素和指向下一个节点的指针,队首和队尾由两个指针维护。 ### 四、...

    栈的基本操作与原理以及内容

    - **撤销操作**:许多软件应用提供撤销功能,这通常通过维护一个操作历史的栈来实现。 #### 实验中的线性表与栈的关系 虽然给定的实验报告专注于线性表的基本操作,但栈本身也是一种特殊的线性表,其中只允许在表的...

    RE_栈1

    【栈在括号生成问题中的应用】 在编程中,栈是一种非常重要的数据结构,它...以上就是关于栈在括号生成、最大矩形、最小栈、双栈队列和去除重复字符等问题中的应用,这些例子充分展示了栈在解决实际问题中的强大能力。

    浅谈单调队列、单调栈

    单调队列和单调栈是两种在算法中常用于优化计算效率的数据结构,它们的主要功能是维护一个单调递增或递减的数据序列,并能快速获取序列中的最大值或最小值。这两种数据结构虽然名称不同,但核心思想相似,都是基于...

    数据结构第4章复习重点.doc

    总的来说,本章复习的重点在于理解栈、队列和优先级队列的概念、特点、操作及其应用,并能够熟练地实现它们在不同存储结构下的操作。同时,掌握中缀表达式到后缀表达式的转换方法,以及如何利用这些数据结构解决实际...

    数据结构(严蔚敏)各算法的c语言实现

    堆通常用于优先队列的实现,分为最大堆和最小堆,C语言中可通过数组来模拟堆结构。 图是另一类非线性数据结构,由顶点和边构成。图的C语言实现可以使用邻接矩阵或邻接表。邻接矩阵用二维数组表示任意两个顶点间是否...

    堆栈的基本操作、队列的基本操作

    这可能涉及将这些数据结构应用于特定的算法或系统设计,例如,堆可以用于实现高效的排序算法(如堆排序),队列可以用于模拟打印任务或网络数据包的传输。 总的来说,理解和熟练掌握堆栈和队列的基本操作是成为优秀...

Global site tag (gtag.js) - Google Analytics