Common linear data structures in Java and their implementation: Exploration from stack to queue

From stack to queue: Exploring common linear data structures in Java and how they are implemented

Introduction:
In computer science, data structures are the organization and implementation of A way to store data. One of them is linear data structure, which is characterized by a clear contextual relationship between data elements. In Java development, common linear data structures include stacks and queues, which are used very frequently. This article will explore in depth how stacks and queues are implemented in Java and provide specific code examples.

1. The concept and implementation of stack:
The stack is a Last In First Out (LIFO) data structure. Its characteristic is that insertion and deletion operations can only be performed on the top of the stack. In Java, there are two common implementations of stacks: array-based implementation and linked-list-based implementation.

1. Array-based stack implementation:
   Array is a continuously stored data structure, which is very suitable for implementing stacks. The following is a sample code of an array-based stack class:

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. Linked list-based stack implementation:
   Linked list is a non-continuous storage data structure, which is also suitable for implementation stack. The following is a sample code of a stack class based on a linked list:

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;
        }
    }
}

2. The concept and implementation of queue:
The queue is a first in first out (FIFO) data structure. Its characteristic is that it can only insert elements at the end of the queue and delete elements at the head of the queue. In Java, there are two common implementations of queues: array-based implementation and linked-list-based implementation.

1. Array-based queue implementation:
   Similar to the array-based stack implementation, the following is a sample code for an array-based queue class:

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. Queue implementation based on linked list:
   Similar to the stack implementation based on linked list, the following is a sample code of a queue class based on linked list:

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;
        }
    }
}

Conclusion:
Stack and queue are Java There are many ways to implement linear data structures commonly used in . This article introduces array-based and linked-list-based stack and queue implementations, and provides specific code examples. Developers can choose the appropriate implementation method according to actual needs to improve the efficiency and maintainability of the program.

The above is the detailed content of Common linear data structures in Java and their implementation: Exploration from stack to queue. For more information, please follow other related articles on the PHP Chinese website!