스택+큐

스택

데이터의 모음 -> 압축적인 데이터 구조 LIFO(Last In First Out) 후입 선출

- Undo/Redo 기능

-인터넷 방문 기록

Big O 

*Insertion - O(1)

*Removal - O(1)

Searching - O(N)

Access - O(N)

 

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

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

큐

FIFO(First In First Out) 선입 선출 (추가 - enqueue 제거 - dequeue) 

- 접속 대기

- 줄

- 업로드

- 프린트 대기열

- 업무 처리할때 유리

Big O 

*Insertion - O(1)

*Removal - O(1)

Searching - O(N)

Access - O(N)

 

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

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

    dequeue(){
        if(!this.first) return null;

        var temp = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}