栈与队列-灵析社区

栈

栈的概念

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

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

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

栈的使用

代码示范：

public class Test {
    public static void main(String[] args) {
        Stack<Integer> 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<Node> 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<Integer> 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;
    }
}

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列， deque 是 “ double ended queue ” 的简称，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队，Deque 是一个接口，使用时必须创建 LinkedList 的对象