数据结构面试题总结

本文总结面试题：

1. 用Java实现一个栈
2. 用Java实现一个队列
3. 用Java实现一个链表

1. 用Java实现一个栈

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;

// 使用泛型，兼容各种数据类型
public class MyStack<T> {

    private List<T> stack = new ArrayList<>();

    // 入栈
    public void push(T item) {
        stack.add(item);
    }

    // 出栈
    public T pop() {
        if (stack.isEmpty()) {
            throw new EmptyStackException();
        }
        // 把最后一个元素删掉
        T item = stack.remove(stack.size() -1);
        return item;
    }

    // 查看栈顶元素
    public T peek() {
        if(stack.isEmpty()) {
            throw new EmptyStackException();
        }
        // 3-1=2 也就是栈顶的元素，指定了下标的位置
        return stack.get(stack.size() -1);
    }

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

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

}

public class MyStackTest {

    public static void main(String[] args) {

        MyStack<Integer> stack = new MyStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("栈顶元素" + stack.peek());
        System.out.println("出栈元素" + stack.pop());
        System.out.println("栈的大小" + stack.size());
    }
}

运行结果：

栈顶元素3
出栈元素3
栈的大小2

2. 用Java实现一个队列

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class MyQueue<T> {

    // 声明队列
    private BlockingQueue<T> queue = new LinkedBlockingQueue<>();

    // 入队列
    public void add(T t) {
        queue.add(t);
    }

    // 出队列
    public T get() throws InterruptedException {
        if(queue.isEmpty()) {
            return null;
        }
        return queue.take();
    }
}

public class MyQueueTest {

    public static void main(String[] args) throws InterruptedException {
        MyQueue<String> myQueue = new MyQueue<>();
        myQueue.add("1");
        myQueue.add("2");
        myQueue.add("3");
        System.out.println(myQueue.get());
        System.out.println(myQueue.get());
        System.out.println(myQueue.get());
    }
}

运行结果：

1
2
3

3. 用Java实现一个链表

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public class MyLinkedList {
    private ListNode head;

    /**
     * 链表新增数据
     * @param val
     */
    public void insert(int val) {
        ListNode newNode = new ListNode(val);
        // 链表为空，则保存到当前节点
        if(head == null) {
            head = newNode;
        } else {
            // 链表不为空，则向链表下一个节点寻找，直到为空为止
            ListNode current = head;
            while(current.next != null) {
                current = current.next;
            }
            // 直到下一个节点为空，则插入当前新增的节点
            current.next = newNode;
        }
    }

    /**
     * 链表删除数据
     * @param val
     */
    public void delete(int val) {
        // 如果链表为空，则直接返回
        if(head == null) {
            return;
        }
        // 如果是头节点，把下一个节点的值赋值给头节点
        if(head.val == val) {
            head = head.next;
            return;
        }
        // 否则不是头节点，通过遍历直到找到存储对应值那个节点，然后把那个节点的后一个节点往前挪，当前节点就失去了引用
        ListNode current = head;
        while(current.next != null && current.next.val != val) {
            current = current.next;
        }
        if(current.next != null) {
            current.next = current.next.next;
        }
    }

    /**
     * 展示链表上的所有值
      */
    public void display() {
        ListNode current = head;
        while(current != null) {
            System.out.println(current.val + "");
            current = current.next;
        }
        System.out.println();
    }
}

public class MyLinkedListTest {

    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.display();
        list.delete(2);
        list.display();
    }
}

运行结果：

1
2
3

1
3