200908 [자료구조 : Stack / Queue]

Stack 

 : 한쪽으로만 자료를 넣고 뺄수 있는 Last in first out(LIFO) 형태의 자료구조

stack의 자료구조

 

Stack 의 method

• pop : Stack의 제일 위(끝)에 자료를 제거한다.
• push(node) : Stack 의 제일 위(끝)에 node(자료)를 추가한다.
• peek : 가장 마지막의 자료를 반환 한다.
• isEmpty : Stack가 비어있을 때 true 를 반환.

Stack 의 사용 예시

• 재귀의 사용 : 재귀 사용 시 임시데이터를 스텍에 넣어주고 backtrack(퇴각검색)을 하면서 스택의 자료를 다시 꺼내온다.
• 웹브라우져의 뒤로가기
• 실행취소 (Undo)
• 역순 문자역 만들기
• 후위표기 계산법

Stack의 구현

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }

  size() {} // this.storage 에 현재 추가된 자료의 개수를 알 수 있다
 
  push(element) {  // this.storage 에 주어진 값을 추가한다.
    this.storage[this.top] = element;
   }

  pop() {
    delete this.storage[this.top-1];
   /* let delValue = this.storage[this.top-1];
    return delValue; */ //delete 한 자료를 반환해준다. peek()가 따로 있다면 따로 구현해도 됨
  }
  
  peek() {
  	if(!this.storage.length){
    	return ; // this.storage 가 비어 있을 때는 반환하지 않는다.
    }
  	let peek = this.storage[this.top-1];
    return peek;  // return this.storage[this.top-1]; 로 간결하게 표현 가능
  }
}

※ 보통의 자료구조는 유한한 크기를 가지고 있지만 Javascript 에서는 크기가 유동적으로 적용한다.

 

 

Queue

 : 입구가 두개인 자료구조로 한쪽으로는 입력만 반대쪽으로는 출력만 가능한 First in first out(FIFO)형 태의 자료구조

Queue 의 자료구조

Queue의 method 

• enqueue : Queue 의 끝에 자료를 추가한다.
• dequeue : Queue 의 처음의 자료를 삭제한다.(삭제한 값을 반환한다.)

Queue 의 사용 예시

• 우선 순위가 같은 대기열의 데이터 처리 : 인쇄 대기열/ 콜센터 고객 대기/ 메시지 처리시스템 등등..

Queue 의 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0; // 가장 앞의 자료
    this.rear = 0; // 가장 뒤의 자료
  }

  size() {} // 현재 Queue 의 개수를 확인 할 수 있다.

  enqueue(element) {
    this.storage[this.rear] = element;  // 데이터의 추가
  }

  dequeue() {
    delete this.storage[this.front];
   
    /* let deValue = this.storage[this.front]
    return deValue; */ // 지우는 자료를 반환 하면 peek의 기능을 할 수 있다.
  }
}