【Day8】[资料结构]-伫列Queue-实作

伫列(Queue)建立的方法

• enqueue: 尾端新增元素
• dequeue: 从前端移除元素
• peek: 查看最前端元素
• size: 此伫列的元素量

伫列的介绍可以参考此篇。

JavaScript(使用阵列)

//Queue

class Queue {
  constructor(){
    this.list = []
  }
  // 尾端新增元素
  enqueue(data){
    this.list.push(data)
  }
  // 从前端移除元素
  dequeue(){
    this.list.shift();
  }
  // 查看最前端元素
  peek(){
    return this.list[0]
  }
  // 此伫列的元素量
  size(){
    return this.list.length;
  }
}

let queue = new Queue()
queue.enqueue(20)
queue.enqueue(30)
queue.enqueue(40)
console.log(queue.size())//3
console.log(queue.peek())//20
queue.dequeue()
console.log(queue.peek())//30

阵列的介绍可以参考此篇。

JavaScript(使用链结串列)

//Queue

class QueueNode {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedQueue {
  constructor() {
    this.front = null
    this.rear = null
    this.length = 0
  }

  // 从尾端新增元素
  enqueue(data) {
    let temp = new QueueNode(data);
    if (this.rear == null) {
      this.front = temp;
      this.rear = temp;
    } else {
      this.rear.next = temp;
      this.rear = temp;
    }
    this.length += 1
  }

  // 从前端移除元素
  dequeue() {
    if (!this.front) return null
    if (this.front === this.rear) {
      this.rear = null
    }
    this.front = this.front.next
    this.length -= 1
  }

  // 查看最前端元素
  peek() {
    return this.front.data
  }

  // 此伫列的元素量
  size() {
    return this.length
  }

}

let queue = new LinkedQueue()
queue.enqueue('20')
queue.enqueue('30')
queue.enqueue('40')
console.log(queue.peek()) //"20"
console.log(queue.size()) //3
queue.dequeue()
console.log(queue.peek()) //"30"
console.log(queue.size()) //2
queue.dequeue()
console.log(queue.peek()) //"40"
console.log(queue.size()) //1
queue.dequeue()
console.log(queue.peek()) //null

Python(使用链结串列)

#Queue
class QueueNode():
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


class LinkedQueue():
    def __init__(self, front=None, rear=None):
        self.front = front
        self.rear = rear
    
    def enqueue(self, data):
        if self.front is None:
            self.front = QueueNode(data)
            self.rear = self.front
        else:
            self.rear.next = QueueNode(data)
            self.rear = self.rear.next

    def dequeue(self):
        if self.rear is None:
            return None
        if self.front == self.rear:
            self.rear = None
        self.front = self.front.next

    def peek(self):
        if self.front is None:
            return None
        return self.front.data

    def size(self):
        count = 0
        current = self.front
        while current:
            count += 1
            current = current.next
        return count


queue = LinkedQueue()
queue.enqueue('20')
queue.enqueue('30')
queue.enqueue('40')
print(queue.peek())#20
print(queue.size())#3
queue.dequeue()
print(queue.peek())#30
print(queue.size())#2
queue.dequeue()
print(queue.peek())#40
print(queue.size())#1
queue.dequeue()
print(queue.peek())#None
print(queue.size())#0

链结串列的介绍可以参考此篇。