iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
Software Development

資料結構與演算法,使用JavaScript與Python系列 第 8

【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

鏈結串列的介紹可以參考此篇


上一篇
【Day7】[資料結構]-佇列Queue
下一篇
【Day9】[資料結構]-雜湊表Hash Table
系列文
資料結構與演算法,使用JavaScript與Python35

尚未有邦友留言

立即登入留言