Java函数实现队列和栈的数据结构

队列和栈是常见的数据结构，用于解决不同的问题。在Java中，可以使用数组或链表来实现队列和栈。

1. 队列的实现

队列是一种FIFO（First In First Out）的数据结构，其中元素按照插入的顺序进行处理。Java中可以通过数组或链表实现队列。

使用数组实现队列的关键是需要两个指针front和rear分别指向队头和队尾。根据队尾指针的位置，判断队列是空还是满。

以下是使用数组实现队列的Java代码：

public class Queue {
    private int capacity; // 队列容量
    private int front; // 队头指针
    private int rear; // 队尾指针
    private int[] queueArray; // 存储队列元素的数组

    public Queue(int size) {
        capacity = size;
        front = 0;
        rear = -1;
        queueArray = new int[capacity];
    }

    // 入队列
    public void enqueue(int element) {
        if (isFull()) {
            System.out.println("Queue is full. Unable to enqueue element.");
        } else {
            rear++;
            if (rear == capacity) {
                rear = 0;
            }
            queueArray[rear] = element;
            System.out.println("Enqueued element: " + element);
        }
    }

    // 出队列
    public void dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Unable to dequeue element.");
        } else {
            int element = queueArray[front];
            front++;
            if (front == capacity) {
                front = 0;
            }
            System.out.println("Dequeued element: " + element);
        }
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (rear + 1 == front || front + capacity - 1 == rear);
    }

    // 判断队列是否已满
    public boolean isFull() {
        return (rear + 2 == front || front + capacity - 2 == rear);
    }
}

使用链表实现队列时，只需维护一个指向队头和队尾的指针即可。以下是使用链表实现队列的Java代码：

public class Queue {
    private Node front;
    private Node rear;

    private class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    // 入队列
    public void enqueue(int element) {
        Node newNode = new Node(element);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        System.out.println("Enqueued element: " + element);
    }

    // 出队列
    public void dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Unable to dequeue element.");
        } else {
            int element = front.data;
            front = front.next;
            if (front == null) {
                rear = null;
            }
            System.out.println("Dequeued element: " + element);
        }
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (front == null && rear == null);
    }
}

2. 栈的实现

栈是一种LIFO（Last In First Out）的数据结构，其中最后一个插入的元素最先被处理。在Java中，栈可以用数组或链表实现。

使用数组实现栈时，需要维护一个指针top，指向栈顶。根据top的位置，判断栈是否为空或满。

以下是使用数组实现栈的Java代码：

public class Stack {
    private int capacity; // 栈容量
    private int top; // 栈顶指针
    private int[] stackArray; // 存储栈元素的数组

    public Stack(int size) {
        capacity = size;
        top = -1;
        stackArray = new int[capacity];
    }

    // 入栈
    public void push(int element) {
        if (isFull()) {
            System.out.println("Stack is full. Unable to push element.");
        } else {
            top++;
            stackArray[top] = element;
            System.out.println("Pushed element: " + element);
        }
    }

    // 出栈
    public void pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Unable to pop element.");
        } else {
            int element = stackArray[top];
            top--;
            System.out.println("Popped element: " + element);
        }
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return (top == -1);
    }

    // 判断栈是否已满
    public boolean isFull() {
        return (top == capacity - 1);
    }
}

使用链表实现栈时，只需维护一个指向栈顶的指针即可。以下是使用链表实现栈的Java代码：

public class Stack {
    private Node top;

    private class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    // 入栈
    public void push(int element) {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
        System.out.println("Pushed element: " + element);
    }

    // 出栈
    public void pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Unable to pop element.");
        } else {
            int element = top.data;
            top = top.next;
            System.out.println("Popped element: " + element);
        }
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return (top == null);
    }
}

以上是使用Java实现队列和栈的简单代码。在实际应用中，还可以根据需要添加其他功能，如获取队头元素、获取栈顶元素等。