栈和队列

栈和队列是两种操作受限的线性表
这种受限表现在：
栈的输入和删除只允许在表的尾端进行（在栈中有一个名次叫做"栈顶"），规则 FIFO：FIRST IN LAST OUT
队列只允许在表尾插入元素，在表头删除元素，FIFO：FIRST IN FIRST OUT

栈与队列的相同点

都是线性结构
插入操作都是在表尾进行
都可以通过顺序结构和链式结构实现

注意

这里的栈和队列我使用了单链表Node类和SuperLinked类来实现机制

Node类

public class Node {
    private Integer data;
    private Node next;
    public Integer getData() {
        return data;
    }
    public void setData(Integer data) {
        this.data = data;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
    public Node() {
    }
    public Node(Integer data, Node next) {
        this.data = data;
        this.next = next;
    }
}

SuperLinked类

public class SuperLinked {
    private int size;
    private Node first;
    private Node last;

    public SuperLinked() {
    }
    public boolean add(Integer data){
        Node node = new Node(data,null);
        if(first == null) {
            first = node;
        }else {
            last.setNext(node);
        }
        last = node;
        size++;
        return true;
    }
    public boolean addIndex(Integer data,Integer index) {
        if (index ==0) {
            Node node = new Node(data,first);
            first = node;
        } else {
            Node preNode = getNode(index-1);
            Node node = new Node(data,preNode.getNext());
            preNode.setNext(node);
        }
        size++;
        return true;
    }
    public void delTop() {
        if (first!=null) {
            first=first.getNext();
            size--;
        }
    }
    public void delLast() {
        if (first!=null) {
            getNode(size-2).setNext(null);
            size--;
        }
    }
    public void delIndex(int index) {
        Node cursor = new Node();
        if (first!=null) {
            getNode(index-1).setNext(getNode(index-1).getNext().getNext());
            size--;
        }
    }
    public boolean del(Integer data) {
        Node preNode = first;
        Node cursor = first;
        for (int i = 0; i <= size; i++) {
            preNode = cursor;
            cursor = cursor.getNext();
            if (cursor.getData().equals(data)) {
                preNode.setNext(cursor.getNext());
                break;
            }
        }
        size--;
        return true;
    }
    public Node getNode(int index){
        if(index < 0){
            index = 0;
        }
        if(index >= size - 1){
            index = size - 1;
        }
        Node cursor = first;
        for (int i = 0; i < index; i++) {
            cursor = cursor.getNext();
        }
        return cursor;
    }
    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public Node getFirst() {
        return first;
    }

    public void setFirst(Node first) {
        this.first = first;
    }

    public Node getLast() {
        return last;
    }

    public void setLast(Node last) {
        this.last = last;
    }
}

栈

public class Stack {

    private SuperLinked superLinked = new SuperLinked();

    public void push(Integer item) {
        superLinked.add(item);
    }

    public void peek() {
        System.out.println(superLinked.getLast().getData());
    }

    public void pop() {
        superLinked.delLast();
    }

    public boolean empty() {
        return superLinked.getSize() == 0;
    }
}

队列

public class Queue {

    private SuperLinked superLinked = new SuperLinked();

    public void add(Integer item) {
        superLinked.add(item);
    }

    public Integer poll() {
        if (superLinked == null) {
            return -1;
        }
        int temp = superLinked.getNode(0).getData();
        superLinked.delTop();
        return temp;
    }

    public boolean empty() {
        return superLinked.getSize() == 0;
    }
}

注意

我整个栈和队列的机制都非常简单
没有做异常处理，即超出范围的操作，正常使用是没有任何问题的

运用队列的实例程序

制作了一个银行实例程序，只有简单的取票和叫号机制
当所有号码全部取出后，可以继续输入要发出的账号

public class BankTicketMachine {

    private Queue queue = new Queue();

    private int startNumber = 100;

    private Scanner scanner = new Scanner(System.in);

    public Integer getTicket() {
        if (queue.empty()) {
            System.out.println("号码已经全部领取，需要继续释放号码！");
            System.out.println("请输入释放号码的个数：");
            int number = scanner.nextInt();
            pushTicket(number);
        }
        return queue.poll();
    }

    public void pushTicket(int ticketNumber) {
        for (int i = 0; i < ticketNumber; i++) {
            startNumber+=1;
            queue.add(startNumber);
        }
    }

    public void run() {
        while (true) {
            System.out.println("请输入你的名字");
            String name = scanner.next();
            Integer ticket = getTicket();
            System.out.println("尊敬的「"+name+"」，你的号码是：+"+ticket);
        }
    }

    public static void main(String[] args) {
        new BankTicketMachine().run();
    }
}

Java ｜栈与队列