数据结构实现难题：使用Java实现堆栈和队列？-蒲公英云

数据结构实现难题：使用Java实现堆栈和队列？

原创淩亂°似流年 2024-11-22 04:57 88阅读 0赞

在Java中，我们可以使用数组或链表来实现堆栈和队列。这里我将分别解释这两种数据结构的Java实现。

堆栈（Stack）：

数组实现：

class Stack {
  int[] arr;
  int top;
  Stack(int size) {
      arr = new int[size];
      top = -1;
  }
  // 入栈操作
  void push(int item) {
      if (top == arr.length - 1) {
          System.out.println("Stack overflow!");
          return;
      }
      arr[++top] = item;
  }
  // 出栈操作（获取堆栈顶元素）
  int pop() {
      if (top == -1) {
          System.out.println("Stack underflow!");
          return -1;
      }
      int item = arr[top--];
      return item;
  }
  // 检查栈是否为空
  boolean isEmpty() {
      return top == -1;
  }
}

链表实现（链表节点结构为：Node(int data) { this.data = data; }）：

class Stack {
  Node stack;
  Stack() {
      stack = new Node(0); // 创建一个空的堆栈
  }
  // 入栈操作
  void push(int item) {
      stack.next = new Node(item);
      stack = stack.next;
  }
  // 出栈操作（获取堆栈顶元素）
  int pop() {
      if (stack == null || stack.next == null) {
          System.out.println("Stack underflow!");
          return -1;
      }
      int item = stack.next.data;
      stack.next = stack.next.next; // 删除节点
      return item;
  }
  // 检查栈是否为空
  boolean isEmpty() {
      return stack == null || stack.next == null;
  }
}

队列（Queue）：

数组实现：

class Queue {
  int[] arr;
  int front, rear;
  Queue(int size) {
      arr = new int[size];
      front = 0;
      rear = -1; // 初始值设为-1，避免直接使用arr.length - 1
  }
  // 入队操作
  void enqueue(int item) {
      if (rear == arr.length - 1) { // 队列已满
          System.out.println("Queue overflow!");
          return;
      }
      arr[++rear] = item; // 将元素添加到数组的末尾
  }
  // 出队操作（获取队列首元素）
  int dequeue() {
      if (front == rear) { // 队列为空
          System.out.println("Queue underflow!");
          return -1;
      }
      int item = arr[front++];
      if (front >= rear + 1) { // 如果第一个出队的元素后不再有任何元素，则需要重新填充数组
          for (int i = rear + 2; i < arr.length; i++) {
              arr[i] = 0;
          }
          front = 0;
          rear = -1; // 初始值设为-1，避免直接使用arr.length - 1
      }
      return item;
  }
  // 检查队列是否为空
  boolean isEmpty() {
      return front == rear;
  }
  // 获取队列的长度
  int size() {
      return rear - front + 1;
  }
}

链表实现（链表节点结构为：Node(int data) { this.data = data; }）：

class Queue {
  Node queue;
  Queue() {
      queue = new Node(0); // 创建一个空的队列
  }
  // 入队操作
  void enqueue(int item) {
      queue.next = new Node(item);
      queue = queue.next;
  }
  // 出队操作（获取队列首元素）
  int dequeue() {
      if (queue == null || queue.next == null) { // 队列为空
          System.out.println("Queue underflow!");
          return -1;
      }
      int item = queue.next.data;
      queue.next = queue.next.next; // 删除节点
      queue = queue.next; // 更新队列头部
      return item;
  }
  // 检查队列是否为空
  boolean isEmpty() {
      return queue == null || queue.next == null;
  }
  // 获取队列的长度
  int size() {
      Node temp = queue;
      int count = 1; // 起始计数为1，因为数组起始位置是0
      while (temp != null) { // 遍历链表
          temp = temp.next;
          if (count % 2 == 1) { // 如果当前节点是奇数位（从0开始的奇数）
              count++; // 计数加一
          }
      }
      return count; // 返回队列长度
  }
}