算法初级——数组实现栈和队列

用数组结构实现大小固定的队列和栈
数组实现队列
/*
* 数组实现队列:定义长度,压入,弹出,查询操作
* 压入时先判断是否满队列,如果不满,队列长度+1,赋值,然后判断游标位置,如果游标等于数组数组最大位置,游标回到队列开头
* 弹出时判断是否空队列,如果不空,队列长度-1,弹出,然后判断游标位置,如果游标位置等于数组最大位置,游标回到开头
*/

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
public class ArrayToQueue {
   
    public static class MyQueue{
        private int out;
        private int in;
        private int size;
        private int arr[];
       
        public MyQueue(int size) {
            arr = new int[size];
            size = 0;
            in = 0;
            out = 0;
        }
        public void push(int num) {
            if(size == arr.length) {
                throw new RuntimeException("full");
            }
            size++;
            arr[in] = num;
            in = in == arr.length-1 ? 0 : in+1;
            System.out.println(in);
        }
        public int pull() {
            if(size == 0) {
                throw new RuntimeException("empty");
            }
            size--;
            int t = out;
            out = out == arr.length-1 ? 0 : out+1;
            return arr[t];
        }
        public int peek() {
            if(size == 0) {
                throw new RuntimeException("empty");
            }
            return arr[out];
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int iniSize = 3;  
        MyQueue myQueue = new MyQueue(iniSize);  
        myQueue.push(12);  
        myQueue.push(13);  
        myQueue.push(15);  
        //myQueue.push(23);  
        System.out.println(myQueue.peek());
        System.out.println(myQueue.pull());  
        System.out.println(myQueue.pull());  
        System.out.println(myQueue.pull());
        //System.out.println(myQueue.pull());
        //myQueue.push(23);  
        //myQueue.push(24);  
        //System.out.println(myQueue.pull());  
        //System.out.println(myQueue.peek());  

    }

}

数组实现栈
/* 栈:先进后出
* 数组实现大小固定的栈,压栈,弹出,查询栈顶
* 压入操作,判断栈是否已满,如果不满,压入,游标后移
* 弹出操作,判断栈是否空,如果不空,游标前移,弹出
* 查询操作,返回size-1的元素(不能用自减,以为查询操作size不变)
*/

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
public class ArraytoStack {
    public static class Mystack{
        private int size;
        private int[] arr;
        public Mystack(int size){
            if(size < 0) {
                throw new RuntimeException("size > 0");
            }
            arr = new int[size];
            size = 0;
        }
        public Integer peek() {
            if(size == 0) {
                return null;
            }
            return arr[size-1];
        }
        public void push(int obj) {
            if(size == arr.length) {
                throw new RuntimeException("full");
            }
            arr[size++] = obj;
        }
        public Integer pop() {
            if(size == 0) {
                throw new RuntimeException("empty");
            }
            return arr[--size];
        }
       
    }
   

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int len = 13;  
        Mystack myStack = new Mystack(len);  
        for (int i = 0; i < len; i++) {  
            myStack.push(i);  
        }  
       
        System.out.println(myStack.peek());
        System.out.println(myStack.peek());
       
        for (int i = 0; i < len; i++) {  
            System.out.print(myStack.pop()+" ");  
        }
         

    }

}
0 条评论
发表一条评论