0420_ Stack, Queue

Stack

 

(1) 구조: 

(2) 특징: 

- 정해진 방향으로만 쌓을 수 있다.

- 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 

- 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.

- 삽입: push, 삭제: pop

 

(3) 사용 예시

- 웹 브라우저 뒤로가기

- 역순 문자열 만들기

 

(4) Stack overflow

지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사요하게 되어 에러가 발생하는 상황

 

함수를 호출시 파라미터, 리턴값, 복귀주소 등을 스택에 저장

재귀함수*를 사용하면 호출한 함수가 종료되지 않은 채 새로운 함수를 호출하므로 스택에 메모리가 계속 저장

가용범위를 초과하면 스택오버플로우 발생!

 

* 해결 방안

함수 호출 시 이전의 호출한 스택 메모리는 종료한다. (꼬리 재귀)

-> 다음 함수 호출시 현재 함수의 결과 값을 전달

-> 함수 종료시 이전 함수의 전달값이 필요없으므로 이전함수의 데이터를 따로 저장할 필요 없음

 

* 재귀함수: 자기 자신을 재참조하는 함수 (파보나치)

 

Queue

(1) 자바스크립트로 구현할 때 문제점

자바스크립트엔 큐의 기능을 사용할 수 있는 내장 메서드가 없다. FIFO 방식을 준수하는 자료구조를 만들어내려면 shift()ㅏ메서드를 떠올려 구현을 하게 되는데 문제는 원소를 앞에서 하나씩 제거할 때, 나머지 배열 원소에 대한 재정렬이 이루어지기 때문에 시간복잡도가 올라간다. 

 

shift() 메서드의 내부 로직은 다음과 같다.

• 배열의 첫 번째 원소 arr[0]에 접근하여 해당 값을 반환하고 배열에서 제거
• 기존 배열에서 첫 번째 원소 arr[0]의 값은 사라졌지만 공간은 차지하고 있음
• shift() 메서드는 계속해서 arr[0]에 접근할 예정
• 따라서 나머지 배열의 원소들을 앞으로 한 칸씩 당겨주는 과정 필요

(2) 해결 방안

자바스크립트에서 객체는 key-value의 구조로 사용 가능하므로 O(1) 시간으로 접근할 수 있다. 

front는 항상 큐에서 가장 처음의 원소를 가리키고, rear는 항상 마지막 원소를 가리킨다.

class Queue {
  consturctor() { ... }constructor() {
    this.storage = {};	// 값을 저장할 객체
    this.front = 0;	// 첫 원소를 가리킬 포인터
    this.rear = 0;	// 마지막 원소를 가리킬 포인터
  }  
  
  // 크기 구하기
  size() {
    // rear가 가리키는 값이 없을 때가 아무 데이터가 없는 경우이다
    if (this.storage[rear] === undefined) {
      return 0;
    } else {
      // 그 외의 경우는 앞서 구한 공식으로 크기를 구할 수 있다
      return this.rear - this.front + 1;
    }
    
  // 데이터 더하기
  add(value) {
    // 큐에 데이터가 아무것도 없는 경우
    if (this.size() === 0) {
      // 0번 위치에 값을 넣고 포인터는 건드리지 않는다
      // 이때 ['0']으로 키를 설정한 이유는
      // 자바스크립트 객체 Object는 키 값으로 오직
      // 문자열과 Symbol만 허용하기 때문
      this.storage['0'] = value;
    } else {
      // 그 외의 경우에는 간단하게
      // rear 위치를 1만큼 늘리고 해당 위치에 값 삽입
      this.rear += 1;
      this.storage[this.rear] = value;
    }
    
  // 값 빼내기
  popleft() {
    let temp;	// 첫 원소 값을 임시로 담을 변수
    // 두 포인터의 값이 같은 경우 (데이터가 1개 남은 경우)
    // 물론 초기 상태에서 아무런 데이터가 없는 상황일 수도 있으나
    // 이때 front의 값을 가져오고 제거하는 과정에서
    // 자바스크립트 특성 상 에러가 발생하지 않고
    // 두 포인터의 값을 계속 0으로 유지시켜 주기 때문에
    // 별도로 이 부분에 대한 처리를 해줄 필요는 없지만
    // 좀 더 호환성 높은 코드를 위해서는 사실 하는 편을 추천
    if (this.front === this.rear) {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      // 이 부분이 없었다면 이 시점에서 front는
      // rear의 값 보다 1보다 더 큰 역설에 빠지게 되므로
      // 데이터가 없는 경우를 다시 0으로 초기화
      this.front = 0;
      this.rear = 0;
    } else {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
    }
    return temp;
  }
  }