Java中两种方法实现栈和队列(面试)

学到LinkedList，上课时老师提了一下代码实现栈和队列，面试可能会用上，就码了栈和队列两种实现方案。如有问题，希望指出。

一、栈

1.数组实现栈

/*
    利用数组的方式实现一个栈
    栈的特点:  存储数据 -- 先进后出(就像弹夹)
    定义一个栈类:
    成员变量:
    1.存储数据的数组
    2.栈容量
    3.栈顶索引
    成员方法:
    1.压入数据方法
    2.取出数据方法

 */
public class Stack {

    private int[] data;
    private int size;
    private int stackTop = -1;  //记录栈顶索引, 默认空, 索引-1

    //构造方法
    public Stack(int size) {
        this.size = size;
        this.data = new int[size];
    }

    public boolean push(int data) {     //压栈方法
        if (stackTop + 1 == size) {
            System.out.println("栈已满");
            return false;
        }
        this.data[++stackTop] = data;       //栈顶默认值为-1,所以要先加后充当索引
        return true;
    }

    public int pop() throws Exception {   //出栈方法
        if (stackTop == -1) {
            throw new Exception("栈已空");
        }
        return data[stackTop--];    //返回数据后栈顶后移
    }
}

class StackDemo {
    public static void main(String[] args) throws Exception {

        Stack s = new Stack(5);
        //s.pop();  //报栈空

        //压栈
        for (int i = 1; i <= 5; i++) {
            System.out.println(s.push(i));
        }
        //s.push(6);    //报栈满

        //出栈
        for (int i = 0; i < 5; i++) {
            System.out.println(s.pop());
        }

    }
}

2.LinkedList实现栈

import java.util.LinkedList;

/*
    使用 LinkedList类 实现栈
    LinkedList类: 底层是链表  特点: 查询慢, 增删快

     特有功能:
     public void addFirst(E e): 在该列表开头插入指定元素
     public void addLast(E e):  将指定元素追加到此列表的末尾

     public E getFirst():   返回此列表中的第一个元素
     public E getLast():    返回此列表中的最后一个元素

     public E removeFirst(): 从此列表中删除并返回第一个元素
     public E removeLast():  从此列表中删除并返回最后一个元素
 */
public class Stack {
    private LinkedList<Integer> list = new LinkedList<>();
    private int size;   //栈的大小

    //构造方法
    public Stack(int size) {
        this.size = size;
    }

    //压栈方法
    public boolean push(int data) {
        if (list.size() == size) {
            System.out.println("栈已满");
            return false;
        }
        list.addLast(data); //直接使用LinkedList的方法往后添加元素
        return true;
    }

    //出栈方法
    public int pop() throws Exception {
        if (list.size() == 0) {
            throw new Exception("栈已空");
        }
        return list.removeLast();   //删除并返回最后一个元素
    }
}

class StackDemo {
    public static void main(String[] args) throws Exception {
        Stack s = new Stack(5);

        //s.pop();    //报栈空
        //压栈
        for (int i = 1; i <= 5; i++) {
            s.push(i);
        }

        //s.push(6);  //报栈满

        //出栈
        for (int i = 0; i < 5; i++) {
            System.out.println(s.pop());
        }
        //s.pop();    //报栈空
    }
}

二、队列

1.数组实现队列

/*
    数组实现队列
    队列的特点:  存储数据 -- 先进先出(排队)
    定义一个队列类:
    成员变量:
    1.存储数据的数组
    2.队列容量
    3.队列头部索引
    4.队列尾部索引
    成员方法:
    1.加入数据方法
    2.取出数据方法
 */
public class Queue {
    private int[] data;
    private int size;
    private int queueLast = -1;     //队列头索引
    private int queueFirst = -1;    //队列尾索引

    //构造方法
    public Queue(int size) {
        this.size = size;
        this.data = new int[size];
    }

    //入列
    public boolean inQueue(int data) {
        if (queueLast + 1 == size) {
            System.out.println("队列已满");
            return false;
        }
        this.data[++queueLast] = data;
        return true;
    }

    //出列
    public int outQueue() throws Exception {
        if (queueFirst == queueLast) {
            throw new Exception("队列已空");
        }
        return data[++queueFirst];
    }
}

class QueueDemo {
    public static void main(String[] args) throws Exception {
        Queue q = new Queue(5);

        //q.outQueue();     //报队列空
        for (int i = 1; i <= 5; i++) {
            q.inQueue(i);
        }

        //q.inQueue(6);   //报队列满

        for (int i = 0; i < 5; i++) {
            System.out.println(q.outQueue());
        }

        //q.outQueue();   //报队列空
    }
}

2.LinkedList实现队列

import java.util.LinkedList;

/*
    LinkedList实现队列
 */
public class Queue {
    private LinkedList<Integer> list = new LinkedList<>();
    private int size;

    //构造方法
    public Queue(int size) {
        this.size = size;
    }

    //入队列方法
    public boolean inQueue(int data) {
        if (list.size() == size) {
            System.out.println("队列已满");
            return false;
        }
        list.addLast(data);    //从头添加元素
        return true;
    }

    //出队列方法
    public int outQueue() throws Exception {
        if (list.size() == 0) {
            throw new Exception("队列已空");
        }
        return list.removeFirst();  //从头删除元素并返回元素
    }

}

class QueueDemo {
    public static void main(String[] args) throws Exception {
        Queue q = new Queue(5);

        //q.outQueue();   //报队列空

        for (int i = 1; i <= 5; i++) {
            q.inQueue(i);
        }

        //q.inQueue(6);   //报队列满

        for (int i = 0; i < 5; i++) {
            System.out.println(q.outQueue());
        }

        //q.outQueue();       //报队列空
    }
}