java栈与队列如何实现

java栈与队列如何实现

栈和队列是计算机科学中常用的数据结构，它们分别代表着后进先出（Last In First Out，简称LIFO）和先进先出（First In First Out，简称FIFO）的操作特性。在Java编程中，可以使用不同的方式来实现栈和队列。本文将介绍在Java中如何实现栈和队列，并分别讨论它们的特点和用法。

一、栈的实现

1. 使用数组实现栈

在Java中，可以使用数组来实现栈。栈的基本操作包括入栈（push）和出栈（pop）。通过数组，可以轻松地实现这些操作。

public class ArrayStack {
    private int[] arr;
    private int top;
    private int capacity;

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

    public void push(int data) {
        if (isFull()) {
            throw new IllegalStateException("Stack is full.");
        }
        arr[++top] = data;
    }

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return arr[top--];
    }

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

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

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return arr[top];
    }

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

2. 使用链表实现栈

除了数组，链表也可以用于实现栈。链表的插入和删除操作较数组更加高效，因此在某些场景下使用链表实现栈会更合适。

public class LinkedListStack {
    private Node top;

    private class Node {
        int data;
        Node next;

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

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

    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        int data = top.data;
        top = top.next;
        return data;
    }

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

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }
}

二、队列的实现

1. 使用数组实现队列

使用数组实现队列时，需要维护队列的头尾指针，以便进行入队（enqueue）和出队（dequeue）操作。

public class ArrayQueue {
    private int[] arr;
    private int front;
    private int rear;
    private int capacity;

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

    public void enqueue(int data) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full.");
        }
        rear = (rear + 1) % capacity;
        arr[rear] = data;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty.");
        }
        int data = arr[front];
        front = (front + 1) % capacity;
        return data;
    }

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

    public boolean isFull() {
        return ((front == 0 && rear == capacity - 1) || (front == rear + 1));
    }

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

    public int size() {
        if (isEmpty()) {
            return 0;
        } else if (front <= rear) {
            return rear - front + 1;
        } else {
            return capacity - front + rear + 1;
        }
    }
}

2. 使用链表实现队列

链表也可以用于实现队列，与使用数组相比，链表的插入和删除操作更加高效。

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

    private class Node {
        int data;
        Node next;

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

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

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

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

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

结论

栈和队列是常用的数据结构，在Java编程中可以使用数组或链表来实现它们。数组实现简单直接，适用于规模固定的情况。链表实现更加灵活高效，适用于规模不固定的情况。在选择实现方式时，可以根据具体的需求和场景来决定。希望本文对你理解和使用Java中的栈和队列有所帮助，并能在实际的编程中加以应用。