java算法:堆栈ADT及实例
在支持插入和删除数据项集的数据类型中,最重要的数据类型是堆栈。
堆栈:是由两个基本操作构成的ADT,插入(或压入)一个新项,以及删除(或弹出)最近插入的数据项。
例1:堆栈ADT接口
- publicinterfaceIIntStack{
-
intintStack(intvalue);
-
intempty();
-
voidpush(intvalue);
-
intpop();
- }
public interface IIntStack {
int intStack(int value);
int empty();
void push(int value);
int pop();
}
例2:中缀法:5*(((9+8)*(4*6))+7),后缀法:5 9 8 + 4 6 * * 7 + *,前缀法:* + 7 * + 9 8 * 4 6 5
后缀计法和相关的压入栈操作应用到计算机中。如:
5 5
9 5 9
8 5 9 8
+ 5 17
4 5 17 4
6 5 17 4 6
* 5 17 24
* 5 408
7 5 408 7
+ 5 415
* 2075
- publicclassPostfix{
-
-
publicstaticvoidmain(String[]args){
-
char[]a="598+46**7+*".toCharArray();
-
intN=a.length;
-
IIntStacks=newIntStackImpl();
-
for(inti=0;i<N;i++){
-
if(a[i]=='+'){
- s.push(s.pop()+s.pop());
- }
-
if(a[i]=='*'){
- s.push(s.pop()*s.pop());
- }
-
if((a[i]>='0')&&(a[i]<='9')){
-
s.push(0);
- }
-
while((a[i]>='0')&&(a[i]<='9')){
-
s.push(10*s.pop()+(a[i++]-'0'));
- }
- }
- System.out.println(s.pop());
- }
- }
public class Postfix {
public static void main(String[] args) {
char [] a = "598+46**7+*".toCharArray();
int N = a.length;
IIntStack s = new IntStackImpl();
for(int i = 0; i < N; i++){
if(a[i] == '+'){
s.push(s.pop() + s.pop());
}
if(a[i] == '*'){
s.push(s.pop() * s.pop());
}
if((a[i] >= '0') && (a[i] <= '9')){
s.push(0);
}
while((a[i] >= '0') && (a[i] <= '9')){
s.push(10 * s.pop() + (a[i++]-'0'));
}
}
System.out.println(s.pop());
}
}
例3:中缀到后缀的转换
- publicclassInfixToPostfix{
-
-
publicstaticvoidmain(String[]args){
-
char[]a="598+46**7+*".toCharArray();
-
intN=a.length;
-
IIntStacks=newIntStackImpl();
-
for(inti=0;i<N;i++){
-
if(a[i]==')'){
-
System.out.println(s.pop()+"");
- }
-
if((a[i]=='*')||(a[i]=='+')){
- s.push(a[i]);
- }
-
if((a[i]>='0')&&(a[i]<='9')){
-
System.out.println(a[i]+"");
- }
- }
-
System.out.println("");
- }
- }
public class InfixToPostfix {
public static void main(String[] args) {
char [] a = "598+46**7+*".toCharArray();
int N = a.length;
IIntStack s = new IntStackImpl();
for(int i = 0; i < N; i++){
if(a[i] == ')'){
System.out.println(s.pop() + " ");
}
if((a[i] == '*') || (a[i] == '+')){
s.push(a[i]);
}
if((a[i] >= '0') && (a[i] <= '9')){
System.out.println(a[i] + " ");
}
}
System.out.println(" ");
}
}
栈的ADT实现
主要:数组和链表
例3:堆栈的数组实现
- classIntStack{
-
privateint[]s;
-
privateintN;
-
IntStack(intmaxN){
-
s=newint[maxN];
-
N=0;
- }
-
booleanisEmpty(){
-
return(N==0);
- }
-
voidpush(intitem){
- s[N++]=item;
- }
-
intpop(){
-
returns[--N];
- }
- }<SPAN></SPAN>
class IntStack{
private int[] s;
private int N;
IntStack(int maxN){
s = new int[maxN];
N = 0;
}
boolean isEmpty(){
return (N == 0);
}
void push(int item){
s[N++] = item;
}
int pop(){
return s[--N];
}
}
例4:堆栈的链表实现
- classintStack{
-
privateNodehead;
-
privateclassNode{
-
intitem;
- Nodenext;
-
Node(intitem,Nodenext){
-
this.item=item;
-
this.next=next;
- }
- }
-
intStack(intmaxN){
-
head=null;
- }
-
booleanisEmpty(){
-
return(head==null);
- }
-
voidpush(intitem){
-
head=newNode(item,head);
- }
-
intpop(){
-
intv=head.item;
- Nodet=head.next;
- head=t;
-
returnv;
- }
- }
class intStack{
private Node head;
private class Node{
int item;
Node next;
Node(int item, Node next){
this.item = item;
this.next = next;
}
}
intStack(int maxN){
head = null;
}
boolean isEmpty(){
return (head == null);
}
void push(int item){
head = new Node(item, head);
}
int pop(){
int v = head.item;
Node t = head.next;
head = t;
return v;
}
}
客户程序并不关心在数组实现和链表实现中栈的项是否按不同的顺序存放的。实现可自由地使用任何数据结构,只要它能保持抽象堆栈的假象。链表实现能产生栈可以无限增长的假象。而在实际中是不可能的:到达一定时候,当无法满足请求更多内存的要求时,就会抛出异常。
一般实现:定义一个接口,并实现object类型的堆栈,
- Stacks=newStack(N);
- s.push(a);
- s.push(b);
- a=(Item)s.pop();
- b=(Item)s.pop();
Stack s = new Stack(N);
s.push(a);
s.push(b);
a = (Item) s.pop();
b = (Item) s.pop();
例5:一般堆栈
- classStack{
-
privateObject[]s;
-
privateintN;
-
Stack(intmaxN){
-
s=newObject[maxN];
-
N=0;
- }
-
booleanisEmpty(){
-
return(M==0);
- }
-
voidpush(Objectitem){
- s[N++]=item;
- }
- Objectpop(){
- Objectt=s[--N];
-
s[N]=null;
-
returnt;
- }
- }
class Stack{
private Object[] s;
private int N;
Stack(int maxN){
s = new Object[maxN];
N = 0;
}
boolean isEmpty(){
return (M == 0);
}
void push(Object item){
s[N++] = item;
}
Object pop(){
Object t = s[--N];
s[N] = null;
return t;
}
}
例6:整数栈的适配类
- classIntStack{
-
privateStacks;
-
intStack(intmaxN){
-
s=newStack(maxN);
- }
-
booleanisEmpty(){
-
returns.isEmpty();
- }
-
voidpush(intitem){
-
s.push(newInteger(item));
- }
-
intpop(){
-
return((Integer)s.pop()).intValue();
- }
-
- }
class IntStack{
private Stack s;
intStack(int maxN){
s = new Stack(maxN);
}
boolean isEmpty(){
return s.isEmpty();
}
void push(int item){
s.push(new Integer(item));
}
int pop(){
return ((Integer)s.pop()).intValue();
}
}
创建新的ADT
设计一个新的ADT:开发解决应用问题的客户程序,定义接口,验证ADT是否更容易实现客户程序,再考虑是否合理、效率实现ADT中的操作,如果不能,找到原因进行更改。多次之后,改进的客户程序和ADT,采取策略冻结接口。
例7:等价关系ADT接口,连通性问题:初始化一个抽象数据结构来跟踪给定节点数之间的联系,判断两个给定节点是否连通,并把两个节点连起来,以后就认为它们是连通的。
- classUF{
-
UF(intN);
-
booleanfind(intx;inty);
-
voidunite(intx;inty);
- }
class UF{
UF(int N);
boolean find(int x; int y);
void unite(int x; int y);
}
例8:等价关系ADT的客户
- classEquivalence{
-
publicstaticvoidmain(String[]args){
-
intp,q,N=100;
-
UFinfo=newUF(N);
-
for(In.init();!In.empty();){
- p=In.getInt();q=In.getInt();
-
if(!info.find(p,q)){
- info.unite(p,q);
-
System.out.println(p+"-"+q);
- }
- }
- }
- }
class Equivalence{
public static void main(String [] args){
int p,q, N = 100;
UF info = new UF(N);
for(In.init(); !In.empty();){
p = In.getInt(); q = In.getInt();
if(!info.find(p,q)){
info.unite(p,q);
System.out.println(p + "-" + q);
}
}
}
}
例9:等价关系ADT实现:加权快速合并实现接口:
- privateint[]id,sz;
-
privateintfind(intx){
-
while(x!=id[x]){
- x=id[x];
- }
-
returnx;
- }
-
UF(intN){
-
id=newint[N];
-
sz=newint[N];
-
for(inti=0;i<N;i++){
- id[i]=i;
- sz[i]=i;
- }
- }
-
booleanfind(intp,intq){
-
return(find(p)==find(q));
- }
-
voidunite(intp,intq){
-
inti=find(p),j=find(q);
-
if(i==j){
-
return;
- }
-
if(sz[i]<sz[j]){
- id[i]=j;sz[j]+=sz[i];
-
}else{
- id[j]=i;sz[i]+=sz[j];
- }
- }
private int [] id, sz;
private int find(int x){
while(x != id[x]){
x = id[x];
}
return x;
}
UF(int N){
id = new int[N];
sz = new int[N];
for(int i = 0; i < N; i++){
id[i] = i;
sz[i] = i;
}
}
boolean find(int p, int q){
return (find(p) == find(q));
}
void unite(int p, int q){
int i = find(p), j = find(q);
if(i == j){
return;
}
if(sz[i] < sz[j]){
id[i] = j; sz[j] += sz[i];
}else{
id[j] = i; sz[i] += sz[j];
}
}
比较:把解决高层(连通性)问题的任务和解决低层(合并-查找)的问题分开了,从而使我们能独立解决这两个问题;为我们提供了把解决该问题的不同算法和数据结构进行比较的自然方式;通过该接口定义了一个方法来检查软件是否按所期望的操作;为我们提供了一种更新的表示(新数据结构或新算法)而根本不需要改变客户程序的方法;为我们提供了一个能用来构建其他算法的抽象结构。
注意:使用抽象类或接口会产生运行时开销,每个抽象方法的调用需要跟踪表中对方法的一个引用。算法与数据结构经常用于系统中关键的性能部分,不希望以此为代价获得抽象类和接口的灵活性。
分享到:
相关推荐
算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...
android ADT-23.0.7,用于解决无法显示手机布局的错误: This version of the rendering library is more recent than your version of ADT plug-in. Please update。 因为上传文件大小限制,分为了3部分下载,请...
Homebridge-adt-smart-security 适用于ADT Smart Security的homebridge-plugin( )特征: 获取并设置安全系统状态(“回家”,“离开”,“关闭”) 查看电池电量(电池电量不足警告) 支持接触式传感器安装:1....
用于家庭桥的ADT脉冲 这是ADT Pulse用户,允许房主通过HomeKit控制其安全系统并查看传感器状态。 该API依赖于ADT Pulse Web门户(由Icontrol One提供)。 要使用此插件,您需要遵循以下三个简单步骤: 运行npm ...
Android安卓java开发组件ADT(免费) 导入myeclipse或者eclipse 安装即可使用
* 二叉树节点ADT接口 */ package dsa; public interface BinTreePosition extends Position { //判断是否有父亲(为使代码描述简洁) public boolean hasParent(); //返回当前节点的父节点 public ...
安装Eclipse插件:ADT.
android windows集成开发环境
修改后的ADT 24.0.2 支持 java 1.8,Elipse 安卓开发报如下错误:Android requires compiler compliance level 5.0 or 6.0. Found '1.8' instead. 下载解压出jar包,替换到Eclipse安装目录下plugins文件夹内即可
android windows集成开发环境
ADT 24.0.2 兼容 java 1.8 com.android.ide.eclipse.adt-24.0.2.1647631 eclipse ADT支持1.8
本文作者在帮助用户集成AndroidSDK的过程中,发现很多遗留项目依旧没有从ADT迁移过来,依然有很多用户对AndroidStudio怀着恐惧与不信任。由此,撰写了系列博文,希望能够帮助更多的开发者拥抱变化。多年前央视有一套...
android+eclipse+ADT-24.2.0-20160729。android开发 eclipse中的adt最新,ADT-24.2.0-20160729。百度网盘下载。
Java算法第一年 在帝国理工学院计算一年级期间教授的 Java 算法集合 写的算法: 树木AVL 堆 未写的算法: 树木 红黑 二分查找 堆栈 队列优先队列 列表链表
二叉树 二叉树ADT的实现
安卓ADT必不可缺少的工具,主要为Eclipse插件,Eclipse扩展安卓应首先应当安装,必不可少
ADT_后端ABAP开发工具(ADT)REST端点的后端实现。 需要这些端点来将连接到abapgit后端。 SAP还发布了SAP Cloud Platform ABAP环境产品中提供的。 高度实验要求安装了源代码的版本(仅报告无效) NW≥750 为了满足...
安卓开发集成环境 官网下载的 32位 分享出来 包含eclipse和SDK 可以直接使用 分10个部分下载
书名:Java中的数据结构和算法变得简单 国际标准书号(ISBN):9781466304161 [用于印度] / 9781468101270 [印度除外] 保修:本软件按“原样”提供,不提供任何保修; 甚至没有对适销性或特定用途适用性的暗示保证...
This version of ADT is designed for use with SDK Tools r24.1.2. If you haven't already installed SDK Tools r24.1.2 into your SDK, use the Android SDK Manager to do so. General Notes: Fixed issues with...