Stack

자료(data)를 쌓는 자료구조

길 목 끝이 막혀있는 골목을 생각해보자.

가장 먼저 들어온 차는 뒤에 차가 나갈 때까지는 꼼짝없이

멈춰있어야한다.

반대로 가장 나중에 들어온 차는 가장 먼저 나갈 수 있습니다.

이러한 stack의 자료구조 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 합니다.

---

스택 구현(2021.04.21일 추가)

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

  size() {
    return this.top;
  }

  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	
  pop() {
    if (this.size()<=0) {//사이즈0이어도 오류없이 리턴!
      return;
    }

    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    //storage의 저장 인덱스는 0부터 시작하지만
 	//top은 바로 1부터 추가되어서 this.top-1을 해줘야 위치를
    //잡아서 값을 빼줄수 있다.
    
    //항상 끝부터 빠져야함 중간값을 뺄 수는 없음.
    this.top= this.top-1;
    
    return result;
  }
}

let stack = new Stack();

스택은 웹 페이지의 앞으로 가기 뒤로가기 버튼을 구현할 수 있습니다.

or(let i=0; i<actions.length; i++){
    //if(prev.length===0 && next.length===0 && actions[i]){
    //  return [];
    //}
    if(actions[i]===-1 && prev.length !==0 ){
      //뒤로 가기 버튼을 누를 경우 원래 있던 페이지를 next 스택에 넣고, prev 스택의 top에 있는 페이지로 이동한 뒤 prev 스택의 값을 pop 합니다.
      next.push(prevPage);
      prevPage=prev.pop();
      //next.push(prev.pop());
      //prev.pop();
    }
    else if(actions[i]===1 && next.length !==0){
      //앞으로 가기 버튼을 누를 경우 원래 있던 페이지를 prev 스택에 넣고/ next 스택의 top에 있는 페이지로 이동한 뒤/ next 스택의 값을 pop 합니다. 
      prev.push(prevPage);
      prevPage=next.pop(); 
    }
    else{
      prev.push(prevPage);
      prevPage=actions[i];
      next=[];
    }
  }

prevPage는 현재 페이지로 실제와는 다르겠지만 이와 같은 형식으로

스택을 두개 이용하여 하나는 이전 페이지를 담는 자료구조로

또 하나는 앞으로 가는 페이지를 담는 자료구조로 사용해 볼 수가 있습니다.

Queue

Stack과 반대되는 개념으로, 먼저 들어간 자료(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 의 특성을 가지고 있는 자료구조

큐의 가장 좋은 예시는 바로 톨게이트인데

톨게이트를 상상해보면 뒤에 차가 아무리 많이 밀려있어도 결국 출력 값은 한 대 씩만 나가게 되어있다.

자료가 입력된 순서대로 처리를 해주는 것이 큐의 특성.

컴퓨터 장치들 사이에서 자료(data)를 주고 받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 Queue가 사용됩니다.

이것을 통틀어 버퍼(buffer)라고 합니다.

우리가 흔히 쓰는 버퍼링(buffering)도 이것의 개념이다.

유튜브 시청을 할 때의 버퍼링도 다운로드 된 자료(data)가 영상을 재생하기에 충분하지 않다면 순서대로 Queue에 모아 두었다가 충분한 양이 되었을 때 비디오를 복원하여 재생해준다.

또한, 보통 프린터는 속도가 느리고, 상대적으로 CPU는 속도가 빨라서 CPU는 빠른 속도로 인쇄 자료(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행합니다. 프린터는 인쇄 작업 Queue에서 자료(data)를 가져가서 일정한 속도로 인쇄하게 된다.

큐 구현(2021.04.21 추가)

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.size()<=0) {
      return;
    }
​
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    if(Object.keys(this.storage).length===0){
      this.front=0
      this.rear=0
    }
    //객체에 아무것도 안담겨있다면 위치값을 초기화(초기상태랑같게)
    return result;
  }
}
let queue = new Queue();