Java学习苦旅（十七）—

Java学习苦旅（十七）——栈和队列

本篇博客将详细讲解Java中的栈和队列。

文章目录

栈
- 概念
- Java中Stack常用方法
- 代码实现
队列
- 概念
- 队列常用方法对比
- - Queue
  - Deque
- 代码实现Queue
结尾

栈

概念

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

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

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

Java中Stack常用方法

方法	解释
E push(E item)	压栈
E pop()	出栈
E peek()	查看栈顶元素
boolean empty()	判断栈是否为空

代码实现

使用顺序表实现push()，pop()，peek()

import java.util.*;

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[5];
    }

    public void push(int val) {
        if(isFUll()) {
            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;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        int oldVal = this.elem[usedSize-1];
        this.usedSize--;
        return oldVal;
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        return this.elem[usedSize-1];
    }
}

队列

概念

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

入队列：进行插入操作的一端称为队尾。

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

队列常用方法对比

Queue

错误处理	抛储异常	返回特殊值
入队列	add(e)	offer(e)
出队列	remove()	poll()
队首元素	element()	peek()

Deque

头部/尾部	头部元素（队首）		尾部元素（队尾）
错误处理	抛出异常	返回特殊值	抛出异常	返回特殊值
入队列	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
出队列	removeFirst()	pollFirst()	removeLast()	pollLast()
获取元素	getFirst()	peekFirst()	getLast()	peekLast()

代码实现Queue

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;
        }
    }

    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;
    }

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