单列表singleList模拟栈Stack数据结构

栈的简单介绍

1. 栈是一种先入后出，后入先出的有序列表
2. 栈是限制线性表中的元素的插入和删除只能在线性表的同一端进行的一种特殊线性表，允许插入和删除的一端，为变化的一端，称为栈顶（top）,另一端为固定的一端，称为栈底（Bottom）。

单列表的节点介绍

使用单列表模拟栈的底层实现

package stack;


import java.util.Scanner;


public class singleListStackDemo {
    public static void main(String[] args) {

        //用单列表->表示栈
        singleListStack stack = new singleListStack();

        singleList list1 = new singleList(1,"stack1");
        singleList list2 = new singleList(2,"stack2");
        singleList list3 = new singleList(3,"stack3");
        singleList list4 = new singleList(4,"stack4");

        stack.push(list1);
        stack.push(list2);
        stack.push(list3);
        stack.push(list4);

        // 出栈
        System.out.println("出栈---后入先出");
        System.out.println(stack.pop());
        System.out.println(stack.pop());

        System.out.println("遍历");
        stack.list();

        System.out.println("程序退出~~~");

    }
}

// 单向列表模拟栈
class singleListStack {

    //先初始化一个头节点, 头节点不要动, 不存放具体的数据
    private singleList head = new singleList(0, "");

    //返回头节点
    public singleList getHead() {
        return head;
    }

    // 入栈
    public void push(singleList singleList) {
        singleList temp = this.head;
        while (true) {
            if (temp.next == null) {//说明找到了尾节点
                break;
            }
            temp = temp.next; // 向后移，直至找到尾节点为null
        }
        temp.next = singleList;
    }

    // 出栈
    // 栈是先进后出，后入先出，所以将挂在最后的节点先pop
    public singleList pop() {
        singleList temp = this.head;
        while (true) {
            if (temp.next.next == null) {//说明找到了尾节点
                break;
            }
            temp = temp.next; // 向后移，直至找到尾节点为null
        }
        singleList val = temp.next;
        temp.next = null;
        return val;
    }

    // 遍历栈 先进后出，后入先出
    // 使用栈的逆序
    public void list() {
        // 创建新的单节点 存放逆序的数据
        singleList reverseSingleList = new singleList(0, "");

        // 创建临时中转节点。
        singleList cur = head.next;
        singleList next = null;
        while (cur != null) {
            next = cur.next; // 存放后面节点的值
            cur.next = reverseSingleList.next; // 用老单列表指向新单列表的头部
            reverseSingleList.next = cur; // 画图分析
            cur = next;
        }
        //head.next = reverseSingleList.next; // 在将原来的头节点next指向逆序后的单列表
        // 此处不能改变原来节点的顺序  逆序后就达到了后进先出 在遍历即可
        singleList temp = reverseSingleList.next;
        if(temp == null){
            throw new RuntimeException("栈空，无法遍历数据！");
        }
        while (true){
            System.out.printf("stack=%sn",temp.toString());
            if(temp.next ==null){
                break;
            }
            temp=temp.next;// 向后移
        }


    }


}


class singleList { //成员内部类
    int no;
    String name;
    singleList next;

    public singleList(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "singleList{" +
                "no=" + no +
                ", name='" + name + ''' +
                '}';
    }
}

使用数组模拟栈的底层实现

package stack;


public class ArrayStackDemo {
}

// 栈的数组模拟

class ArrayStack {

    private int top = -1;
    private int[] arr;
    private int maxSize;

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

    // 判断栈是否满了
    public boolean isFull() {
        return top == maxSize - 1;
    }

    // 判断栈空
    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("栈满，无法加入数据~");
        }
        top++;
        arr[top] = value;
    }

    // 出栈
    public int pop() {
        // 从上往下取
        if (isEmpty()) {
            throw new RuntimeException("栈空，无法取数据~");
        }
        int value = arr[top];
        top--;
        return value;
    }

    // 遍历栈
    public void list(){
        // 从上往下取
        if (isEmpty()) {
            throw new RuntimeException("栈空，无法取数据~");
        }
        for (int i = top; i >=0 ; i--) {
            System.out.printf("stack[%d]=%d",i,arr[i]);
        }

    }


}