% j1 P9 q% f" X& Y; E5 ]
! b' o& Q) b2 I: M
. k7 l# I7 p- K6 F4 c+ }# T 二、 用数组实现栈1、栈的接口定义 / v* [9 V3 a' ?9 v/**# p4 V7 q) s' ~$ N+ b
* 定义栈的接口 , p5 V/ X: r% O, x * 3 g: C3 Q# S5 x& J4 e' k7 z$ M * @Author zhuhuix + B- Q( x9 [9 q0 B * @date 2020-05-01 / ], ]8 O3 F2 l* S */$ \2 M3 R3 `9 ]# {
public interface Stack { ; J' b2 N; o$ a7 @5 \: P% [ /** 6 K4 ?% G5 V) _ * 入栈 ) p1 ~1 G6 l! Q$ N$ \; r# i2 o * @param object 入栈元素 ; P7 J0 {/ ]* Y; ]3 n2 W' a- Y */ , }+ f3 q4 g: a* i% N+ ]1 ^, X* i void push(Object object); k0 F4 a; N4 P& C2 v
. ^4 ?+ s+ W0 ^ H) z, I
/** ; F& |/ T- H2 A) B- h * 出栈 5 o& G0 }: K# s% g9 ^7 X4 T H/ T: O * @return 出栈元素 5 z2 D9 {+ u# r- l' a9 W* W9 h: l */ ' [: |, A7 |. P9 X Object pop();6 h4 `. u0 N$ M" E# K
0 h+ ?5 A+ b) }5 `) ~% b) l$ c /**( |$ A3 [# O! M* I$ v. n
* 获取元素个数 $ G0 Q% K, P4 [7 T) F' M/ \ * @return 元素个数 + ^/ q+ L5 @" B! M */ ) k4 |# \ S0 U. p int getElementCount();& | W' c1 q4 r% n/ c
; A V/ v, \$ f5 t4 h /**( E4 }; x+ w% y; m+ O' V1 d0 \
* 遍历栈的元素( S) ?) f# ^% g# R$ I
*/ 7 [& f/ |1 A; p void traverse(); ( x8 r/ k$ d) N+ e6 s 9 C# C5 t: v0 Z. f7 `}& v; E4 V0 q3 c0 T 2、栈的接口实现& s" R2 L7 G6 N0 u2 }( H
/**$ U. ]3 e5 y& t8 r
* 栈的接口实现 ( R/ Q: H6 ^% M( f- v% Z/ Y *7 M6 W5 G8 G% T- _
* @author zhuhuix: v1 N* H) v4 ]( V
* @date 2020-05-019 o1 n! P1 p" I" }7 t8 w! n
*/1 P) P1 G* E$ @9 h
public class StackImpl implements Stack {6 L$ F7 j9 j/ }& j
2 C. N; z) c: Y
protected Object[] element; j" A! \9 j+ R
( a, J0 C/ N4 x0 v2 Y% w f protected int elementCount;; k3 e: T1 C1 J5 j; n$ o9 a
3 R5 ]( h( I, ]3 S9 o9 N private int defaultSize = 16;7 i5 R( E8 F1 ~$ n u2 ^
" }. Z/ D! Z5 Y
private int maxSize;* ^8 f. D! W' z. E
* A; V: b* A( n e7 D; \2 v
StackImpl() {# g9 n" D8 g- w3 ]0 X; V3 A6 X0 ~$ @
element = new Object[defaultSize];. S0 W I2 e) f: ?9 ]
maxSize = defaultSize;! h" e' K# ]0 R7 Y
} " S9 z9 c0 U7 q4 Y, W! H2 G" M; l: \- m( R; z2 V& x
StackImpl(int size) {% c6 g7 P2 t% Z8 g; i
element = new Object[size]; : M* N( v& [- m% C+ C, x) T c% D maxSize = size;/ F' M6 a [9 ^
} [. m" Q- c! x% h' Q1 B3 c
1 G: Q4 X1 A9 F; Y# B @Override: ]# x% U- \4 t$ ]9 Y8 A6 d% a: Z
public void push(Object object) { $ E2 Y% o( W% r& d3 C }* i: _ //如果元素个数已经达到数组的最大个数,则进行扩容6 T9 r6 y( [) a
if (elementCount == maxSize) {8 @& k/ ?/ p5 w% j
element = Arrays.copyOf(element, elementCount + defaultSize); ; I5 f! j/ I# V }9 f. F } , l( K* [0 ]: K% k. L6 A4 K$ { element[elementCount++] = object;9 T) F& S8 H+ t# j* ?
: H5 `. M7 c; A: p
}5 B/ V, F" k# |' V7 U! j6 ^
// 本代码未实现数组的自动缩小,具体方法可参考JDK9 L% p+ p" V6 e1 _
@Override ' `; p% S# K2 V/ D public Object pop() { " a6 I% ]& o, \ if (elementCount == 0) { 3 p1 `. ?4 X: z4 J4 n* U6 ?8 I throw new ArrayIndexOutOfBoundsException("栈中无元素"); ) M. ~; M6 A L6 d* j1 m }' R, _3 I" k; t, M# {- E5 w
Object object = element[--elementCount]; 6 ^. f. Z" c# _6 M1 [0 c element[elementCount] = null;# k1 z/ S f3 U( R$ B( [
return object;9 |* ^ |* |; B$ m
}4 G+ v0 |8 U- {3 a" v5 T4 i1 N9 ^6 |
1 e( Y: f2 M& D @Override+ d% v5 } T2 d8 ~
public int getElementCount() { 5 N4 n. U, E- F' u' [1 I- p- c return elementCount; ! r' ]# H4 G, z7 l5 D; W } 8 D! k1 E: V( m5 B+ h! o; O7 s( Z( I
@Override3 u2 |% x, r0 E
public void traverse() {! F( v2 v' G' F6 r% d
for (int i = 0; i < elementCount; i++) {5 O- x/ K! I; N. r7 e1 e
System.out.print(element + ",");) V) B9 ], I9 g4 u
}6 K/ ?1 d' E8 [; ^5 m
System.out.println();% c5 ~* [' O- u0 T) \2 Q6 i) x
} . h( Y& J* ~' h1 i# d9 J; {, y} 6 e- E. f4 h* [2 o8 d3 l% Y6 X: ?3、栈的测试" i$ _4 U4 |! Z/ ?
public class StackTest { ' \, j1 Y9 v3 v public static void main(String[] args) {3 g2 f! v6 S5 V6 a$ l- g1 V) I
Stack stack = new StackImpl(); % w. Q% j& ^1 t+ J5 e+ u + _9 _( T1 p5 E //第一次入栈:压入1-15 " O- W- m1 \3 D% z( H for (int i = 0; i < 16; i++) { % e2 U: Q; M: Z+ R stack.push(i); ; m9 x% b. Y& Y' Z' W3 C% ]; } } - k9 H* J9 K/ r6 V t' i+ K: Y: { System.out.println("第一次入栈后元素个数为:" + stack.getElementCount()); # W5 O5 Y8 ~2 ^/ o, X+ Z stack.traverse();& {. Y8 s* |( R/ x# X4 C
/ T# y0 @; f5 c
//第二次入栈:压入16-31 ) v* \+ t5 y6 d: s: M1 F for (int i = 16; i < 32; i++) {! l+ U( m3 A6 Z. }/ \! l3 _: @
stack.push(i); , V$ c# f1 ] Y i } $ N: u3 s& F L System.out.println("第二次入栈后的元素个数为:" + stack.getElementCount()); : X/ V9 I3 F8 T# d8 w9 [1 j stack.traverse(); ( A4 ?! W9 F8 c2 J! A2 Z4 g3 |0 u$ j4 [4 j5 ^5 c
//第一次出栈:取出31-160 X* ~9 H; V# O% E8 u
for (int i = 0; i < 16; i++) {, }; X& ?7 b$ g# C& K! V8 n
stack.pop(); / o) o. ^3 R1 h) f/ x$ g, t) R } . t+ N/ {% t5 \2 z System.out.println("第一次出栈后的元素个数为:" + stack.getElementCount()); % v" y8 l8 ?+ T* i stack.traverse();8 B: |! V9 O0 R0 P
. f- @/ U7 V( t6 l) f" X; F( e8 A4 l //第二次出栈:取出15-0 1 M! d& Q* v# d; q* R+ R) C% s for (int i = 0; i < 16; i++) { # {! p, b1 K/ N; Z: Z5 v+ D9 Z stack.pop(); , u: u- P+ i* {2 W) \1 L/ r } - y, U* W/ j) G) E; p' b* e System.out.println("第二次出栈后的元素个数为:" + stack.getElementCount());) o/ H1 n- X }
stack.traverse();0 y3 F8 y6 N' D1 S( e4 [
* m) }0 H! _5 v, y* M# b
//栈中无元素,出栈报错 / a0 c4 V/ @% \% o6 p stack.pop();, I; A- G: d2 g8 v) c- v. ]4 B$ r
l' ~* {9 X' _# P
} 5 e$ j8 t4 F7 X; {6 x3 `}# s. p2 c7 m7 Y- t* M; e
: [6 i) G+ e# I1 N- g+ e //队头$ ^# U! |0 @' `. F" x
private int front; ' d9 e) ~7 ] Q: n. S: t, Y" v' A5 p l2 a
//队尾8 b- C/ z' i3 S. W
private int rear; $ F d) ~9 C9 Z' a; r8 q, c' D6 P, f: ?( J# p6 \
private int defaultSize = 16; 9 ]' `. l! F# e' u! v0 a6 P% O' h" j
private int maxSize; ( K4 ~/ b& W s& w' x2 T [ L9 q( k( F QueueImpl() { 8 ~, u/ P* _, j7 L: ~% a" H element = new Object[defaultSize]; ( X# w5 E$ L7 u, b9 v maxSize = defaultSize;3 n2 W# U* b, J' ^
front = 0;7 b7 ?- S5 ?* P# C: d5 h y" h" E
rear = -1;9 Z# Y9 o+ j9 c p- h, W. |
} 9 @* i+ A5 ^/ H5 w/ q 1 o, Q8 h. L% _5 p QueueImpl(int size) {& \# X: v! A" C
element = new Object[size]; . @& V9 C/ P, C6 w maxSize = size;; o* T' \& f5 H* G) Q+ M! P
front = 0;, }/ j" ?+ D& E2 g7 l
rear = -1; / d6 j2 |: O, [ }# G. f0 l" g0 A$ @
r7 M3 M' ]0 Y$ q
@Override1 d# S" h: \" @$ r
public int getMaxSize() {# F5 D3 v" B8 i1 j9 T+ { t
return maxSize;0 P' c% n- {8 C' S
}/ Q; o. B+ u- \5 u% }
. Z$ U8 \: f% d5 @ @Override# s4 w" n5 a! ^' |& _
public void push(Object object) { @' i3 Y7 } c+ @3 m5 Y/ L //如果元素个数已经达到数组的最大个数,则进行扩容) p8 r$ @- e! m h2 y: L
if (elementCount == maxSize) {7 E$ I2 O9 l7 k4 _
throw new ArrayIndexOutOfBoundsException("队列已满,请先进行出队");) n7 B8 S# G2 _- A# j
} / p4 [% s! [9 D# e! ]: ` element[++rear] = object;4 J" g+ E8 O! }- n
if (rear == element.length) { 1 C" V( s; a' v- j+ L; J rear = -1; 4 s: |2 P8 a; B. @9 j" N }# x% A% x$ J$ a/ W
elementCount++; 6 q& X* g y; c6 k) l }/ p% N& |- Q0 r y2 U: M
+ m; m3 p. f8 z: V7 d; O
@Override ; @4 ?6 E8 q) }) Y8 v: n$ U0 k public Object pull() { ! k* t8 s1 ^& N if (elementCount == 0) { 8 E7 A% N9 r" g- ]" H. v throw new ArrayIndexOutOfBoundsException("队列中无元素");3 @4 n# H# _4 v! K) a/ f0 U2 j7 l' o* }
}( |- _$ U$ u8 I' M, f- p1 ^7 e
Object object = element[front];, n2 Q4 D6 Y( f% M' b: I5 l
element[front] = null; ; e8 {9 Z; t3 S1 p: ?1 z* v front++;9 ?3 E/ _2 W" T/ w4 i# H
elementCount--;3 m( ]0 k9 {) [1 v
//队列清空,队头队尾恢复初始值3 ^6 {4 c. @" V. ?8 [" |9 l
if (elementCount == 0) { $ o4 x; s: a7 V& m4 K# T2 ^ front = 0;8 P7 F+ h7 I6 O7 N, y
rear = -1;3 W# B L1 p+ f( q$ z
} + Q/ [+ M' D0 x( ~1 S# O3 I return object;3 C$ m4 c- W1 n5 F# | O8 u
}* z; q1 B3 p d! X* v3 g9 M) V5 k' S& P
2 q1 t; b- _0 E. i4 s
@Override8 ?! d- P! x( V6 g' n: z
public int getElementCount() { 0 K) x( b5 {4 t1 R8 g u return elementCount; ; P9 W5 Y. k( c3 [# O+ ] } . Z8 p; E' V* V/ C' T4 i 8 m2 x+ Q C) e9 `2 k7 Z0 b @Override2 N. [" h; x6 u: B7 W
public Object getFront() {% ]3 }, @4 `' `: q3 q
if (elementCount == 0) {; [5 z O/ d4 e. o1 p, A
System.out.print("队头无元素"); 8 @0 Y5 Q4 B9 G2 c/ y return null; : \6 f' a2 h5 c4 Z P0 Z } ; @+ L: }% I0 @' | return element[front];. I6 b! B2 j3 e
}6 S( d W( R6 L; b* ~2 o' @
+ N8 P) |2 Q+ u# i
@Override' }& @9 X) D9 j+ u5 t8 L
public Object getRear() { # z) C: J: H$ c7 h" C! [ K if (elementCount == 0) { V; {1 S* Y+ \/ P B
System.out.print("队尾无元素"); 0 D4 P: D7 I8 ~. f0 x return null; ) p$ o$ Z1 h) a& O6 g9 @ }8 J! c! S* Q+ z8 d& k; M% D
return element[rear]; , P, I0 t% a1 o } D: x' c) F" U! m1 y) p7 e/ m3 G3 \1 }" R0 w
@Override$ |9 M _1 `' B
public void traverse() {& B5 g- `5 S2 ?3 w
if (elementCount == 0) { / L$ H- r; _. j( Y$ @1 b9 t return;$ ^, I5 T" G7 G7 X& o7 \/ ^
} & O6 X: u6 A5 V0 d5 K! w for (int i = front; i <= rear; i++) {+ r% `5 J, _) U; ]. x7 |. @
System.out.print(element + ",");, p: ?; W/ S; Y2 w* B7 G
} 8 W' ]$ p( a# _2 M3 H System.out.println(); 9 O; z2 Q) X( U, ~1 l } % P1 ^+ P. T% x" R% k3 n! U8 ~. ?}0 }2 X: V& k, K4 A W' l
9 M) h8 i# o4 d
0 n. D, `# F) w, [3 {* b4 `3 _ 3、队列的测试8 A% m. f" c" J
public class QueueTest {- _ b: i( n5 q) E" m9 A4 I
public static void main(String[] args) { 2 s6 |& X; C. _: h% n3 ` Queue queue = new QueueImpl();4 [2 q$ r; p! P" w
) [! O! \' k' K2 ?; |$ M' @# r //获取队列大小& `* E) i0 ^; ^6 \, Z) M; l x+ s: R
System.out.println("队列中最大可放置元素:" + queue.getMaxSize());2 T1 \$ s8 r" P O
* O; O7 V0 h s$ ]: U. a //第一次入队列:压入1-15 ) h& m- {- ^; V6 \ for (int i = 0; i < 16; i++) { : F; f/ r0 ~7 G% y queue.push(i); & [1 p& N7 x' t7 O% b- E9 J }0 h, k' l; r( x
System.out.println("第一次入队后元素个数为:" + queue.getElementCount()); 8 P* ]$ d# q+ S; w5 C* ~8 k queue.traverse();* e8 c! Y/ e1 M z3 P7 `4 V1 _
System.out.println("队头:"+queue.getFront()+" 队尾:"+queue.getRear()); 8 D4 n. T6 \1 C9 g, ?) u) b0 }2 U0 z
//第一次出队:取出0-15 ' R5 [" N; [ H3 r for (int i = 0; i < 16; i++) { $ i4 Y2 s8 E( o7 Q6 [, L8 {7 o queue.pull(); 4 a4 v+ z- A6 C! O } 2 \3 M% ?7 @' I4 P! E" ]$ q System.out.println("第一次出队后元素个数为:" + queue.getElementCount());* u6 e, W4 p! C2 m! r
queue.traverse();+ ` j( i3 B2 e0 y9 G1 T+ \5 m
System.out.println("队头:"+queue.getFront()+" 队尾:"+queue.getRear()); & j2 _8 D# E7 u6 `; j! j4 ~7 a: I: `% g( p: v, e6 \
) o/ M; p( `8 ~ e4 x* ~' s* R //第二次入队列:压入16,31 ; |. w* X4 L+ z* S/ k: o. Q for (int i = 16; i < 32; i++) {+ A Z H( o9 H( N
queue.push(i); 1 P/ w0 }; w4 s' g5 K } i, l# Z. i6 K System.out.println("第二次入队后元素个数为:" + queue.getElementCount()); & J8 }& i- l6 s3 T queue.traverse();; H( K7 O8 d2 `5 m4 n! [, v* M