栈是存放对象的一种特殊容器,在插入与删除对象时,这种结构遵循后进先出( Last-in-first-out,LIFO)的原则。java本身是有自带Stack类包,为了达到学习目的已经更好深入了解stack栈,自己动手自建java stack类是个很好的学习开始:
1 package com.stack;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5
6 /**
7 * Stack Class
8 * @author ganyee
9 *
10 */
11 public class Stack {
12 //Define capacity constant:CAPACITY
13 private static final int CAPACITY = 1024;
14 //Define capacity
15 private static int capacity;
16 //Define the top position of stack
17 //top = -1 meaning that the stack empty
18 private static int top = -1;
19 //Basic Object class array
20 Object[] array;
21 //Initialize the capacity of stack
22 public Stack() {
23 this.capacity = CAPACITY;
24 array = new Object[capacity];
25 }
26
27 //Get the size of stack
28 public int getSize(){
29 if(isEmpty()){
30 return 0;
31 }else{
32 return top + 1;
33 }
34 }
35
36 //Get whether stack is empty
37 public boolean isEmpty(){
38 return (top <0);
39 }
40
41 //Get the top element of stack
42 public Object top() throws ExceptionStackEmpty{
43
44 if(isEmpty()){
45 throw new ExceptionStackEmpty("Stack is empty");
46 }
47 return array[top];
48
49 }
50
51 //Push element to stack
52 public void push(Object element) throws ExceptionStackFull{
53 if(getSize()== CAPACITY){
54 throw new ExceptionStackFull("Stack is full");
55 }
56 array[++ top] = element;
57 }
58
59 //Pop element from stack
60 public Object pop() throws ExceptionStackEmpty{
61 if(isEmpty()){
62 throw new ExceptionStackEmpty("Stack is empty");
63 }
64 return array[top --];
65 }
66
67 //Get the all elements of stack
68 public String getAllElements() throws ExceptionStackEmpty{
69 String[] arr = new String[top + 1];
70 if(!isEmpty()){
71 for(int i = 0;i ){
72 arr[i] = (String)array[i];
73 }
74 }
75 return Arrays.toString(arr);
76 }
77 }
1 package com.stack;
2
3 public class ExceptionStackEmpty extends Exception {
4
5 //Constructor
6 public ExceptionStackEmpty(){
7
8 }
9
10 //Define myself exception construct with parameters
11 public ExceptionStackEmpty(String string){
12 super(string);
13 }
14 }
1 package com.stack;
2
3 public class ExceptionStackFull extends Exception {
4
5 //Constructor
6 public ExceptionStackFull(){
7
8 }
9
10 //Define myself exception construct with parameters
11 public ExceptionStackFull(String string){
12 super(string);
13 }
14 }
1 package com.stack;
2
3 public class StackTest {
4
5 public static void main(String[] args) {
6 // TODO Auto-generated method stub
7 Stack stack= new Stack();
8 System.out.println(stack.getSize());
9 System.out.println(stack.isEmpty());
10 try {
11 stack.push(8);
12 stack.push(3);
13 stack.push(4);
14 stack.push(7);
15 stack.push(1);
16 stack.push(8);
17 stack.push(3);
18 stack.push(4);
19 stack.push(7);
20 stack.push(1);
21 System.out.println(stack.getSize());
22 System.out.println(stack.top());
23 System.out.println(stack.getAllElements());
24
25 System.out.println(stack.pop());
26 System.out.println(stack.pop());
27 System.out.println(stack.pop());
28 System.out.println(stack.pop());
29 System.out.println(stack.pop());
30 System.out.println(stack.pop());
31 System.out.println(stack.pop());
32 System.out.println(stack.pop());
33 System.out.println(stack.pop());
34 System.out.println(stack.pop());
35
36 } catch (ExceptionStackFull e) {
37 // TODO Auto-generated catch block
38 e.printStackTrace();
39 }catch (ExceptionStackEmpty e) {
40 // TODO Auto-generated catch block
41 e.printStackTrace();
42 }
43 }
44
45 }
0
true
10
1
[8, 3, 4, 7, 1, 8, 3, 4, 7, 1]
1
7
4
3
8
1
7
4
3
8
1 package com.stack;
2
3 public class MatchClass {
4
5 public static boolean Match(String str) throws ExceptionStackFull, ExceptionStackEmpty{
6 Stack stack = new Stack();
7 str = str.replaceAll(" ","");
8 char s;
9 for(int i = 0;i ){
10 if(str.charAt(i) == ‘(‘ || str.charAt(i) == ‘{‘ || str.charAt(i) == ‘[‘)
11 stack.push(str.charAt(i));
12 else{
13 if(stack.isEmpty())
14 return false;
15 else{
16 s = str.charAt(i);
17 switch(s){
18 case ‘)‘:
19 if((Character)stack.pop() != ‘(‘)
20 return false;
21 break;
22 case ‘}‘:
23 if((Character)stack.pop() != ‘{‘)
24 return false;
25 break;
26 case ‘]‘:
27 if((Character)stack.pop() != ‘[‘)
28 return false;
29 break;
30 }
31 }
32
33 }
34 }
35 if(stack.isEmpty()){
36 return true;
37 }else{
38 return false;
39 }
40 }
41 }
1 package com.stack;
2
3 public class ParentMatch {
4
5 public static void main(String[] args) {
6
7 MatchClass match = new MatchClass();
8 //String str = "()({})"; //Match
9 //String str = "()({}) {([()[]])}";//Match
10 //String str = "([]{)";//Not match
11 //String str = ")([()] {}";//Not match
12 String str = "([())]{}";//Not match
13 try {
14 if(!match.Match(str)){
15 System.out.println(str + ": Not Macth");
16 }else{
17 System.out.println(str + ": Macth");
18 }
19 } catch (ExceptionStackFull e) {
20 // TODO Auto-generated catch block
21 e.printStackTrace();
22 } catch (ExceptionStackEmpty e) {
23 // TODO Auto-generated catch block
24 e.printStackTrace();
25 }
26 }
27
28 }
()({}): Macth
()({}) {([()[]])}: Macth
([]{): Not Macth
)([()] {}: Not Macth
([())]{}: Not Macth