java数据结构之栈和队列

java数据结构之栈和队列 目录

java数据结构之栈和队列一、栈二、队列三、标准库中的栈和队列 一、栈

核心思想：后进先出

顺序表实现：

public class MyStack1 { private int[] data = new int[100]; private int size = 0;

入栈：尾插

public void push(int val){ if (size >= data.length){ return; } data[size] = val; size++; }

出栈：尾删（返回值就是被出栈删除的元素）

public Integer pop(){ if (size == 0){ return null; } //删除栈顶元素 int ret = data[size-1]; size--; return ret; }

取栈顶元素：根据下标获取元素

public Integer peek(){ if (size == 0){ return null; } return data[size-1]; }

链表实现

class Node{ int val; Node next; public Node(int val) { this.val = val; }}public class MyStack2 { //此处以不带傀儡节点的链表为例 private Node head = null;}

入栈：头插

public void push(int val){ //step1：创建新节点 Node newNode = new Node(val); //2、把新节点进行头插，由于当前链表是不带傀儡的， // 所以需要判断当前链表是非空还是空 if (head == null){ head = newNode; return; } newNode.next = head; //让 newNode 指向原头结点 head = newNode; //更新 head }

出栈：头删

public Integer pop(){ //进行头删，若是空链表 if (head == null){ return null; } //只有一个节点的链表 if (head.next == null){ int ret = head.val; head = null; return ret; } // 其他一般情况 // java中节点的删除主要看该对象是否有引用指向他， // 若是无引用指向该对象，则表示该对象被删除(GC垃圾回收) int ret = head.val; head = head.next; return ret; }

取栈顶元素：取头结点

public Integer pip(){ if (head == null){ return null; } return head.val; }

二、队列

核心思想：先进先出

顺序表（数组）实现：

入队列：尾插

public boolean offer(int val){ //队列满了,也可以实现扩容逻辑 if (size == data.length){ return false; } //队列没满的情况下可以把新元素放到tail对应的下标上 data[tail] = val; tail++; //一旦tail到达队列的末尾就要让其从头开始 //方法1： if (tail == data.length){ tail = 0; } //方法2： tail = tail % data.length; size++; //更新 size 的值 return true; }

出队列：尾删

public Integer poll(){ if (size == 0){ return null; } int ret = data[head]; head++; //更新 head 的位置 if (head == data.length){ head = 0; } size--; return ret; }

取队顶元素：根据下标获取元素

public Integer peek(){ if (size == 0){ return null; } return data[head]; }

链表实现

//链表实现队列public class MyQueue { //创建链表 static class Node{ int val; Node next; public Node(int val) { this.val = val; } } //创建一个链表并记录其头结点和尾结点 private Node head = null; private Node tail = null;}

入队：尾插

返回值表示是否插入成功

public boolean offer(int val){ //创建新节点 Node newNode = new Node(val); //若是空链表,直接让 head 和 tail 指向新节点即可 if (head == null){ head = newNode; tail = newNode; return true; } //一般情况的尾插 tail.next = newNode; tail = tail.next; return true; }

出队：头删

public Integer poll(){ if (head == null){ return null; } int ret = head.val; if (head.next == null){ return ret; } head = head.next; //删除头结点 return ret; }

取队首元素：获取头结点

public Integer peek(){ if (head == null){ return null; } return head.val; }

三、标准库中的栈和队列

标准库中，栈（Stack）是一个类，可以直接使用；队列（Queue）是一个接口，不能直接实例化，需要创建对应的子类。Stack 继承自 Vector。