Data Structure 공부 중 이해한 부분을 정리합니다. 각 자료구조의 구현은 JavaScript를 이용하였습니다.

Stack

마지막에 집어넣은 자료가 먼저 빠져 나오는 LIFO (last in, first out)으로 한쪽 끝에서만 자료를 넣다가 뺄 수 있는 구조입니다.

Stack 구현

구현한 메소드

• push(element) - 요소를 스택의 최상단에 추가합니다.
• pop() - 스택의 최상단 요소를 제거하고 반환합니다.
• size() - 스택의 현재 요소 개수를 반환합니다.

Pesuedo Code

• Stack class는 생성되어있는 상태

• push(element) - this.storage에 this.top을 key, element를 value로 생성. 그리고 this.top++;

• pop() - if(this.top > 0) 경우에만 실행하고 delete를 이용하여 this.storage[this.top - 1]을 지움. 그리고 그 값을 return

• size() - this.top을 return

  array로 구현하지 않고 numeric key를 사용하여 구현하였습니다!

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

  }

  push(element) {
    this.storage[this.top] = element;  
    this.top++;
  }

  pop() {
    if(this.top > 0){
      let popNumber = this.storage[this.top - 1];

      delete this.storage[this.top - 1];
      this.top--;
      return popNumber;

    }
  }
}

콘솔에서 확인 해봤습니다.

let stack = new Stack();
stack.push('a');

stack // Stack {storage: {…}, top: 1} storage: {0: "a"} top: 1__proto__: Object
stack.pop(); // "a"

Queue

먼저 집어 넣은 데이터가 먼저 나오는 FIFO (first in, first out)구조로 저장하는 형식을 말합니다.

Queue 구현

구현한 메소드

• enqueue(element) - 요소를 큐의 뒤에 추가합니다.
• dequeue() - 요소를 큐의 앞에서 제거하고 반환합니다.
• size() - 큐의 현재 요소 개수를 반환합니다.

pesuedo Code

• class Queue는 이미 구현되어 있는 상태입니다.

• enqueue(element) - 뒤에 추가하는 것 이기 때문에 this.storage에 key로 this.rear, value로 element 추가. this.rear++;

• dequeue() - Queue의 사이즈가 0보다 커여야 실행될 수 있게하고, delete를 사용하여 this.storage[this.front]를 삭제. this.front를 1 더하고 지운값을 reture.

• size() - this.rear - this.front을 return.

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++;
  }

  dequeue() {
    if((this.rear - this.front) > 0){
      let dequeueNumber = this.storage[this.front];
      delete this.storage[this.front];
      this.front++;
      return dequeueNumber;
    }
  }
}

콘솔에서 확인 해봤습니다.

let queue = new Queue;
queue.enqueue("a");
queue.enqueue("b");
queue.dequeue(); // "a"
queue.size() // 1
queue // Queue {storage: {…}, front: 1, rear: 2}

Reference

• Queue (abstract data type)