Java中实现栈和队列的函数详解

栈和队列都是在计算机中常见的数据结构，它们的出现大大方便了我们在编程中的操作。在Java中，我们可以利用数组和链表等数据结构来实现栈和队列。本篇文章将详细介绍Java中实现栈和队列的函数。

1. 栈的实现

栈是一种先进后出的数据结构，在Java中可以使用数组和链表来实现。以下是使用数组实现栈的代码：

public class ArrayStack {
    private int[] array;
    private int top;    // 栈顶指针

    public ArrayStack(int size) {
        array = new int[size];
        top = -1;    // 初始化栈顶指针
    }

    public void push(int element) {
        if (top + 1 == array.length) {
            throw new RuntimeException("Stack is full.");
        }
        array[++top] = element;
    }

    public int pop() {
        if (top == -1) {
            throw new RuntimeException("Stack is empty.");
        }
        return array[top--];
    }

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

    public int size() {
        return top + 1;
    }
}

上述代码中，我们使用数组来存储栈中的元素，同时使用栈顶指针来指示栈的状态。push()方法用于将元素压入栈中，pop()方法用于将元素弹出栈，isEmpty()方法用于判断栈是否为空，size()方法用于返回栈的元素个数。

以下是使用链表实现栈的代码：

public class LinkedStack<T> {
    private static class Node<T> {
        private T data;
        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> top;    // 栈顶节点

    public void push(T element) {
        Node newNode = new Node(element, top);
        top = newNode;
    }

    public T pop() {
        if (top == null) {
            throw new RuntimeException("Stack is empty.");
        }
        T data = top.data;
        top = top.next;
        return data;
    }

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

    public int size() {
        int count = 0;
        Node p = top;
        while (p != null) {
            count++;
            p = p.next;
        }
        return count;
    }
}

上述代码中，我们使用链表来存储栈中的元素，同时使用一个指针top来指向栈顶节点。push()方法用于将元素压入栈中，pop()方法用于将元素弹出栈，isEmpty()方法用于判断栈是否为空，size()方法用于返回栈的元素个数。

2. 队列的实现

队列是一种先进先出的数据结构，在Java中可以使用数组和链表来实现。以下是使用数组实现队列的代码：

public class ArrayQueue {
    private int[] array;
    private int front;    // 队列头指针
    private int rear;    // 队列尾指针

    public ArrayQueue(int size) {
        array = new int[size];
        front = rear = -1;    // 初始化队列头和尾指针
    }

    public void enqueue(int element) {
        if (rear + 1 == array.length) {
            throw new RuntimeException("Queue is full.");
        }
        array[++rear] = element;
    }

    public int dequeue() {
        if (front == rear) {
            throw new RuntimeException("Queue is empty.");
        }
        return array[++front];
    }

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

    public int size() {
        return rear - front;
    }
}

上述代码中，我们使用数组来存储队列中的元素，同时使用队列头和尾指针来指示队列的状态。enqueue()方法用于将元素加入队列，dequeue()方法用于将元素移出队列，isEmpty()方法用于判断队列是否为空，size()方法用于返回队列的元素个数。

以下是使用链表实现队列的代码：

public class LinkedQueue<T> {
    private static class Node<T> {
        private T data;
        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> front;    // 队列头节点
    private Node<T> rear;    // 队列尾节点

    public void enqueue(T element) {
        Node newNode = new Node(element, null);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public T dequeue() {
        if (front == null) {
            throw new RuntimeException("Queue is empty.");
        }
        T data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return data;
    }

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

    public int size() {
        int count = 0;
        Node p = front;
        while (p != null) {
            count++;
            p = p.next;
        }
        return count;
    }
}

上述代码中，我们使用链表来存储队列中的元素，同时使用队列头和尾节点来指示队列的状态。enqueue()方法用于将元素加入队列，dequeue()方法用于将元素移出队列，isEmpty()方法用于判断队列是否为空，size()方法用于返回队列的元素个数。

总结：

栈和队列都是非常常用的数据结构，在Java中的实现也非常简单。我们可以使用数组或链表来存储栈和队列中的元素，同时使用指针或节点来指示它们的状态。以上是本文对Java中实现栈和队列的函数进行的详细介绍，希望能对大家有所帮助。