java堆栈和队列_java-栈和队列-算法

1，栈的实现

1.1 栈-链表实现

//定义Node类

public classNode {public String data="";

Node next=null;publicNode(){

data="THE-HEAD";

}publicNode(String data){this.data=data;

}

}

View Code

//基础//空？//长度-用成员变量表示//操作//入栈//出栈//返回栈顶元素//遍历

public classLinkedStack {private int length=0;private Node head=newNode();//空？

public booleanisEmpty(){if(length==0)return true;else

return false;

}//入栈

public voidpush(String data){

Node newNode=newNode(data);

newNode.next=head.next;

head.next=newNode;

length++;

}//出栈

publicString pop(){if(length==0){

System.out.println("栈空，无法出栈");return "ERROR-emptyStack";

}else{

Node p=head.next;

head.next=p.next;

length--;returnp.data;

}

}//返回栈顶元素

publicString getTop(){if(length==0){

System.out.println("栈空，无法返回");return null;

}else{returnhead.next.data;

}

}//遍历

public voidprint(){if(length==0)

System.out.println("栈空，无输出");else{

System.out.print("栈： ");

Node p=head;while(p.next!=null){

p=p.next;

System.out.print(p.data+" ");

}

System.out.println();

}

}public static voidmain(String[] asdf){

LinkedStack mystack=newLinkedStack();

System.out.println(mystack.isEmpty());

mystack.pop();

mystack.getTop();

mystack.push("123");

mystack.push("234");

mystack.push("345");

mystack.push("456");

mystack.print();

System.out.println(mystack.isEmpty());

System.out.println(mystack.pop());

mystack.pop();

mystack.print();

}

}

View Code

1.2 栈-数组实现

public classArrayStack {private final int SIZE=30;private int[] stackarray=new int[SIZE];private int top=-1;public void push(intdata){

stackarray[++top]=data;

}public booleanisEmpty(){if(top==-1)return true;else

return false;

}public intpop(){if(top<0){

System.out.println("栈空，无法出栈");returnInteger.MAX_VALUE;

}else{int num=stackarray[top];

top--;returnnum;

}

}public intgetTop(){if(top<0){

System.out.println("栈空，返回失败");returnInteger.MAX_VALUE;

}else{returnstackarray[top];

}

}public voidprint(){if(top==-1)

System.out.println("栈空，无输出");else{

System.out.print("栈： ");int num=top;while(num>=0){

System.out.print(stackarray[num--]+" ");

}

System.out.println();

}

}public static voidmain(String args[]) {

ArrayStack mystack=newArrayStack();

System.out.println(mystack.isEmpty());

mystack.pop();

mystack.getTop();

mystack.push(1);

mystack.push(2);

mystack.push(3);

mystack.push(4);

mystack.print();

System.out.println(mystack.isEmpty());

mystack.pop();

mystack.pop();

mystack.print();

}

}

View Code

2，队列

2.1队列-链表

1 //Node类

2 public classNode {3 public String data="";4 Node next=null;5

6 publicNode(){7 data="THE-HEAD";8 }9 publicNode(String data){10 this.data=data;11 }12 }13

14 //队列类

15

16 public classLinkedQueue {17 private Node Head=newNode();18 private Node Tail=newNode();19 private int length=0;20

21 public booleanisEmpty(){22 return Head.next==null&&Tail.next==null;23 }24 //入队

25 public voidadd(String data){26 Node newNode=newNode(data);27 if(length==0){28 Head.next=newNode;29 Tail.next=newNode;30 length++;31 }else{32 Tail.next.next=newNode;33 Tail.next=newNode;34 length++;35 }36 }37 //出队

38 publicString poll(){39 if(length<1){40 System.out.println("队列空,无法出队");41 return "ERROE-emptyQueue";42 }else if(length==1){43 String data=Head.next.data;44 Head.next=null;45 Tail.next=null;46 length--;47 returndata;48 }49 else{50 Node p=Head.next;51 String data=Head.next.data;52 Head.next=p.next;53 length--;54 returndata;55 }56 }57 //返回队首

58 publicString getHead(){59 if(length==0){60 System.out.println("队空，无队头");61 return null;62 }63 else{64 returnHead.next.data;65 }66 }67

68 //遍历队列

69 public voidprint(){70 if(length==0)71 System.out.println("队空，无输出");72 else{73 System.out.print("队列： Head->");74 Node p=Head;75 while(p.next!=null){76 p=p.next;77 System.out.print(p.data+"->");78 }79 System.out.println("(

83

84 public static voidmain(String args[]) {85 LinkedQueue myQueue=newLinkedQueue();86 System.out.println(myQueue.isEmpty());87 myQueue.getHead();88 myQueue.poll();89

90 myQueue.add("12");91 myQueue.add("23");92 myQueue.add("34");93 myQueue.add("45");94

95 myQueue.print();96

97 myQueue.poll();98 myQueue.poll();99 myQueue.print();100

101 }102

103 }

View Code

2.2队列-数组

循环数组队列，头指向第一个元素，尾指向最后一个元素的下一个

1 //头指向第一个，尾指向最后一个的下一个2 //队空：Head==Tail3 //队满：(Tail+1)%SIZE==Head

4

5 public classArrayQueue {6 private int SIZE=10;7 private int[] queueArray=new int[SIZE];8 private int Head=0;9 private int Tail=0;10

11

12 //空？

13 public booleanisEmpty(){14 if(Head==Tail){15 return true;16 }else

17 return false;18 }19 //返回长度

20 public intlength(){21 if(Head==Tail)22 return 0;23 else if(Head

30 public void add(intdata){31 if((Tail+1)%SIZE==Head)32 System.out.println("队列已满,无法入队");33 else{34 queueArray[Tail]=data;35 Tail=(Tail+1)%SIZE;36 }37 }38 //出队

39 public intpoll(){40 if(Head==Tail){41 System.out.println("队空，无法出栈");42 returnInteger.MAX_VALUE;43 }44 else

45 return Head=(Head+1)%SIZE;46 }47 //返回队首

48 public intgetHead(){49 if(Head==Tail){50 System.out.println("队空，无队首");51 returnInteger.MAX_VALUE;52 }53 else

54 returnqueueArray[Head];55 }56

57 //遍历

58 public voidprint(){59 if(Head==Tail)60 System.out.println("队空，无输出");61 else{62 System.out.print("队： ");63 int head=Head;64 while(Tail!=head){65 System.out.print(queueArray[(head++)%SIZE]+" ");66 }67 System.out.println();68 }69 }70

71 public static voidmain(String args[]) {72 ArrayQueue myQueue=newArrayQueue();73 System.out.println(myQueue.isEmpty());74 myQueue.getHead();75 myQueue.poll();76

77 myQueue.add(12);78 myQueue.add(23);79 myQueue.add(34);80 myQueue.add(45);81 System.out.println("队长 "+myQueue.length());82 myQueue.add(45);83 myQueue.add(45);84 myQueue.add(45);85 myQueue.add(45);86 myQueue.add(45);87 myQueue.add(45);88 System.out.println("队首 "+myQueue.getHead());89 System.out.println("队长 "+myQueue.length());90

91 myQueue.print();92

93 myQueue.poll();94 myQueue.poll();95 myQueue.print();96 }97

98 }

View Code

3，用栈表示队列，用队列表示栈

3.1 栈->队列

①用两个栈，将数据从一个栈的顺序弹出压入另一个栈，刚好顺序相反-----满足队列一端进一端出要求，队列倒序遍历的一种实现方式；

②一个记录stackin记录入队顺序，栈顶当作队尾，另一个stackout记录出队顺序，栈顶当中队首

③要入队时，让数据从stackout弹出，在压进stackin，

1 importjava.util.Stack;2

3 public classStackQueue {4 private Stack stackIn=new Stack<>();5 private Stack stackOut=new Stack<>();6

7 public booleanisEmpty(){8 return stackIn.isEmpty()&&stackOut.isEmpty();9 }10 public void add(intdata){11 if(stackIn.isEmpty()){12 while (!stackOut.isEmpty())13 stackIn.push(stackOut.pop());14 stackIn.push(data);15 }else{16 stackIn.push(data);17 }18 }19 public intlength(){20 if(stackIn.isEmpty())21 returnstackOut.size();22 else

23 returnstackIn.size();24 }25 public intpoll(){26 if(!isEmpty()){27 //stackin,stackOut都是专用的，不像queueStacck一样两个queue等价28 //因为①用两个栈，将数据从一个栈的顺序弹出压入另一个栈，刚好顺序相反-----满足队列一端进一端出要求29 //②用两个队列，因为把数据从一个队列移动到另一个队列顺序不变，所以这两个队列是等价，

30 if(stackOut.isEmpty()){31 //这里是用isempty判空，然后push最后一个，还是用size>1，直接返回popz最后一个，两者时间复杂度？32 //https://blog.caoyu.info/is-empty-size-in-java.html

33 //ConcurrentLinkedQueue如类需要异步求当前size()34 //isempty O(1)35 //size() 通常O(1),有时O(n);

36 while (stackIn.size()>1)37 stackOut.push(stackIn.pop());38 returnstackIn.pop();39 }else{40 returnstackOut.pop();41 }42 }else{43 System.out.println("队空，无出队");44 returnInteger.MAX_VALUE;45 }46 }47 //遍历48 //遍历49 //可正序，也可倒叙

50 public voidprint(){51 if(!isEmpty()){52 if(stackIn.isEmpty()){53 System.out.print("倒序遍历： (队尾)");54 while(!stackOut.isEmpty()){55 int num=stackOut.pop();56 System.out.print(num+" ");57 stackIn.push(num);58 }59 System.out.println();60 System.out.print("正序遍历： (队首)");61 while(!stackIn.isEmpty()){62 int num=stackIn.pop();63 System.out.print(num+" ");64 stackOut.push(num);65 }66 System.out.println();67 }else{68 System.out.print("正序遍历： (队首)");69 while(!stackIn.isEmpty()){70 int num=stackIn.pop();71 System.out.print(num+" ");72 stackOut.push(num);73 }74 System.out.println();75 System.out.print("倒序遍历： (队尾)");76 while(!stackOut.isEmpty()){77 int num=stackOut.pop();78 System.out.print(num+" ");79 stackIn.push(num);80 }81 System.out.println();82 }83 }else

84 System.out.println("队空，无输出");85 }86

87

88

89 public static voidmain(String args[]) {90 StackQueue myQueue=newStackQueue();91 System.out.println(myQueue.isEmpty());92 //myQueue.getHead();

93 myQueue.poll();94

95 myQueue.add(12);96 myQueue.add(23);97 myQueue.add(34);98 myQueue.add(45);99 System.out.println("队长 "+myQueue.length());100 myQueue.print();101 myQueue.add(56);102 myQueue.add(67);103 myQueue.add(78);104 myQueue.add(89);105 myQueue.add(90);106 myQueue.add(01);107 System.out.println("队长 "+myQueue.length());108 myQueue.print();109

110

111 myQueue.poll();112 myQueue.poll();113 System.out.println("队长 "+myQueue.length());114 myQueue.print();115 }116

117 }

View Code

3.2 队列表示栈

①用两个队列，因为把数据从一个队列移动到另一个队列顺序不变，所以这两个队列是等价，

②当要入栈时，将有数据的队列顺序出队进入另一个队列，留下最后一个数据，即栈顶数据，

③入栈直接进入有数据的队列队尾就行了

1 importjava.util.LinkedList;2 importjava.util.Queue;3

4 //始终保持辅助队列为空，不为空为数据队列5 //只有两条队列都空才空

6 public classQueueStack {7 private Queue q1=new LinkedList();8 private Queue q2=new LinkedList();9 public booleanisEmpty(){10 return (q1.isEmpty()&&q2.isEmpty());11 }12 //入栈

13 public void push(inta){14 if(isEmpty())15 q1.add(a);16 else{17 if(q1.isEmpty())18 q2.add(a);19 if(q2.isEmpty())20 q1.add(a);21 }22 }23 //出栈

24 public intpop(){25 if(!isEmpty()){26 if(q1.isEmpty()){27 while(q2.size()>1)28 q1.add(q2.poll());29 returnq2.poll();30 }else{31 while(q1.size()>1)32 q2.add(q1.poll());33 returnq1.poll();34 }35 }else{36 System.out.println("栈空，无出栈");37 returnInteger.MAX_VALUE;38 }39 }40 //返回栈首

41 public intpeek(){42 intnum;43 if(!isEmpty()){44 if(q1.isEmpty()){45 while(q2.size()>1)46 q1.add(q2.poll());47 num=q2.poll();48 q1.add(num);49 returnnum;50 }else{51 while(q1.size()>1)52 q2.add(q1.poll());53 num=q1.poll();54 q2.add(num);55 returnnum;56 }57 }else{58 System.out.println("栈空，无栈头");59 returnInteger.MAX_VALUE;60 }61 }62 //遍历

63 public voidprint(){64 if(!isEmpty()){65 System.out.print("栈： ");66 if(q1.isEmpty()){67 while (!q2.isEmpty()){68 int num=q2.poll();69 System.out.print(num+" ");70 q1.add(num);71 }72 System.out.println();73 }else{74 while (!q1.isEmpty()){75 int num=q1.poll();76 System.out.print(num+" ");77 q2.add(num);78 }79 System.out.println();80 }81 }else

82 System.out.println("栈空，无输出");83 }84

85

86 public static voidmain(String args[]) {87 QueueStack s=newQueueStack();88 s.isEmpty();89 s.peek();90 s.pop();91

92 s.push(5);93 s.push(6);94 s.push(7);95 s.push(8);96 s.print();97

98 System.out.println(s.peek());99 System.out.println(s.pop());100 System.out.println(s.pop());101 s.print();102

103 }104

105

106 }

View Code

4，栈队列相关算法

参考网上帖子

转载：简书ID：@我没有三颗心脏

https://www.jianshu.com/p/5087c751cb42

4.1

①最小堆问题，数据栈+辅助栈，辅助栈负责记录每一个值入栈时，当前数据栈状态得最小值，即每一个数入栈时如果<=辅助栈栈顶值，同时进辅助栈，

②出队时一样与辅助栈栈顶比较，与辅助栈顶相同则辅助栈pop,

③，辅助栈保证栈顶始终是数据栈当前状态下的最小值，

1 importjava.util.Stack;2

3 //入栈4 //空栈加入第一个元素，两个栈都push;5 //栈非空，push时若小于min栈顶元素，min栈也入6 //出栈7 //若data栈顶==min栈顶，双栈出；！=min栈不出

8 public classMinStack {9 private Stack data=new Stack<>();10 private Stack min=new Stack<>();11

12 public booleanisEmpty(){13 returndata.isEmpty();14 }15

16 public void push(inta){17 if(isEmpty()){18 data.push(a);19 min.push(a);20 }else{21 data.push(a);22 if(a<=min.peek())23 min.push(a);24 }25 }26 public voidpop(){27 if(!isEmpty()){28 int a=data.pop();29 if(a==min.peek())30 min.pop();31 }else{32 System.out.println("栈空，出栈失败");33 }34 }35 public intpeek(){36 if(!isEmpty())37 returndata.peek();38 else

39 returnInteger.MAX_VALUE;40 }41 public intgetMind(){42 if(!isEmpty())43 returnmin.peek();44 else returnInteger.MAX_VALUE;45 }46

47 public static voidmain(String args[]) {48 MinStack m=newMinStack();49 m.push(-1);50 m.push(3);51 m.push(-3);52 m.push(5);53 m.push(-2);54 m.push(8);55

56 System.out.println("最小 "+m.getMind());57

58 m.pop();59 System.out.println("最小 "+m.getMind());60 m.pop();61 System.out.println("最小 "+m.getMind());62 m.pop();63 System.out.println("最小 "+m.getMind());64 m.pop();65 System.out.println("最小 "+m.getMind());66 }67

68

69 }

View Code

4.2  括号匹配问题，{} []()<>

左括号直接入栈，遇到右括号，栈顶一定是与之匹配的左括号，是-出栈，不是-直接返回错误

1 //转载：简书ID：@我没有三颗心脏2 //https://www.jianshu.com/p/5087c751cb42

3 importjava.util.Scanner;4 importjava.util.Stack;5

6 public classStack_Use_For {7

8 //LeetCode 相关题目整理9 //20.有效的括号

10 public booleanisRight(String s){11

12 Stack stack=new Stack<>();13 if(s.length()==0)14 return false;15 else{16 for(int i=0;i'&&stack.pop()!='

42

43 }44

45 public static voidmain(String args[]) {46 Stack_Use_For stack=newStack_Use_For();47

48 System.out.println("请输入包含{}[]()<>的字符串");49 Scanner sc=newScanner(System.in);50 String s=sc.nextLine();51

52

53 System.out.println(stack.isRight(s));54

55

56 }57

58

59 }

View Code

4.3 某给定顺序序列入栈的出栈序列问题，比如1234567入栈，5436721是否是出栈序列问题

唉，自己的方法太蠢，233，，思路没问题，实现起来太容易出错，下标很乱

1 //https://www.jianshu.com/p/5087c751cb42

2

3 /*

4 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假5 * 设压入栈的所有数字均不相等。例如，序列{1,2,3,4,5}是某栈的压栈序列，序列{4,5,3,2,1}是该压6 * 栈序列对应的一个弹出序列，但{4,3,5,1,2}就不可能是该压栈序列的弹出序列。7

8 */

9

10 /**

11 * 思路1：从前往后遍历弹出序列，求出弹出值入序的下标x，在求出入序列表中在x之前的元素的出序下标数组12 * ，这个数组是降序的，不是降序的则错误，因为靠近X 的先弹出。13 *14 * 前提：序列元素不能重复15 */

16

17 /**

18 * 更正思路119 * 思路1错了一部分，求出第一个值后，若没返回false则证明x之前的元素顺序都对，则就不用考虑这些元素了，即把1-x之间的元素从out20 * 中删除(in也要删除)，不是从前往后遍历，而是跳着遍历，21 *22 *23 * 不能删除，删除后后面的下标就乱了2333，，还是得用特殊字符代替，24 *25 *26 * * (我们拿到输出序列往外很关注第一个值，比如1234567入栈，如果出栈序列第一个是5，那么4321的出栈顺序就限制住了，27 * * 4要在321前面中间肯有其他值比如67，只要是4在出序中的位置下标比3小，3比2小，以此类推，如果4有差错，直接返回错误28 * * ，如果没错，出栈序列中54321(5是第一个，下标肯定比4321小)就不用遍历了，已经确认没问题了，可以标记一下如替换“-”，接着拿29 * * 下一个非“-”当作“第一个”继续，)30 *31 *32

33 */

34 importjava.util.Stack;35 public classStack_Out_Order {36 //工地英语，是否是in序的out37 //这里用String返回值，方便定位哪里出了问题，到底是哪里下标设计会溢出，

38 publicString isOutOfIn(String in,String out){39 if(out.length()!=in.length())40 return "false1";41 else{42 //遍历出序的值

43 for(int i=0;i

46 int index=findIndex(curChar,in);47 //curChar不在入序

48 if(index==Integer.MAX_VALUE)49 return "false2";50 //找出入序中在index之前的元素，并求他们在出序中的位置

51 int indexarry=Integer.MAX_VALUE;//保证其比下一个index大即可，不需要存数组

52 for(int j=0;jindexarry){59 return "false3";60 }61 else{62 indexarry=index2;63

64 //删除ste指定index上的char;

65 out=out.substring(0,index2)+"_"+out.substring(index2+1,out.length());66 int index3=findIndex(curChar2,in);67 in=in.substring(0,index3)+"_"+in.substring(index3+1,in.length());68

69 }70 }71 }72 //把第一个也删掉才对

73 out=out.substring(0,i)+"_"+out.substring(i+1,out.length());74 in=in.substring(0,index)+"_"+in.substring(index+1,in.length());75

76 }77 //遍历完无返回false,即true;

78 return "true";79 }80

81 }82 //假设序列中无重复值，

83 public int findIndex(charc,String in){84 for(int i=0;i

90 }91

92

93

94

95 //看了原博主的方法，还标准方法简单，啊啊啊

96 public booleanisOutOfIn2(String in,String out){97 Stack stack=new Stack<>();98 int indexin=0;99 int indexout=0;100

101 while (indexout

115 public static voidmain(String args[]) {116 String in="1234567";117 String out1="5432167";118 String out2="5431267";119 String out3="1234567";120 String out4="2367541";121 String out5="7654321";122 String out6="7564321";123 Stack_Out_Order s=newStack_Out_Order();124 System.out.println(in+" "+out1+" "+s.isOutOfIn(in,out1));125 System.out.println(in+" "+out2+" "+s.isOutOfIn(in,out2));126 System.out.println(in+" "+out3+" "+s.isOutOfIn(in,out3));127 System.out.println(in+" "+out4+" "+s.isOutOfIn(in,out4));128 System.out.println(in+" "+out5+" "+s.isOutOfIn(in,out5));129 System.out.println(in+" "+out6+" "+s.isOutOfIn(in,out6));130 System.out.println();131

132 System.out.println(in+" "+out1+" "+s.isOutOfIn2(in,out1));133 System.out.println(in+" "+out2+" "+s.isOutOfIn2(in,out2));134 System.out.println(in+" "+out3+" "+s.isOutOfIn2(in,out3));135 System.out.println(in+" "+out4+" "+s.isOutOfIn2(in,out4));136 System.out.println(in+" "+out5+" "+s.isOutOfIn2(in,out5));137 System.out.println(in+" "+out5+" "+s.isOutOfIn2(in,out6));138 }139

140 }

View Code