FilesExpand file tree

master

/

StackArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

81 lines (68 loc) · 1.28 KB

master

/

StackArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

81 lines (68 loc) · 1.28 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

package com.algs;

import java.util.Iterator;

public class StackArray<Item> implements Iterable<Item> {

private Item[] arr = (Item[]) new Object[1]; // Java无法创建泛型数组，只能使用转换类型

private int N = 0;

public boolean isEmpty(){

return 0 == N;

}

public int size(){

return N;

}

/**

* 检测栈是否为空

* @return

*/

public Item pop(){

if(N < 0){

throw new IllegalArgumentException();

}

Item result = arr[N--];

arr[N--] = null; // 避免内存溢出，也即对象游离

if(N > 0 && N == arr.length / 4){

resize(arr.length/2);

}

return result;

}

/**

* 需要检测栈是否已满

* @param item

*/

public void push(Item item){

if(N == arr.length){

resize(2 * arr.length);

}

arr[N++] = item;

}

/**

*

* @param newSize

*/

private void resize(int newSize){

Item[] newArr = (Item[]) new Object[newSize];

for(int i = 0; i < N; i++){

newArr[i] = arr[i];

}

arr = newArr;

}

@Override

public Iterator<Item> iterator() {

return new ReverseArrayIterator();

}

/**

* 栈是后进先出，逆序遍历数组

* @author Administrator

*

*/

private class ReverseArrayIterator implements Iterator<Item>{

private int i = N;

@Override

public boolean hasNext() {

return i > 0;

}

@Override

public Item next() {

return arr[--i];

}

}

}