【数据结构】栈与队列

2023-10-23 06:19

短信预约 -IT技能 免费直播动态提醒

作者主页：paper jie 的博客

本文作者：大家好，我是paper jie，感谢你阅读本文，欢迎一建三连哦。

本文录入于《JAVA数据结构》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将javaSE基础知识一网打尽，希望可以帮到读者们哦。

其他专栏：《算法详解》《C语言》《javaSE》等

内容分享：本期将会分享数据结构中的栈与队列

栈

栈的概念

栈它是一种特殊的线性表，只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守着先进后出的规则。

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

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

栈的使用

代码示范：

public class Test {    public static void main(String[] args) {        Stack stack = new Stack<>();        stack.push(1);        stack.push(2);        stack.push(3);        stack.push(4);        stack.push(5);        System.out.println(stack.peek());        System.out.println(stack.pop());        System.out.println(stack.empty());        System.out.println(stack.size());    }}

栈的模拟实现

Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，但不同的是Vector是线性安全的。

代码模拟实现：

public class MyStack implements Istack{    private int[] elem;    private int usedsize;    private static final int DEFAULT_CAPACITY = 10;    public MyStack() {        this.elem = new int[DEFAULT_CAPACITY];    }    @Override    public void push(int x) {        if(full()) {            elem = Arrays.copyOf(elem, 2*elem.length);        }        elem[usedsize] = x;        usedsize++;    }    @Override    public boolean full() {        if(usedsize == elem.length) {            return true;        }        return false;    }    @Override    public int pop() {        if(Empty()) {            throw new Emptyexception("数组为空");        }        int ret = elem[usedsize-1];        usedsize--;        return ret;    }    @Override    public int peek() {        if(Empty()) {            throw new Emptyexception("数组为空");        }        return elem[usedsize - 1];    }    @Override    public int size() {        return usedsize;    }    @Override    public boolean Empty() {        if(usedsize == 0) {            return true;        }        return false;    }}

栈的应用

将递归转化为循环

// 递归方式    void printList(Node head){        if(null != head){            printList(head.next);            System.out.print(head.val + " ");        }    }    // 循环方式    void printList(Node head){        if(null == head){            return;        }        Stack s = new Stack<>();// 将链表中的结点保存在栈中        Node cur = head;        while(null != cur){            s.push(cur);            cur = cur.next;        }        // 将栈中的元素出栈        while(!s.empty()){            System.out.print(s.pop().val + " ");        }    }

栈，虚拟机栈，栈帧的区分

栈：是一种数据结构

虚拟机栈：是java虚拟机JVM中分配的一块内存

栈帧：是在调用方法的时候，会在虚拟机中为这个方法分配一块内存

队列（Queue）

队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头

队列的使用

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

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

public static void main(String[] args) {Queue q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}

队列模拟实现

链式结构对列：

public class MyLinkqueue {    static class ListNode {        int val;        ListNode prev;        ListNode next;        public ListNode(int val) {            this.val = val;        }    }    ListNode head;    ListNode last;    int usedsize;    public void offer(int val) {        ListNode node = new ListNode(val);        if(head == null) {            head = node;            last = node;            usedsize++;            return;        }            last.next = node;            node.prev = last;            last = node;            usedsize++;    }    public int poll() {        if(head == null) {            return -1;        }        int ret = head.val;        if(head.next == null) {            head = null;            last = null;        } else {            head.next.prev = null;            head = head.next;        }        usedsize--;        return ret;    }    public int peek() {        if(head == null) {            return -1;        }        return head.val;    }    public boolean Empty(){        return head == null;    }    public int size() {        return usedsize;    }}

循环队列

实际中我们有时还会使用一种队列叫循环队列，操作系统课程讲解生产者消费者模型时可以就会使用循环队列，环形队列通常使用数组实现

代码：

class MyCircularQueue {    int[] elem;    int front;    int rear;    public MyCircularQueue(int k) {        elem = new int[k+1];    }        public boolean enQueue(int value) {        if(isFull()) {            return false;        }        elem[rear] = value;        rear = (rear+1) % elem.length;        return true;    }        public boolean deQueue() {        if(isEmpty()) {            return false;        }        front = (front+1)% elem.length;        return true;    }        public int Front() {        if(isEmpty()) {            return -1;        }        return elem[front];    }        public int Rear() {        if(isEmpty()) {            return -1;        }        int ret = (rear == 0) ?  elem.length-1 : rear-1;        return elem[ret];    }        public boolean isEmpty() {        return front == rear;    }        public boolean isFull() {        return (rear+1) % elem.length == front;    }}