Java面试题之栈和队列的实现

在Java面试中，栈和队列的实现是常见的考点。了解它们的原理和实现方式，对于Java开发者来说至关重要。

栈是一种后进先出（LIFO）的数据结构。在Java中，可以使用数组或链表来实现栈。使用数组实现栈时，需要定义一个数组来存储元素，并维护一个栈顶指针。当入栈操作时，将元素放入栈顶位置，并更新栈顶指针；出栈操作则取出栈顶元素，并将栈顶指针下移。

以下是一个简单的基于数组的栈实现示例：

class ArrayStack {
    private int[] stack;
    private int top;

    public ArrayStack(int size) {
        stack = new int[size];
        top = -1;
    }

    public void push(int item) {
        if (top == stack.length - 1) {
            System.out.println("Stack is full");
        } else {
            stack[++top] = item;
        }
    }

    public int pop() {
        if (top == -1) {
            System.out.println("Stack is empty");
            return -1;
        } else {
            return stack[top--];
        }
    }
}

队列是一种先进先出（FIFO）的数据结构。同样可以用数组或链表实现。用数组实现队列时，需要维护队头和队尾指针。入队操作在队尾添加元素，出队操作从队头取出元素。

以下是一个简单的基于数组的队列实现示例：

class ArrayQueue {
    private int[] queue;
    private int front;
    private int rear;

    public ArrayQueue(int size) {
        queue = new int[size];
        front = 0;
        rear = -1;
    }

    public void enqueue(int item) {
        if (rear == queue.length - 1) {
            System.out.println("Queue is full");
        } else {
            queue[++rear] = item;
        }
    }

    public int dequeue() {
        if (front > rear) {
            System.out.println("Queue is empty");
            return -1;
        } else {
            return queue[front++];
        }
    }
}

在面试中，除了能够正确实现栈和队列，还需要理解它们的时间复杂度、空间复杂度以及适用场景等。掌握这些知识，能让你在面试中更加自信地应对相关问题。