Stack과 Queue

Stack

LIFO(Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조이다

해당 자료구조를 사용해 데이터를 저장하고 검색하는 프로세스가 매우 빠르며, 최상위 블록에서 데이터를 저장하고 검색하면 된다는 장점이 있다

데이터는 하나씩 넣고 뺄 수 있다

 한꺼번에 여러 개를 넣거나 뺄 수 없다

하나의 입출력 방향을 가지고 있다.

Stack 자료구조는 데이터의 입출력 방향이 같다. 만약, 입출력 방향이 여러 개라면 Stack 자료구조라고 볼 수 없다.

스택의 크기는 제한되어있고 데이터는 정적이야 한다

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

 

Stack 구현

 

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화
  }

  size() {
    return this.top 
  }

	// 스택에 데이터를 추가
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 한다
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 한다
    if (this.top===0) {
      return;
    }

    const result = this.storage[this.top-1];//pudh에서 미리 top++ 해주기 때문에
    delete this.storage[this.top-1];
    this.top -= 1;
    
    return result;
  }
}

Queue

FIFO (First In First Out)

먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조를 가지고 있다

데이터는 하나씩 넣고 뺄 수 있다

 한꺼번에 여러 개를 넣거나 뺄 수 없.

두 개의 입출력 방향을 가지고 있다

Queue 자료구조는 데이터의 입력, 출력 방향이 다르다

 

 

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

 

 

Queue 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear-this.front
  }
	

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 한다
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 한다
    if (this.rear===this.front) {
      return;
    }

    const result = this.storage[this.front];

    delete this.storage[this.front];
    this.front += 1;
 

    return result;
  }
}