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

2023年 12月 26日 92.4k 0

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

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

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

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

  • 基于数组的栈实现:数组是一种连续存储的数据结构,非常适合用来实现栈。下面是一个基于数组的栈类的示例代码:
  • 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];
    }
    }

    登录后复制

  • 基于链表的栈实现:链表是一种非连续存储的数据结构,同样适合用来实现栈。下面是一个基于链表的栈类的示例代码:
  • 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中,队列的常见实现方式有两种:基于数组的实现和基于链表的实现。

  • 基于数组的队列实现:与基于数组的栈实现类似,下面是一个基于数组的队列类的示例代码:
  • 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];
    }
    }

    登录后复制

  • 基于链表的队列实现:与基于链表的栈实现类似,下面是一个基于链表的队列类的示例代码:
  • 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中常见的线性数据结构及其实现方式:从栈到队列的探索的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!

    相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论