Stack & Queue 堆疊與佇列-day 28

2024 iThome 鐵人賽

DAY 28

佛心分享-IT 人自學之術

演算法與資料結構入門：30天基礎學習之旅系列第 28 篇

16th鐵人賽

dc88

2024-10-12 00:56:19

77 瀏覽

分享至

Stack 堆疊

Stack is a linear data structure that follows the "LIFO"(last in first out) principle.
Elements can only be added to the top and removed from the top.
It can be implemented by arrays or linked lists.
The elements in a stack do not have index property because you can only interact with the top element.

圖片來源

Two main operations of Stack

push
Adds an element to the collection.
pop
Removed the most recently added elements.

可以將 stack 想像成一個開口向上的容器(或盤子堆)，只能從單方向放置元素
先放入的元素會堆積在底部，要 access 的話要先把後放入的元素先取出來

堆疊的主要操作方法有兩種，push & pop
作用分別為將元素添加入堆疊與將最近添加的元素移出堆疊

Implementation Stack in js

可以用 js array 跟 linked list 來寫
這裡用 linked list 下去修改
完整程式碼在這裡

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  push(value) {
    let newNode = new Node(value);
    if (this.length === 0) {
      this.head = newNode;
    } else {
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
    }
    this.length++;
  }

  pop() {
    if (this.length === 0) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let currentNode = this.head;
      for (let i = 1; i < this.length - 1; i++) {
        currentNode = currentNode.next;
      }
      let temp = currentNode.next;
      currentNode.next = null;
      this.length--;
      return temp;
    }
  }
}

let intStack = new Stack();

intStack.push(1);
intStack.push(3);
intStack.push(5);

console.log(intStack); // // length=3 [1,3,5]

intStack.pop();

console.log(intStack); // length=2 [1,3]

Queue 佇列

Queue is a linear data structure that follow the "FIFO"(first in, first out) principle.
Elements are added to the back(enqueue) and removed from the front(dequeue).
It can also be implemented using arrays or linked lists.
Like stacks, the elements in a queue don't have an index property, and you can only interact with the front and back of the queue.

圖片來源

Queue 依循 先進先出 的原則，如同排隊
先添加的元素會隨著順序從表頭(front)移出，且只能從隊尾(tail/rear)添加新元素

Two main operations of Queue

Enqueue 入隊
push element from back/tail of queue
從佇列(queue)添加資料，每執行一次，就從後端加入一個資料
Dequeue 出隊
remove element from front of queue
從佇列(queue)取出資料，每執行一次，就從前端取出一個資料

Implementation Queue in js

可以用 js array 跟 linked list 來寫
這裡用 linked list 下去修改
完整程式碼在這裡

class Node{
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Queue{
    constructor(){
        this.head= null;
        this.length=0;
    }
    // remove elements from head position
    dequeue(){
        
    }
    // add elements from the rear position
    enqueue(value){
        if(!this.head){
            this.head = new Node(value);
        }else{
            let currentNode = this.head;
          let newNode = new Node(value);
            while(currentNode.next !== null){
                currentNode = currentNode.next;
            }
            currentNode.next = new Node(value);
        }
        this.length++;
    }
}


let groceryQueue = new Queue();
groceryQueue.enqueue("sushi");
groceryQueue.enqueue("tuna");

console.log(groceryQueue);

Circular quque 環形佇列

與 queue 相同, 但首尾相交

Deque

A hybrid type of Stack and Queue, which combines the features of stack and queue.
Deque allows us to add and remove elements from both ends.
Stack 跟 Queue 的混合體,可以從 front 處跟 tail 處添加跟移除元素

有興趣的話不妨試著用 js 寫看看~