目录

1.栈（Stack）

1.1概念

1.2 栈的实现

 2.队列(Queue)

2.1 概念

2.2 单链表实现队列

 2.3 循环队列

 2.4双端队列

3.java 中的栈和队列

---

1.栈（Stack）

1.1概念

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

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

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

1.2 栈的实现

1）利用顺序表实现，即使用尾插+尾删的方式实现

2）利用链表实现，则头尾都可以

因为顺序表实现上更为简单，此处使用顺序表实现

1.创建 MyStack 类

import java.util.Arrays;
 
/**
 * 栈的实现
 */
public class MyStack {
    public int[] elem;
    public int usedSize;
 
    public MyStack() {
        this.elem = new int[5];
    }
 
    //压栈
    public void push(int val) {
        if(isFull()) {
            //满了就2倍扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
    }
    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }
 
    //出栈,pop 会删除栈元素，peek 获取栈元素，不删除
    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("栈为空！");
        }
        int oldVal = this.elem[usedSize-1];
        this.usedSize--;
        return oldVal;
    }
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("栈为空！");
        }
        int oldVal = this.elem[usedSize-1];
        return oldVal;
    }
 
    //判断栈是否为空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }
 
}

2.main 函数

import java.util.Stack;
 
/**
 * 栈，先进后出
 */
 
public class StackTest {
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        //压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        //出栈，pop 是出一个栈顶元素并且在栈中删除
        System.out.println(stack.pop());//6
        // peek 是获取栈顶元素但不删除栈中元素
        System.out.println(stack.peek());//5
        System.out.println(stack.peek());//5
        System.out.println(stack.isEmpty());//false
    }
}

3.运行结果

 2.队列(Queue)

2.1 概念

2.2 单链表实现队列

 单链表实现

/**
 * 队列的实现，使用单链表
 */
class Node {
    public int val;
    public Node next;
    public Node(int val) {
        this.val = val;
    }
}
 
public class MyQueue {
    public Node head;
    public Node last;
 
    /**
     * 添加队列元素
     * 使用单链表尾插法
     * @param val
     */
    public void offer(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            last = node;
        }else {
            last.next = node;
            last = last.next;
        }
    }
 
    /**
     * 出队
     * @return
     */
    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int oldVal = head.val;
        this.head = head.next;
        return oldVal;
    }
    public boolean isEmpty() {
        return this.head == null;
    }
 
    /**
     * 获取队列元素
     * @return
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
}

main 方法

import java.util.Queue;
 
public class QueueTest {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        //入队列
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        //获取队列元素
        System.out.println(queue.peek());//1
        //出队
        System.out.println(queue.poll());//1
        System.out.println(queue.poll());//2
        System.out.println(queue.poll());//3
 
    }
}

效果

 2.3 循环队列

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

 代码

/**
 * 设计循环队列
 */
public class MyCircularQueue {
    public int[] elem;
    public int front;//队头下标
    public int rear;//队尾下标
    public MyCircularQueue(int k) {
        this.elem = new int[k + 1];
    }
 
    /**
     * 入队
     * @param value
     * @return
     */
    public boolean enQueue(int value) {
        if (isFull()) return false;
        this.elem[rear] = value;
        rear = (rear+1) % elem.length;
        return true;
    }
 
    /**
     * 出队
     * @return
     */
    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front+1) % elem.length;
        return true;
    }
 
    /**
     * 得到对头元素
     * @return
     */
    public int Front() {
        if (isEmpty()) return -1;
        return elem[front];
    }
 
    /**
     * 队尾元素
     * @return
     */
    public int Rear() {
        if (isEmpty()) return -1;
        int index = -1;
        if (rear == 0) {
            index = elem.length - 1;
        }else {
            index = rear - 1;
        }
        return elem[index];
    }
 
    public boolean isEmpty() {
        return front == rear;
    }
 
    public boolean isFull() {
        if((this.rear+1) % elem.length == front) {
            return true;
        }
        return false;
    }
}

 2.4双端队列

3.java 中的栈和队列