Java数据结构之栈与队列实例详解

Java数据结构之栈与队列实例详解攻略

简介

栈和队列是常见的数据结构，在Java中也有对应的实现方式。本文将介绍栈和队列的概念、常见实现方式、应用场景和两个示例。

栈

概念

栈是一种具有后进先出（Last In First Out）特性的数据结构。栈可以使用数组或链表实现。

常见实现方式

基于数组的栈实现

使用数组作为底层存储结构实现栈时，需要注意栈顶指针和数组的下标对应的关系。在栈中，栈顶指针指向栈顶元素的下标，而数组下标从0开始，因此需要额外维护一个变量记录栈顶指针。

public class ArrayStack<E> {

    private final Object[] arr;
    private int top = -1;

    public ArrayStack(int capacity) {
        arr = new Object[capacity];
    }

    public boolean push(E e) {
        if (top == arr.length - 1) {
            return false;
        }
        arr[++top] = e;
        return true;
    }

    public E pop() {
        if (top == -1) {
            return null;
        }
        return (E) arr[top--];
    }

    public E peek() {
        if (top == -1) {
            return null;
        }
        return (E) arr[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

}

基于链表的栈实现

使用链表作为底层存储结构实现栈时，每次插入或删除一个元素只需要改变指针的指向就可以了。

public class LinkedListStack<E> {

    private Node<E> top = null;

    private static class Node<E> {

        private final E value;
        private Node<E> next;

        public Node(E value) {
            this.value = value;
        }

    }

    public boolean push(E e) {
        Node<E> newNode = new Node<>(e);
        newNode.next = top;
        top = newNode;
        return true;
    }

    public E pop() {
        if (top == null) {
            return null;
        }
        E value = top.value;
        top = top.next;
        return value;
    }

    public E peek() {
        if (top == null) {
            return null;
        }
        return top.value;
    }

    public boolean isEmpty() {
        return top == null;
    }

}

应用场景

栈的应用场景非常广泛，下面简单列举一些：

1. 函数调用栈：在函数调用的时候，每个函数都有自己的局部变量和参数。这些变量和参数都保存在栈中，每次函数调用结束之后，这些变量和参数都会从栈中弹出。

2. 浏览器历史记录：在浏览器中，每次访问一个新的页面都会把这个页面的信息压入栈中，每次返回上一个页面的时候就从栈中弹出最新的页面信息。

3. 表达式求值：在计算机中，表达式求值的时候会用到栈。例如，中缀表达式需要转化成后缀表达式后再进行计算，转化过程中需要借助栈来存储操作符。

...

示例

示例一

给定一个仅由括号和字母组成的字符串，判断这个字符串中的括号是否成对出现。

例如：字符串“{}”是符合规则的，而字符串“{”就不符合规则。

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if (c == ')' && top != '(') {
                return false;
            }
            if (c == '}' && top != '{') {
                return false;
            }
            if (c == ']' && top != '[') {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

示例二

将一个数组中的元素从头到尾依次压入栈中，再依次从栈中弹出元素，输出的结果与原来的数组顺序相反。

public void reverse(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < nums.length; i++) {
        stack.push(nums[i]);
    }
    for (int i = 0; i < nums.length; i++) {
        nums[i] = stack.pop();
    }
}

队列

概念

队列是一种具有先进先出（First In First Out）特性的数据结构。队列也可以使用数组或链表实现。

常见实现方式

基于数组的队列实现

使用数组作为底层存储结构实现队列时，需要注意队头指针和队尾指针的指向关系。在队列中，队头指针指向队列中第一个元素，队尾指针指向队列中最后一个元素的下一个位置。在入队或出队的时候分别更新队尾指针和队头指针即可。

public class ArrayQueue<E> {

    private final Object[] arr;
    private int front = 0;
    private int rear = 0;

    public ArrayQueue(int capacity) {
        arr = new Object[capacity + 1];
    }

    public boolean enqueue(E e) {
        if (front == (rear + 1) % arr.length) {
            return false;
        }
        arr[rear] = e;
        rear = (rear + 1) % arr.length;
        return true;
    }

    public E dequeue() {
        if (front == rear) {
            return null;
        }
        E value = (E) arr[front];
        front = (front + 1) % arr.length;
        return value;
    }

    public E peek() {
        if (front == rear) {
            return null;
        }
        return (E) arr[front];
    }

    public boolean isEmpty() {
        return front == rear;
    }

}

基于链表的队列实现

使用链表作为底层存储结构实现队列时，入队和出队操作只需要改变指针的指向就可以了。

public class LinkedListQueue<E> {

    private Node<E> head = null;
    private Node<E> tail = null;

    private static class Node<E> {

        private final E value;
        private Node<E> next;

        public Node(E value) {
            this.value = value;
        }

    }

    public boolean enqueue(E e) {
        Node<E> newNode = new Node<>(e);
        if (tail == null) {
            head = newNode;
        } else {
            tail.next = newNode;
        }
        tail = newNode;
        return true;
    }

    public E dequeue() {
        if (head == null) {
            return null;
        }
        E value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }

    public E peek() {
        if (head == null) {
            return null;
        }
        return head.value;
    }

    public boolean isEmpty() {
        return head == null;
    }

}

应用场景

队列的应用场景也非常广泛，下面简单列举一些：

1. 任务队列：在线程池等多线程应用中，需要通过队列来存储任务，等待线程池中的线程来处理。

2. 消息队列：在分布式系统中，需要通过消息队列来协调各个模块的数据交换。

3. 广度优先搜索：在算法中，广度优先搜索需要用到队列。

...

示例

示例一

给定一个由数字组成的数组和一个数字k，求这个数组中所有长度为k的连续子数组的和。

例如：给定数组[1,2,3,4,5,6]和k=3，输出[6,9,12,15]。

public int[] findSubArraySum(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    LinkedListQueue<Integer> queue = new LinkedListQueue<>();
    int index = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        queue.enqueue(nums[i]);
        sum += nums[i];
        if (queue.size() > k) {
            sum -= queue.dequeue();
        }
        if (queue.size() == k) {
            result[index++] = sum;
        }
    }
    return result;
}

示例二

将一个数组中的元素从头到尾依次加入队列中，再依次从队列中取出元素，输出的结果与原来的数组顺序相同。

public void print(int[] nums) {
    LinkedListQueue<Integer> queue = new LinkedListQueue<>();
    for (int i = 0; i < nums.length; i++) {
        queue.enqueue(nums[i]);
    }
    while (!queue.isEmpty()) {
        System.out.println(queue.dequeue());
    }
}