Java의 일반적인 선형 데이터 구조 및 구현: 스택에서 큐까지 탐색

스택에서 큐까지: Java의 일반적인 선형 데이터 구조와 구현 방법을 살펴보세요.

소개:
컴퓨터 과학에서 데이터 구조는 데이터를 구성하고 저장하는 방법입니다. 선형 데이터 구조는 그 중 하나이며 데이터 요소 간의 명확한 문맥 관계가 특징입니다. Java 개발에서 일반적인 선형 데이터 구조에는 매우 자주 사용되는 스택과 큐가 포함됩니다. 이 기사에서는 스택과 큐가 Java에서 구현되는 방법을 심층적으로 살펴보고 특정 코드 예제를 제공합니다.

1. 스택의 개념 및 구현:
스택은 LIFO(후입선출) 데이터 구조입니다. 그 특징은 삽입과 삭제 작업이 스택 상단에서만 수행될 수 있다는 것입니다. Java에는 배열 기반 구현과 연결 목록 기반 구현이라는 두 가지 일반적인 스택 구현이 있습니다.

1. Array 기반 스택 구현:
   Array는 지속적으로 저장되는 데이터 구조이므로 스택 구현에 매우 적합합니다. 다음은 배열 기반 스택 클래스의 샘플 코드입니다.

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

2. 큐의 개념 및 구현:
큐는 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에서 일반적으로 사용되는 선형 데이터 구조이며 이를 구현하는 방법에는 여러 가지가 있습니다. 이 문서에서는 배열 기반 및 연결 목록 기반 스택 및 큐 구현을 소개하고 특정 코드 예제를 제공합니다. 개발자는 프로그램의 효율성과 유지 관리성을 향상시키기 위해 실제 요구 사항에 따라 적절한 구현 방법을 선택할 수 있습니다.

위 내용은 Java의 일반적인 선형 데이터 구조 및 구현: 스택에서 큐까지 탐색의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!