博客

目录

1.栈

（1）定义

（2）栈的基本操作

（3）特点

（4）常见的方法

（5）在java中实现栈的操作

2.队列

2.1 概念

2.2 常用的方法

2.3 队列的实现

1.栈

（1）定义

栈（Stack）作为一种限定性线性表，是将线性表的插入和删除操作限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶（Top），因此栈顶的当前位置是动态变化的。同时表的另一端称为栈底（Bottom）。

栈顶：允许插入和删除的一端

栈底：栈顶的另一端

（2）栈的基本操作

入栈、出栈、取出栈顶元素

（3）特点

先进后出(FILO)

（4）常见的方法

（5）在java中实现栈的操作

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

2.利用链表实现，则头尾皆可。

相对来说，顺序表的实现上更为简单一些，所以我们优先用顺序表实现栈

public class MyStack {
    // 简单起见，我们就不考虑扩容问题了
    private int[] array = new int[100];
    private int size = 0;

    public void push(int v) {
        array[size++] = v;
    }

    public int pop() {
        return array[--size];
    }

    public int peek() {
        return array[size - 1];
    }

    public boolean isEmpty() {
        return size == 0;
    }
    
    public int size(){
        return size;
    }
}

2.队列

2.1 概念

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

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

出队：进行删除操作的一端称为 队头（Head/Front）

2.2 常用的方法

2.3 队列的实现

队列可以使用数组和链表实现，但是选择链表实现会更好一点。通常我们选择使用链表的结构来实现队列，效率更高。

//定义结点类
public class Node {
    int val;
    Node next;

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }

    public Node (int val){
        this(val,null);
    }
}

public class MyQueue {
    private Node head = null;
    private Node tail = null;
    private int size = 0;

    public void offer(int val){
        Node node =new Node(val);
        if(tail == null){       //初始队列为空
            head=node;
        }else{
            tail.next = node;
        }
        tail = node;
        size++;
    }

    public int poll(){
        if(size == 0){
            throw new RuntimeException("队列为空");
        }

        Node oldHead = head;
        head = head.next;
        if(head == null){       //若原来队列中只有一个元素，取出后队列为空
            tail = null;
        }
        size--;
        return oldHead.val;
    }

    public int peek(){
        if(size == 0){
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public int size(){
        return size;
    }
}

值得关注的是，还有两种特殊的队列  循环队列和双端队列，这里不再详细说明，后面另附博客。🙌🙌🙌