java数据结构与算法--栈与队列

女爷i 2022-05-26 11:20 206阅读 0赞

1、模拟栈

package com.evior.stack;
    
    /** * 模拟栈 */ public class Stack {
    
        //栈顶指针
        private int top=-1;
    
        //数组
        private int[] arr;
    
        public Stack() {
            arr=new int[50];
        }
    
        public Stack(int maxLength) {
            arr=new int[maxLength];
        }
    
        //压栈
        public void push(int value){
            //判断栈是否已满
            if (!isFull()){
                top++;
                arr[top]=value;
            }else {
                throw new RuntimeException("栈满，无法入栈");
            }
    
    
        }
    
        //弹栈
        public int pop(){
            if (!isEmpty()){
                top--;
                return arr[top+1];
            }else {
                throw new RuntimeException("栈空，无法弹栈");
            }
        }
    
    
        //判空
        public boolean isEmpty(){
            return top==-1;
        }
    
        //判断栈满
        public boolean isFull(){
            return arr.length-1==top;
        }
    
    
    }

2、测试

package com.evior.stack;
    
    public class Test {
    
        public static void main(String[] args) {
            Stack stack=new Stack(3);
            stack.push(1);
            stack.push(2);
            stack.push(3);
            System.out.println(stack.pop());
    
            while (!stack.isEmpty()){
                System.out.print(stack.pop()+",");
            }
    
        }
    }

3、结果

![70][]

4、模拟队列

package com.evior.queue;
    
    
    /** * 队列 */ public class Queue {
    
        //底层数组
        private long[] arr;
    
        //有效数据的大小
        private int element;
    
        //对头
        private int head;
    
        //队尾
        private int end;
    
    
        /** * 默认构造器 */ public Queue() {
            arr=new long[50];
            element=0;
            head=-1;
            end=-1;
        }
    
        /** * 带参构造 * @param maxLength */ public Queue(int maxLength) {
           arr=new long[maxLength+1];
            element=0;
            head=-1;
            end=-1;
        }
    
    
        /** * 入队 */ public void insert(long value){
            if (!isFull()){
                //移动数组
                if (element>0){
                    for (int i=element-1;i>=0;i--){
                        arr[i+1]=arr[i];
                    }
                    arr[0]=value;
                    element++;
                    head++;
                }else {
                    arr[++head]=value;
                    element++;
                }
            }else {
                throw new RuntimeException("队列已满,无法插入");
            }
    
        }
    
    
    
        /** * 出队 * @return */ public long out(){
            if (!isEmpty()){
                element--;
                return arr[head--];
            }else {
                throw new RuntimeException("队列为空,无法出队列");
            }
    
        }
    
        /** * 参看对头 * @return */ public  long peek(){
            return arr[head];
        }
    
        /** * 判断队是否为空 */ public boolean isEmpty(){
            return element==0;
        }
    
        public boolean isFull(){
            return element==arr.length-1;
        }
    
    
    
    }

5、测试

package com.evior.queue;
    
    public class Test {
    
        public static void main(String[] args) {
            Queue queue=new Queue(5);
            queue.insert(1);
            queue.insert(2);
            while (!queue.isEmpty()){
                System.out.println(queue.out());
            }
            queue.insert(3);
            queue.insert(4);
        }
    }

6、结果

![70 1][]

[70]: /images/20220526/b6cb5c3aac2e4f0180129c8ba46df6fa.png
[70 1]: /images/20220526/777ddd8d279f431a8613e9b820c2989c.png