Chapter [ Stack / Queue ]

이재협·2021년 10월 8일
0

자료구조란?

여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것으로 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없다.

[ Stack ]

1. Stack이란 데이터(data)를 순서대로 쌓는 자료구조를 말한다.

2. 자료구조 Stack의 특징

  • 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.

  • LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다.

3. Stack의 실사용 예제

  • 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용

    1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관합니다.

    2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옵니다.

    3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져옵니다.

    4. 마지막으로 현재 페이지를 Prev Stack에 보관합니다.

4. class 키워드로 Stack 구현

class Stack {
  //stack constructor를 생성합니다.
  constructor() {
    this.storage = {};
    this.top = 0;
  }
  // stack의 사이즈를 구합니다.
  // this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로 size를 구할 수 있습니다.
  // this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타냅니다. 0부터 1씩 증감하며 표현하기 때문에 전체 요소의 개수를 나타낼 수 있습니다
  size() {
    return this.top;
  }
  //stack에 element를 추가합니다.
  //새롭게 추가될 요소의 인덱스를 나타내는 this.top을 키로, 요소를 값으로 하여 storage에 할당합니다.this.top은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
  // stack에서 element를 제거한 뒤 해당 element를 반환합니다.
  // 만약 size가 0이라면 아무 일도 일어나지 않습니다.
  // top-1로 최상단을 설정한 후 변수에 저장하고, 스택에서 삭제합니다.
  // 하나를 제거했으니 top도 감소합니다.
  pop() {
    if (this.top <= 0) {
      return;
    }
    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    return result;
  }
}

5. 배열로 자료구조 Stack 구현하기

// const array = new Array() 미리 정의된 Array 객체를 사용합니다.
const stack = []; 

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.push(4); // [1, 2, 3, 4]
stack.push(5); // [1, 2, 3, 4, 5]

console.log(stack); // [1, 2, 3, 4, 5]

stack.pop(); // [1, 2, 3, 4]
stack.pop(); // [1, 2, 3]

console.log(stack); // [1, 2, 3]

[ Queue ]

1. 큐(Queue)줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있다.

2. 자료구조 Queue 특징

  • 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징

3. Queue의 실사용 예제

  • 컴퓨터 장치들 사이에서 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이시간 차이 를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용 한다. 이것을 통틀어 버퍼(buffer)

4. class 키워드로 Queue 구현

class Queue {
  //가장 앞에 있는 요소를 front,
  //가장 뒤에 있는 요소를 rear 라고 했을 때
  //queue constructor 생성
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  // queue의 사이즈를 구합니다.
  // queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있습니다.
  size() {
    return this.rear - this.front;
  }
  // queue에 element를 추가합니다.
  // 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당합니다. this.rear은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  // queue에서 element를 제거 한 뒤 해당 element를 반환합니다.
  // 만약 size가 0이라면 아무 일도 일어나지 않습니다.
  // this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제합니다.
  dequeue() {
    if (this.size() === 0) {
      return;
    }
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
  }
}

5. 배열로 자료구조 Queue 구현하기

// const array = new Array() 미리 정의된 Array 객체를 사용합니다.
const queue = []; 

queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]
queue.push(4); // [1, 2, 3, 4]
queue.push(5); // [1, 2, 3, 4, 5]

console.log(queue); // [1, 2, 3, 4, 5]

queue.shift(); // [2, 3, 4, 5]
queue.shift(); // [3, 4, 5]

console.log(queue); // [3, 4, 5]
profile
코딩만을 잘하는 개발자가 아닌 문제를 해결하는 개발자가 되어보자

0개의 댓글