Java实现栈和队列面试题

接下来我将详细讲解Java实现栈和队列面试题的完整攻略。

栈和队列

栈

栈是一种常见的数据结构，栈的特点是“后进先出(LIFO)”（Last In First Out）。也就是说，最新添加的元素最先被取出，而最旧的元素最后被取出。

队列

队列也是一种常见的数据结构，队列的特点是“先进先出(FIFO)”（First In First Out）。也就是说，最先添加的元素最先被取出，而最后添加的元素最后被取出。

Java实现栈和队列

接下来我将分别介绍Java实现栈和队列的方法。

Java实现栈

Java中可以使用Stack类或Deque接口来实现栈。

使用Stack类实现栈

import java.util.Stack;

public class MyStack {
    private Stack<Integer> stack = new Stack<>();

    public void push(int x) {
        stack.push(x);
    }

    public int pop() {
        return stack.pop();
    }

    public int peek() {
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

使用Deque接口实现栈

import java.util.ArrayDeque;
import java.util.Deque;

public class MyStack {
    private Deque<Integer> stack = new ArrayDeque<>();

    public void push(int x) {
        stack.push(x);
    }

    public int pop() {
        return stack.pop();
    }

    public int peek() {
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

Java实现队列

Java中可以使用Queue接口或Deque接口来实现队列。

使用Queue接口实现队列

import java.util.LinkedList;
import java.util.Queue;

public class MyQueue {
    private Queue<Integer> queue = new LinkedList<>();

    public void enqueue(int x) {
        queue.offer(x);
    }

    public int dequeue() {
        return queue.poll();
    }

    public int peek() {
        return queue.peek();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

使用Deque接口实现队列

import java.util.ArrayDeque;
import java.util.Deque;

public class MyQueue {
    private Deque<Integer> queue = new ArrayDeque<>();

    public void enqueue(int x) {
        queue.offer(x);
    }

    public int dequeue() {
        return queue.poll();
    }

    public int peek() {
        return queue.peek();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

下面我将给出两个示例说明。

示例一

假设有一个整数数组，要求倒序输出其中的元素。这个任务可以使用栈来完成。

int[] arr = {1, 2, 3, 4, 5};
MyStack stack = new MyStack();
for (int i = 0; i < arr.length; i++) {
    stack.push(arr[i]);
}
while (!stack.isEmpty()) {
    System.out.print(stack.pop() + " ");
}

输出结果为：5 4 3 2 1

示例二

假设有一个整数列表，要求先输出其中的偶数，在输出其中的奇数。这个任务可以使用队列来完成。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
MyQueue queue = new MyQueue();
for (int i = 0; i < list.size(); i++) {
    int x = list.get(i);
    if (x % 2 == 0) {
        queue.enqueue(x);
    }
}
for (int i = 0; i < list.size(); i++) {
    int x = list.get(i);
    if (x % 2 != 0) {
        queue.enqueue(x);
    }
}
while (!queue.isEmpty()) {
    System.out.print(queue.dequeue() + " ");
}

输出结果为：2 4 6 8 10 1 3 5 7 9

以上就是Java实现栈和队列面试题的完整攻略。