单链表与队列和栈

单链表与队列和栈

使用单链表实现队列

队列是一个先进先出的数据结构，它包括进队、出队、获取队列大小等功能。

代码：

/**
 * 使用单链表实现队列
 * 队列是一个先进先出的数据结构,有进队列出队列,计算队列的大小等
 */
public class LinkedListImplementsQueue {
    //1.定义一个单链表的节点信息类
    public static class Node<V>{
        public V value;
        public Node<V> next;
        public Node(V v){
            value = v;
            next = null;
        }
    }

    //2.定义一个队列信息类
    public static class MyQueue<V>{
        //1.队列的头
        private Node<V> head;
        //2.队列的尾
        private Node<V> tail;
        //3.队列的大小
        private int size;
        public MyQueue(){
            head = null;
            tail = null;
            size = 0;
        }

        //1.判断队列是否为空
        public boolean isEmpty(){
            return size == 0;
        }
        //2.队列大小
        public int size(){
            return size;
        }
        //3.节点入队
        public void offer(V v) {
            //1.首先应该定义一个节点来接受新入队列的节点
            Node<V> current = new Node<>(v);
            //2.如果队列的尾部为空说明此时该队列是一个空队列，那么就让头部和尾部都指向该节点
            if(tail == null){
                head = current;
                tail = current;
            }else {
                //如果队列不为空
                tail.next = current;
                tail = current;
            }
            size++;
        }
        //4.节点出队列
        public V poll() {
            //首先定义一个变量接收出队列节点的值
            V ans = null;
            //出队列是从头部开始出因为队列是先进先出
            if(head != null){
                //首先记录头节点的值
                ans = head.value;
                //然后head向下走 不用管之前头节点的指针因为当它没有引用的时候jvm会自动回收
                head = head.next;
                //然后大小减一
                size--;
            }
            //最后返回出节点的值
            return ans;
        }
        //5.获取当前头节点的值
        public V peek() {
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }
    }
}

单链表实现栈

栈是一个先进后出的数据结构，它包括进栈、出栈、获取栈的大小等功能。

代码：

/**
 * 使用单链表实现栈,栈是一个先进后出的数据结构
 */
public class LinkedListImplementsStack {
    //1.定义一个单链表的节点信息类
    public static class Node<V>{
        public V value;
        public Node<V> next;
        public Node(V v){
            value = v;
            next = null;
        }
    }
    //2.定义一个栈的信息类
    public static class MyStack<V> {
        private Node<V> head;
        private int size;
        public MyStack(){
            head = null;
            size = 0;
        }

        //1.栈的大小是否为空
        public boolean isEmpty(){
            return size == 0;
        }
        //2.栈的大小
        public int size(){
            return size;
        }
        //3.进栈
        public void push(V v) {
            //1.首先定义一个节点用来接收进栈节点信息
            Node<V> current = new Node<>(v);
            //如果栈为空就将头节点指向此时进栈的节点
            if (head == null) {
                head = current;
            }else {
                //首先将新进入节点的next指向原来的head
                current.next = head;
                //再将原来的head指向新进入的节点
                head = current;
            }
            //最后size加一
            size++;
        }
        //4.出栈
        public V pop() {
            //1.首先定义一个变量用来接收出栈节点的值
            V ans = null;
            //2.当head!=null的时候进行出栈
            if(head!=null){
                //先记录head节点的值
                ans = head.value;
                //然后head指向head的下一个节点
                head = head.next;
                //最后size--
                size--;
            }
            //最后返回ans
            return ans;
        }
        //5.获取栈顶节点的值
        public V peek() {
            return head != null ? head.value : null;
        }
    }
}