Java-栈和队列

文章目录

一、栈
- 1、什么是栈？
- 2、栈的应用
- 3、栈的实现
二、队列
- 1、什么是队列？
- 2、队列的应用
- 3、队列的实现
- 4、循环队列
三、双端队列

栈和队列是一码事，都是对只能在线性表的一端进行插入和删除。因此，其实栈和队列是可以相互转换的。

一、栈 1、什么是栈？

栈：就像是生活中装羽毛球的盒子，只能从一端进，从同一端出。最开始放进去的羽毛球在最里面，最后放的在最外面。要想取出最里面的羽毛球，就需要先将外面的羽毛球都先取出，才能拿到最里面的羽毛球。

栈的进入和取出顺序是相反的，先进的后出，后进的先出。（LIFO）
栈也属于一种线性表的数据结构。

2、栈的应用

1）、无处不在的undo（撤销）操作
2）、浏览器点击后退操作，就能帮我们返回到上一次浏览的网页
3）、操作系统栈
程序在执行过程中，从调用的函数退出返回时，如何得知从哪儿继续执行，背后就是栈的结构。

3、栈的实现

栈可以基于链表实现，也可以基于数组实现。
这里我们基于动态数组ArrayList实现栈
栈的三个核心操作：
1、入栈：push（）；
2、出栈：pop（）；
3、查看栈顶元素：peek（）；
另外还有判断栈的是否为空：isEmpty（）；

代码实现：

public class MyStack {
    private List Stack=new ArrayList<>();

    //进栈
    public void push(int val) {
        Stack.add(val);
    }
    //出栈
    public int pop(){
        if (isEmpty()){
            throw new NullPointerException("栈为空，无法执行pop语句");
        }
        return Stack.remove(Stack.size()-1);
    }
    //获取栈顶的值，不弹出
    public int peek(){
       return Stack.get(Stack.size()-1);
    }

    //判空
    public boolean isEmpty(){
        return Stack.size()==0;
    }


    @Override
    public String toString() {
        StringBuilder str=new StringBuilder();
        str.append("[");
        for (int i = 0; i < Stack.size(); i++) {
            str.append(Stack.get(i));
            if (i!=Stack.size()-1) {
                str.append(",");
            }
        }
        str.append("]");
        return str.toString();
    }
}

二、队列 1、什么是队列？

队列和栈差不多，都是一种线性表的数据结构。
队列是一种先进先出（FIFO）的结构，从一端进，从另一端出，最先进队列的最先出队列。

2、队列的应用

队列在实际生活中的应用也十分广泛，这种结构就相当于人们在生活中排队一样，数据的传输过程中就会用到。

3、队列的实现

一般的队列都是基于链表实现的（特殊情况除外），因为如果基于数组实现，前面的数据弹出之后，数组后面的所有内容都要跟着变化，这样很麻烦。
队列的三个核心操作：
1、入队操作：offer（）；
2、出队操作：poll（）；
3、查看队首元素：peek（）；

同样，队列结构中也有判空操作
代码实现：

public class MyQueue{
    private Node headNode;
    private Node tailNode;

    //入队操作
    public void offer(E val) {
        Node node = new Node<>(val);
        if (isEmpty()) {
            headNode = tailNode = node;
            return;
        }
        tailNode.next = node;
        tailNode = tailNode.next;
    }

    //出队操作
    public E pop() {
        if (isEmpty()) {
            throw new NullQueue("队列为空，不能进行出队列操作");
        }
        Node a = headNode;
        headNode = headNode.next;
        a.next = null;
        return (E) a.val;
    }


    //显示队首操作
    public E peek() {
        if (isEmpty()) {
            throw new NullQueue("队列为空，没有队首");
        }
        return headNode.val;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("first[");
        for (Node aNode = headNode; aNode != null; aNode = aNode.next) {
            sb.append(aNode.val);
            if (aNode.next != null) {
                sb.append(",");
            }
        }
        sb.append("]tail");
        return sb.toString();
    }

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

class NullQueue extends RuntimeException {
    public NullQueue(String message) {
        super(message);
    }
}


class Node {
    E val;
    Node next;

    public Node(E val) {
        this.val = val;
    }

}

4、循环队列

循环队列是基于一个定长数组去实现，通过改变引用值去操作数组中的元素。
代码实现：

public class cycleQueue implements Queue {
    private Integer[] data;
    private int head;
    private int tail;

    public cycleQueue(int val) {
        this.data=new Integer[val+1];
    }
    @Override
    public void offer(Integer val) {
        if (isFull()) {
            throw new FullQueue("队列已满，无法进行入队操作");
        }
        data[tail]=val;
        tail=(tail+1)% data.length;
    }

    @Override
    public Integer peek() {
        if (isEmpty()) {
            throw new isEmpty("队列为空，没有队首元素");
        }
        return data[head];
    }

    @Override
    public Integer pop() {
        if (isEmpty()) {
            throw new isEmpty("队列为空，无法执行出队操作");
        }
        int a=data[head];
        head=(head+1)%data.length;
        return a;
    }

    @Override
    public boolean isEmpty() {
        return head==tail;
    }
    public boolean isFull() {
        return (tail+1)%data.length==head;
    }

    @Override
    public String toString() {
        int last=tail==0? data.length-1:tail-1;
        StringBuilder sb=new StringBuilder();
        sb.append("first[");
        for (int i = head; i!=tail ; i=(i+1)%data.length) {
            sb.append(data[i]);
            if (i!=last) {
                sb.append(",");
            }
        }
        sb.append("]tail");
        return sb.toString();
    }
}
class isEmpty extends RuntimeException{
    public isEmpty(String msg){
        super(msg);
    }

}

class FullQueue extends RuntimeException {
    public FullQueue(String msg){
        super(msg);
    }
}

三、双端队列

可以从任意一端进入，也可以从任意一端退出，那么我们是不是就可以认为双端队列即是栈，也是队列。
其实在开发过程中很少再去使用Queue去创建队列，使用Stack去创建栈。而是直接使用Deque创建双端队列去进行栈和队列的操作。
在使用过程中只要区分方法就能实现区分栈和队列的操作。

public class Test {
    public static void main(String[] args) {
        //栈
        Deque stack=new LinkedList<>();
        stack.push(1);
        stack.push(1);
        stack.push(1);
        stack.push(4);
        stack.push(3);
        System.out.println(stack.pop());
        //队列
        Queue queue=new LinkedList<>();
        queue.offer(3);
        queue.offer(3);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue.poll());
    }
}

Java-栈和队列

Java相关栏目本月热门文章