实现队列、栈和链表

问题

用 JavaScript 实现队列、栈和链表这三种基础数据结构。

解答

实现队列 (Queue)

队列是先进先出 (FIFO) 的数据结构。

class Queue {
  constructor() {
    this.items = [];
  }

  // 入队
  enqueue(element) {
    this.items.push(element);
  }

  // 出队
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.shift();
  }

  // 查看队首元素
  front() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[0];
  }

  // 判断是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 获取队列长度
  size() {
    return this.items.length;
  }

  // 清空队列
  clear() {
    this.items = [];
  }
}

// 测试
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // 1
console.log(queue.front());   // 2
console.log(queue.size());    // 2

实现栈 (Stack)

栈是后进先出 (LIFO) 的数据结构。

class Stack {
  constructor() {
    this.items = [];
  }

  // 入栈
  push(element) {
    this.items.push(element);
  }

  // 出栈
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.pop();
  }

  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.items.length - 1];
  }

  // 判断是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 获取栈长度
  size() {
    return this.items.length;
  }

  // 清空栈
  clear() {
    this.items = [];
  }
}

// 测试
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());  // 3
console.log(stack.peek()); // 2
console.log(stack.size()); // 2

实现链表 (Linked List)

链表由节点组成，每个节点包含数据和指向下一个节点的指针。

// 节点类
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// 链表类
class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  // 在末尾添加节点
  append(value) {
    const node = new ListNode(value);

    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }

    this.length++;
  }

  // 在指定位置插入节点
  insert(index, value) {
    if (index < 0 || index > this.length) {
      return false;
    }

    const node = new ListNode(value);

    if (index === 0) {
      node.next = this.head;
      this.head = node;
    } else {
      let current = this.head;
      let prev = null;
      let i = 0;

      while (i < index) {
        prev = current;
        current = current.next;
        i++;
      }

      prev.next = node;
      node.next = current;
    }

    this.length++;
    return true;
  }

  // 删除指定位置的节点
  removeAt(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    let current = this.head;

    if (index === 0) {
      this.head = current.next;
    } else {
      let prev = null;
      let i = 0;

      while (i < index) {
        prev = current;
        current = current.next;
        i++;
      }

      prev.next = current.next;
    }

    this.length--;
    return current.value;
  }

  // 查找元素的索引
  indexOf(value) {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

  // 获取指定位置的元素
  get(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    let current = this.head;
    let i = 0;

    while (i < index) {
      current = current.next;
      i++;
    }

    return current.value;
  }

  // 判断是否为空
  isEmpty() {
    return this.length === 0;
  }

  // 获取链表长度
  size() {
    return this.length;
  }

  // 转换为数组
  toArray() {
    const result = [];
    let current = this.head;

    while (current) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }
}

// 测试
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.insert(1, 1.5);
console.log(list.toArray());   // [1, 1.5, 2, 3]
console.log(list.get(1));      // 1.5
console.log(list.indexOf(2));  // 2
list.removeAt(1);
console.log(list.toArray());   // [1, 2, 3]

关键点

• 队列：先进先出，用数组的 push 和 shift 实现
• 栈：后进先出，用数组的 push 和 pop 实现
• 链表：由节点组成，每个节点有 value 和 next 指针
• 链表操作：插入和删除需要维护前后节点的指针关系
• 边界处理：注意空结构和索引越界的情况