JZTXT

使用链表模拟队列和栈

发布时间 2023-09-29 16:25:53作者: DogLeftover

使用链表模拟队列

  • 案例1
// 创建节点类
public class Node {
    int n;
    Node next;
}

// 编写方法
public class Queue {

    Node head = new Node();

    Node last = new Node();

    private int len=0;

    public int size(){
        return this.len;
    }

    // 添加
    public void add(int n){
        // 新建元素节点
        Node node=new Node();
        node.n=n;
        // 当第一次添加时
        if (head.next==null){
            head.next=node;
            last.next=node; // 让新节点放到last节点后
            //
            len++;
        }else {
            // 已经有数据时
            // [head|][10|][|]
            Node node1= last.next;  // Node node1= head.next; 这里取出10这个节点
            node1.next=node;   // 让10这个节点指向新节点
            last.next=node;    // 让新节点作为last节点
            //
            len++;
        }
    }

    // 获取
    public int get(){
        // 取出头节点后的第一个节点中的值
        Node node= head.next;
        int n= node.n;
        // 头节点指向下下一个节点
        head.next=node.next;
        //
        len--;
        return n;
    }

}
  • 测试
public class test {
    public static void main(String[] args) {
        Queue queue=new Queue();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        queue.add(40);
        queue.add(50);

        // 取出
        while (queue.size()>0){
            System.out.println(queue.get());
        }

    }
}

使用链表模拟栈

  • 案例1
// 创建节点类
public class Nod {
    int n;
    Nod top;
    Nod next;
}

// 编写方法
public class Zan {

    Nod head = new Nod();

    Nod last = new Nod();

    private int len=0;

    public int size(){
        return this.len;
    }

    // 添加
    // [head|][|][|]
    public void add(int n){
        // 新建元素节点
        Nod nod=new Nod();
        nod.n=n;
        // 当第一次添加时
        if (head.next==null){
            head.next=nod; // 新节点放在头节点后
            last.next=nod; // 让新节点放到last节点后
            nod.top=last;  // 新节点的top中存放last节点的地址
            //
            len++;
        }else {
            // 已经有数据时
            // [head|][10|][|]
            Nod nod1= last.next;  // Node node1= head.next; 这里取出10这个节点
            nod1.next=nod;   // 让10这个节点指向新节点
            nod.top=nod1;    // 让新节点的top指向10这个节点
            // 让last节点的next指向新节点，top指向新节点的前一个节点
            last.next=nod;
            last.top=nod1;
            len++;
        }
    }

    // 获取
    public int get(){
        // 取出last节点后面节点中的值
        Nod nod= last.next;
        int n= nod.n;
        // [head|][10|][20|]
        // 让last节点的next指向取出节点的前一个节点
        last.next=last.top;
        // 让last节点的top指向last节点的前一个节点的前一个节点
        last.top=last.top.top;
        //
        len--;
        return n;
    }

}
  • 测试
public class test2 {
    public static void main(String[] args) {
        Zan zan= new Zan();
        zan.add(10);
        zan.add(20);
        zan.add(30);
        zan.add(40);
        zan.add(50);

        // 取出
        while (zan.size()>0){
            System.out.println(zan.get());
        }

    }
}
  • 案例2