【Java】用单向链表模拟栈

本文主要是介绍【Java】用单向链表模拟栈，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 单个节点Node：

class Node{
    private int no; 
    private String data;
    private Node next;

    public Node(int no, String data) {
        this.no = no;
        this.data = data;
    }

    public Node(int no, String data, Node next) {
        this.no = no;
        this.data = data;
        this.next = next;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", data='" + data + '\'' +
                '}';
    }
}

 用单向链表模拟栈，栈的特点是先入后出

//用单向链表模拟栈，栈的特点是先入后出
public class SingleLinkedListStack {

    private int maxSize; //最大容量
    private Node topNode; //栈顶节点，指向链表的最前端
    private int nodeCount; //栈内元素个数

    public SingleLinkedListStack(int maxSize){
        this.maxSize = maxSize;
    }

    //判断栈满
    public boolean isFull(){
        return nodeCount == maxSize;
    }

    //判断栈空
    public boolean isEmpty(){
        return nodeCount == 0;
    }

    //入栈
    public void push(Node node){ 
        if (isFull()){
            System.out.println("栈满！");
            return;
        }
        topNode = new Node(node.getNo(),node.getData(),topNode); //新入栈的节点指向原先的栈顶节点，新入栈的节点为新的topNode，即新入栈的节点被加在了链表的最前端
        nodeCount++; //计数器+1;
    }

    //出栈
    public Node pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空！");
        }
        if (topNode == null){ //topNode是否指向栈底，即是否指向链表尾
            throw new RuntimeException("栈空！");
        }
        Node res = new Node(topNode.getNo(),topNode.getData());
        topNode = topNode.getNext(); // 指针下移
        return res;
    }

    public void list(){
        if (isEmpty()){
            System.out.println("栈空！");
            return;
        }
        Node temp = topNode; //topNode不能随意更改，因此需要辅助指针temp
        while (true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.getNext(); //指针下移
        }
    }
}

测试：

public class SingleLinkedListStackDemo {

    public static void main(String[] args) {

        SingleLinkedListStack stack = new SingleLinkedListStack(4);
        Node node1 = new Node(1,"郭靖");
        Node node2 = new Node(2,"黄蓉");
        Node node3 = new Node(3,"杨过");
        Node node4 = new Node(4,"小龙女");
        stack.push(node1);
        stack.push(node2);
        stack.push(node3);
        stack.push(node4);
        stack.list();

        try {
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            System.out.println(stack.pop());
            
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }
}

这篇关于【Java】用单向链表模拟栈的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！