TIL 30. Stack & Queue

Stack

A LIFO(Last In First Out) data structure
The last element added to the stack will be the first element removed from the stack

実装スタック

1.クラス宣言

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

class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

2.push()を実施する
pseudocode

The function should accept a value

Create a new node with that value

If there are no nodes in the stack, set the first and last property to be the newly created node

If there is at least one node, create a variable that stores the current first property on the stack

Reset the first property on the node to be the previously created variable

Increment the size of the stack by 1

class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  
  push(val){
    let newNode = new Node(val);
    if(!this.first){
      this.first = newNode;
      this.last = newNode;
    } else {
      let temp = this.first;
      this.first = new Node;
      this.first.next = temp;
    }
    return ++this.size;
  }  
}

3.pop()実施
pseudocode

If there are no nodes in the stack, return null

Create a temporary variable to store the first property on the stack

If there is only 1 node, set the first and last property to be null

If there is more than one node, set the first property to be the next property on the current first

Decrement the size by 1

Return the value of the node removed

class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  
  push(val){
    let newNode = new Node(val);
    if(!this.first){
      this.first = newNode;
      this.last = newNode;
    } else {
      let temp = this.first;
      this.first = new Node;
      this.first.next = temp;
    }
    return ++this.size;
  }  
}

Big O of Stack
Insertion - O(1)
Removal - O(1)
Searching - O(N)
Access - O(N)

Queue

A FIFO(First in First Out) data structure

配列内のQueue

// 1. push() & shift()
let Q = [];
Q.push(1); // 1 인덱스 리턴
Q.push(2); // 2 인덱스 리턴
Q.push(3); // 3 인덱스 리턴

Q; // [1,2,3]

Q.shift(); // 1 value 리턴
Q.shift(); // 2 value 리턴
Q.shift(); //3 value 리턴

// 2 unshift() & pop() 
let Q = [];
Q.unshift(1); // 1 배열의 길이 리턴
Q.unshift(2); // 2
Q.unshift(3); // 3

Q.pop(); // 1 value 리턴
Q.pop(); // 2 value 리턴
Q.pop(); // 3 value 리턴

Queueの実装

配列を使用するのは便利ですが、インデックス・プロシージャが追加されたため、より多くのメモリが使用されます.インデックスを作成する必要がない場合は、キュークラスを個別に作成できます.
1.クラス宣言

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

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

2.enqueue()実装=push()

This function accepts some value

Create a new node using that value passed to the function

If there are no nodes in the queue, set this node to be the first and last property of the queue

Increment the size of the queue by 1

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

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
  enqueue(val){
    let newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
   }
 }

3.dequeue()実装=shift()

If there is no first property, just return null

Store the first property in a variable

See if the first is the same as the last(check if there is only 1 node.) If so, set the first and last to be null.

If there is more than 1 node, set the first property to be the next property of first

Decrement the size by 1

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
dequeue(){
    if (!this.first) return null;
    let temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }
}

Big O of Queue
Insertion - O(1)
Removal - O(1)
Searching - O(N)
Access - O(N)