从栈到队列:探索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 函数式编程范式与面向对象编程范式的比较
Spring Boot项目启动Jar包冲突,如何快速排查并解决?
子类如何通过父类方法修改父类私有属性?
在Java编程中,如果你想在检测到学生ID重复时停止后续代码的执行,可以使用return语句或者抛出异常来实现。以下是两种常见的方法:方法一:使用return语句这种方法适用于在方法内部检测到重复ID时,直接返回,停止后续代码的执行。public void processStudent(Student student) { if (isStudentIdDuplicate(student.getId())) { System.out.println("学生ID已存在,停止处理。")
在 Android Fragment 中,如何最佳地调用 Activity 方法?
HttpServletResponseWrapper加密接口返回值时如何避免中文乱码?