package org.jf.alg;
/**
* * 算法描述:
一个栈stack,具有push和pop操作,其时间复杂度皆为O(1)。
设计算法max操作,求栈中的最大值,该操作的时间复杂度也要求为O(1)。
可以修改栈的存储方式,push,pop的操作,但是要保证O(1)的时间复杂度,空间时间复杂度无要求。
链表存储, 当然数组存储也可以
* @author junfeng.chen
*
*/
public class Pstack<T extends Comparable> {
private Node head;
private int size ;
public void push(T data)
{
Node node = new Node();
node.data = data;
if(head==null)
{
head = node;
head.max = data;
}else
{
if(head.max.compareTo(data)>0)
node.max = head.max;
else
node.max = data;
node.next = head;
head = node;
}
size++;
}
public T pop()
{
if(head==null)
throw new RuntimeException("Stack is empty");
T data = head.data;
if(size==1)
head = null;
else
head = head.next;
size --;
return data;
}
public boolean isEmpty()
{
return size==0;
}
public int size()
{
return size;
}
public T peek()
{
if(size==0)
return null;
return head.data;
}
public T peekMax()
{
if(size == 0)
return null;
return head.max;
}
class Node
{
T data;
T max;
Node next;
}
}
分享到:
相关推荐
本程序包含9个函数: 1)主函数main( ) 2)初始化顺序栈InitStack ( ) 3)入栈Push ( ) 4)出栈 Pop( ) 5)获取栈顶元素 GetTop( ) 6)遍历顺序表 OutStack( ) 7)置空顺序表 setEmpty( ) 8)判断圆括号是否正确...
1. 请创建一个抽象类DataStructure,该类包括下面的成员变量和成员函数: 1) 一个成员变量len,表示里面的元素个数最大值 2) 构造函数DataStructure(int l),将len初始化为0 3) 虚析构函数~DataStructure() 4) ...
本文实例为大家分享了C语言利用模板实现简单的栈类(数组和单链表),供大家参考,具体内容如下 主要的功能是实现一个后进先出的列表,有入栈、出栈、返回大小、判空等基本功能 #pragma once using namespace std;...
对于可在当前源文件以外使用的函数,应该在一个头文件中说明,要使用这些函数的源文件要包含这个头文件 static全局变量与普通的全局变量有什么区别:static全局变量只初使化一次,防止在其他文件单元中被引用; ...
1.类头定义包含的四个部分分别为:访问控制修饰符、类名说明、父类名说明和接口名的说明,它们中的任何一个都是不能缺少的。 2.在 Applet 的坐标系中,(0,0) 代表输出窗口左上角的象素点。 3.应用程序一定要有main...
代码块 :包含多条可执行的语句 2、函数的声明与调用 1、普通函数 语法: function 函数名(){ 语句块; } 调用:在JS中任何的合法位置处,都可以通过 函数名() 的方式进行调用 练习: 1、声明一个函数,...
这上传的资源中包含一套我工作中常用的模板库,及不需要MFC支持的excel操作接口,导出函数调用栈(dump stack)接口,可以直接用VS2008运行TestCodeLib.sln来根据unit test来了解用法。 ⑴ 需求(requirements) 重量级...
B. 球最大值函数max:通过单链表的一趟遍历,在单链表中确定值最大的结点; C. 统计函数number:统计单链表中具有给定值x的所有元素数量; D. *建立函数create:根据一维数组a[n]建立一个单链表,使...
(1)针对多窗口类浏览器模式问题,指出并分析了该问题存在的原因,利用Activity的运行机制,通过Fragment栈对主要模块的Webview进行管理,实现对不同模块之间切换的控制。 (2)针对跨域数据交互问题,指出并分析了...
ArrayList是基于串联实现的线性表,没有最大容量限制(实际上有,是Integer.MAX_VALUE),可扩容。LinkedList是基于串联实现的线性表(双向链表),没有最大容量限制。 LinkedList还实现了Deque接口,可以作为单向...
IoData池采用原子函数InterlockedCompareExchange来操作进出栈。HndData采用单向FIFO双锁并发链表来管理出入列操作。其他小内存需求的均采用静态数组或new操作。 五、内存需求 每个IoData等于一个分页内存大小,...
IoData池采用原子函数InterlockedCompareExchange来操作进出栈。HndData采用单向FIFO双锁并发链表来管理出入列操作。其他小内存需求的均采用静态数组或new操作。 五、内存需求 每个IoData等于一个分页内存大小,...
答:Class可以被实例化,属于引用类型,是分配在内存的堆上的,Struct属于值类型,是分配在内存的栈上的. [Page] 26.根据委托(delegate)的知识,请完成以下用户控件中代码片段的填写: namespace test { public ...
本书是第II卷,以开发人员在项目开发中经常遇到的问题和必须掌握的技术为中心,介绍了应用Java进行桌面程序开发各个方面的知识和技巧,主要包括Java语法与面向对象技术、Java高级应用、窗体与控件应用、文件操作...
outputMax.java 求两个数中的最大数 overflowExample.java 演示溢出 precedence.java 演示自加运算符的优先级 primeNumber.java 输出100-200之间的所有素数 ranking.java 评定成绩等级 rankingBySwitch.java ...
1. 对一个算法的评价,不包括如下( )方面的内容。 A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 2. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( )。 A. p->next=HL->next; ...
在文件的最后加入Nand Flash的初始化函数,该函数在后面Nand Flash的操作都要用到。 u-boot运行到第2阶段会进入start_armboot()函数。其中nand_init()函数是对nand flash的最 初初始化函数。nand_init()函数在两个...