Java栈和队列的实现

一.栈(Stack)

1.1栈的概念

1.2栈的实现及模拟

二.队列(Queue)

2.1队列的概念

2.2队列的实现及模拟

2.3循环队列

2.4双端队列（Deque）

一.栈(Stack)

1.1栈的概念

栈:一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO （ Last In First Out ）的原则

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。

出栈：栈的删除操作叫做出栈。 出数据在栈顶

1.2栈的实现及模拟

public class Test {
    public static void main(String[] args) {
        Stack<Integer>s=new Stack();//创建一个空栈
        s.push(1);//往栈中存入1
        s.push(2);//2
        s.push(3);//3
        s.push(4);//4
        s.push(5);//5

        System.out.println(s.size());//有效个数5
        System.out.println(s.peek());//获取栈顶元素5

        s.pop();//5出栈

        System.out.println(s.peek());//此时栈顶元素变为4

        System.out.println(s.empty());//判断是否为空栈,此时不为空 返回false
    }
}

这里我们用自己的方法来模拟实现上述的方法

public class MyStack {
    int[] elem;
    int usedSize;

    public MyStack(){
        this.elem=new int[10];
    }

    public void push(int val){
        if(isFull()){
            //扩容
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize]=val;
        usedSize++;
    }

    public boolean isFull(){
        return usedSize==elem.length;
    }

    public int pop(){
        if(empty()){
            return -1;
        }
        int oldVal=elem[usedSize-1];
        usedSize--;
        return oldVal;
    }

    public int peek(){
        if(empty()){
            return -1;
        }
        return elem[usedSize-1];
    }

    public boolean empty(){
        return usedSize==0;
    }
}

二.队列(Queue)

2.1队列的概念

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front）

2.2队列的实现及模拟

在Java中，Queue是个接口，底层是通过链表实现的

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public class Test{
    public static void main(String[] args) {
        Queue<Integer>q=new LinkedList<>();
        q.offer(1);//从队尾入
        q.offer(2);
        q.offer(3);
        q.offer(4);

        System.out.println(q.size());//有效个数 4
        System.out.println(q.peek());//获取头元素 1

        q.poll();//1从队列中出

        System.out.println(q.peek());//2

        System.out.println(q.isEmpty());//此时队列不为空，所以返回 false
    }
}

这里我们进行模拟实现上述方法

public class MyQueue {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val){
            this.val=val;
        }
    }

    public ListNode head;
    public ListNode last;

    public void offer(int val){
        ListNode node=new ListNode(val);
        if(head==null){
            head=last=node;
        }else{
            last.next=node;
            node.prev=last;
            last=last.next;
        }
    }

    public int poll(){
        if(head==null){
            return -1;
        }
        int ret=head.val;
        if(head.next==null){
            head=last=null;
        }else{
            head=head.next;
            head.prev=null;
        }
        return ret;
    }

    public int peek(){
        if(head == null) {
            return -1;
        }
        return head.val;
    }

    public boolean isEmpty(){
        return head==null;
    }
}