从队列到栈：深入研究Java中常见的线性数据结构及其实现方法

从栈到队列：探索Java中常见的线性数据结构及其实现方式

引言：
在计算机科学中，数据结构是组织和存储数据的一种方式。线性数据结构是其中之一，它的特点是数据元素之间存在明确的前后关系。在Java开发中，常见的线性数据结构包括栈和队列，它们的使用频率非常高。本文将深入探索栈和队列在Java中的实现方式，并提供具体的代码示例。

一、栈的概念及实现方式：
栈是一种后进先出（Last In First Out, LIFO）的数据结构。它的特点是只能在栈顶进行插入和删除操作。在Java中，栈的常见实现方式有两种：基于数组的实现和基于链表的实现。

1. 基于数组的栈实现：
   数组是一种连续存储的数据结构，非常适合用来实现栈。下面是一个基于数组的栈类的示例代码：

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

    public ArrayStack(int capacity) {
        stack = new int[capacity];
        top = -1;
    }

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

    public boolean isFull() {
        return top == stack.length - 1;
    }

    public void push(int item) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = item;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }
}

2. 基于链表的栈实现：
   链表是一种非连续存储的数据结构，同样适合用来实现栈。下面是一个基于链表的栈类的示例代码：

public class LinkedStack {
    private Node top;

    public LinkedStack() {
        top = null;
    }

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

    public void push(int item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
    }

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

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

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

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

二、队列的概念及实现方式：
队列是一种先进先出（First In First Out, FIFO）的数据结构。它的特点是只能在队尾插入元素，在队头删除元素。在Java中，队列的常见实现方式有两种：基于数组的实现和基于链表的实现。

1. 基于数组的队列实现：
   与基于数组的栈实现类似，下面是一个基于数组的队列类的示例代码：

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

    public ArrayQueue(int capacity) {
        queue = new int[capacity + 1];  // 额外预留一个空位
        front = rear = 0;
    }

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

    public boolean isFull() {
        return (rear + 1) % queue.length == front;
    }

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

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int item = queue[front];
        front = (front + 1) % queue.length;
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }
}

2. 基于链表的队列实现：
   与基于链表的栈实现类似，下面是一个基于链表的队列类的示例代码：

public class LinkedQueue {
    private Node front;  // 队头指针
    private Node rear;  // 队尾指针

    public LinkedQueue() {
        front = null;
        rear = null;
    }

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

    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

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

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return front.data;
    }

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

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

结论：
栈和队列是Java中常用的线性数据结构，有多种实现方式。本文介绍了基于数组和基于链表的栈、队列实现，并提供了具体的代码示例。开发者可以根据实际需求选择合适的实现方式，以提高程序的效率和可维护性。