img source

Stack

stack 말 그대로 쌓는다는 뜻의 자료구조 형태이다.
data를 저장 공간에 쌓아올리는데, 자료가 들어가는 곳과 나가는 곳이 같다. 그렇기 때문에 stack 에서 가장 나중에 들어간 data 부터 차례대로 빼야한다.

배열 메소드의 가장 뒤에있는 요소부터 제거하는 pop, 가장 뒤에 요소를 추가하는 push 를 이용하여 stack 자료구조를 구현해 볼 수 있다.

실사용 예시

웹페이지의 뒤로 가기, 앞으로 가기 기능을 구현할 때 stack 자료구조가 활용된다.

JS 코드구현

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

	// 스택에 데이터를 추가
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	// 가장 나중에 추가된 데이터 먼저 추출
  pop() {
    // 빈 스택에 pop 연산을 적용시 에러 X
    if (this.size()<= 0) {
      return;
    }

    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    
    return result;
  }
}

// Instance 생성
const stack = new Stack();

stack.size(); // 0
for(let i = 1; i < 10; i++) {
  	stack.push(i);
}
stack.pop(); // 9
stack.pop(); // 8
stack.size(); // 7
stack.push(8);
stack.size(); // 8

---

Queue

줄을 설 때, line이랑 같은 뜻으로 queue를 많이 쓰는데, 자료구조에서도 queue 가 있다!

주문을 먼저한 사람이 먼저 받는 것 처럼 queue 자료 구조는 선입선출을 기반으로 이루어진다. 위의 이미지와 같이 자료가 들어오는 곳과 나가는 곳이 다르다.

자료가 입력된 순서대로 처리해야할 경우에 사용된다.

실사용 예시

프린터에서 인쇄할 때, 먼저 입력받은 문서 먼저 queue에 들어가고, 순서대로 문서를 출력한다.

JS 코드구현

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 연산을 적용해도 에러 X
    if (this.size() === 0) {
      return;
    }

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

    return result;
  }
}

// Instance 생성
const queue = new Queue();

queue.size(); // 0
for(let i = 1; i < 10; i++) {
  	queue.enqueue(i);
}
queue.dequeue(); // 1
queue.dequeue(); // 2
queue.size(); // 7
queue.enqueue(10);
queue.size(); // 8
queue.dequeue(); // 3
queue.dequeue(); // 4
queue.size(); // 6