欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法(java)——栈和队列

程序员文章站 2022-03-13 10:46:59
...
  • 栈:栈又名堆栈,它是一种运算受限的线性表,其限制是只能在表的一端进行插入和删除操作,这一端称为栈顶。插入新的元素又称为进栈、入栈或压栈,删除元素又称为出栈或者退栈。


    数据结构与算法(java)——栈和队列

代码实现:

public class MyStack {

    //底层实现是一个数组
    private long[] arr;

    //栈顶
    private int top;

    public MyStack() {
        arr = new long[10];
        top = -1;
    }

    public MyStack(int maxSize){
        arr = new long[maxSize];
        top = -1;
    }

    /**
     * 添加数据
     * @param l
     */
    public void pusk(long l) {
        arr[++top] = l;
    }

    /**
     * 移除数据
     * @return
     */
    public long pop(){
        return arr[top--];
    }

    /**
     * 查看数据
     */
    public long peek(){
        return arr[top];
    }

    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty(){
        return top == -1;
    }

    /**
     * 判断是否满了
     * @return
     */
    public boolean isFull(){
        return top == arr.length - 1;
    }

}
  • 队列:和栈一样,队列也是一种受限的线性表,不一样的是队列只能在队头(front)删除元素,在队尾(rear)插入元素。


    数据结构与算法(java)——栈和队列


    代码实现:

    public class MyCircleQueue {
    
        // 底层实现数组
        private long[] arr;
    
        // 队头
        private int front;
    
        // 队尾
        private int rear;
    
        // 元素
        private int elements;
    
        public MyCircleQueue() {
            arr = new long[10];
            elements = 0;
            front = 0;
            rear = -1;
        }
    
        public MyCircleQueue(int maxSize) {
            arr = new long[maxSize];
            elements = 0;
            front = 0;
            rear = -1;
        }
    
        /**
         * 添加数据<br/>
         * 队尾添加
         * 
         * @param value
         */
        public void insert(long value) {
            if(rear == arr.length - 1){
                rear = -1;
            }
            arr[++rear] = value;
            elements++;
        }
    
        /**
         * 移除数据<br/>
         * 队头移除
         * 
         * @return
         */
        public long remove() {
            long result = arr[front++];
            if(front == arr.length){
                front = 0;
            }
            elements--;
            return result;
        }
    
        /**
         * 查看队头数据
         * 
         * @return
         */
        public long peek() {
            return arr[front];
        }
    
        /**
         * 是否为空
         * 
         * @return
         */
        public boolean isEmpty() {
            return elements == 0;
        }
    
        /**
         * 是否满了
         * 
         * @return
         */
        public boolean isFull() {
            return elements == arr.length;
        }
    
    }
    

总结:栈和队列都是一种受限的线性表,不同的是:栈是只能再一端进行操作,后进先出;而队列则是只能在一端进行插入,另一端删除,先进先出。