[TIL] 자료구조 : Stack, Queue

자료구조

여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것
필요에 따라 데이터의 특징을 잘 파악(분석)하여 정리하고 활용하기 위해 선배 개발자들이 연구해둔 방법이 자료구조라고 할 수 있겠다!

자료구조의 종류는 당장 구글에 자료구조 분류라고 쳐보면 알 수 있듯이 굉장히 많은데,
이번 유닛에서는 그 중에서 가장 많이 사용되고, 알고리즘 테스트에 자주 등장하는 Stack, Queue, Tree, Graph를 학습한다고 한다.

오늘 배운 건 Stack과 Queue 두가지이다.

Stack 🥞

데이터를 순서대로 쌓는 자료구조

특징

• 입력과 출력이 하나의 방향으로 이루어지고 (제한적 접근), 후입선출 방식.
• 스택에 넣는 건 push, 데이터를 꺼내는 건 pop이라고 하는데 데이터를 넣거나 뺄 때는 한 개씩만 가능.
• 스택에 저장되는 데이터는 유한하고 정적이어야 하는데, 그래야 컴파일 시간이 결정되기 때문.
• 스택의 크기는 힙(Heap)에 비해 제한되어 있어서 Stack overflow 같은 에러가 자주 발생.
• 대부분 언어는 스택에 저장할 수 있는 값의 크기가 제한되어 있음.

예시 및 과제

대표적으로 앞으로 가기, 뒤로 가기 기능을 구현할 때 stack을 사용할 수 있다.

//앞으로 가기, 뒤로 가기 구현 

function browserStack(actions, start) {
  //출력되는 값은 배열 : [prev 스택, 현재 위치, next 스택]
  //브라우저에서 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우(클릭이 되지 않을 경우)에는 스택에 push 하지 않는다. 
  //**비활성화 되었을 때 === 해당 버튼의 stack이 비었을때**
  //prev에 아무것도 없거나 next에 아무것도 없을 때 
  const prev = [];
  let now = start;
  const next= [];

  //예외 조건 제외(start의 인자로 string 자료형이 아닌 다른 자료형이 들어온다면 false를 리턴) 
  if(typeof start !== 'string'){
    return false;
  }
  
  for(let i=0;i<actions.length;i++){
    if(actions[i] === 1 && next.length !== 0 ){
  //앞으로 가기 버튼을 누를 경우 (+1) && next가 비어있지 않은 경우 
  //원래 있던 페이지를 prev 스택에 넣는다
  //next 스택의 top에 있는 페이지로 이동한다 
  //next 스택의 값을 pop한다 (현재 페이지가 되었으니 prev 스택에서 제거하는 것)
  prev.push(now);
  now = next[next.length-1];
  next.pop();

    }else if(actions[i] === -1 && prev.length !== 0){
  //뒤로 가기 버튼을 누를 경우 (-1) && prev가 빈 배열이 아닐 경우 
  //원래 있던 페이지를 next 스택에 넣는다
  //prev 스택의 top(포인터)에 있는 페이지로 현재 페이지를 이동한다 
  //prev스택의 값을 pop 한다 (현재 페이지가 되었으니까 prev 스택에서 제거하는 것)
    next.push(now);
    now = prev[prev.length-1];
    prev.pop();
    }else if(typeof actions[i] === 'string'){
  //새로운 페이지로 접속할 경우 
  //prev 스택에 원래 있던 페이지를 넣는다 
  //next 스택을 비운다 
    prev.push(now);
    next.splice(0);
    now = actions[i];
    }//마지막 조건이 else가 아니고 else if인 이유는 
    //뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우에는 아무것도 해주지 않기 위해서 
    //else를 하게 되면 actions[i]가 새로운 페이지인 경우와 
   	//뒤로 가기, 앞으로 가기 버튼을 눌렀지만 next나 prev가 비어있는 경우가 합쳐져서 잘못된 결과가 나오기 때문 
  }
 
  return [prev,now,next];
}

Queue 🚗 🚕 🚙

stack과 반대되는 개념.

먼저 들어간 데이터가 먼저 나오는 선입선출 방식으로 Queue에 데이터를 넣는 것을 enqueue, 데이터를 꺼내는 것을 dequeue라고 함.

데이터가 입력된 순서대로 처리할 때 Queue를 사용.

특징

• First In First Out 선입선출
• 데이터를 하나씩 넣고 뺄 수 있음
• 두 개의 입출력 방향을 가진다
• 단점 : 선형 큐의 경우 자료를 꺼내올 때 배열의 가장 앞에 있는 데이터를 꺼내오기 때문에 그 다음 인덱스의 데이터들을 한 칸씩 모두 이동해야 한다. (=> 보완 : 원형 큐)

예시 및 과제

문서 순서대로 인쇄하기 (컴퓨터 출력 버튼 ⇒ Queue에 하나씩 들어옴 ⇒ Queue에 들어온 문서를 순서대로 인쇄)

//인쇄 구현하기 

function queuePrinter(bufferSize, capacities, documents) {

  //아직 채워지지 않은 빈 작업 목록 칸은 0으로 채운다 
  let printerQueue = new Array(bufferSize).fill(0);
  //첫번째 문서를 documents에서 제거하면서 해당 값을 printerQueue의 맨 뒤에 넣는다 
  printerQueue[printerQueue.length-1] = documents.shift();
  //시간은 1초 지남 
  let time = 1
  //sum은 printerQueue의 모든 용량의 합이다 (sum을 통해서 새로운 문서를 queue에 추가할 수 있는지 없는지 판별한다)
  let sum = printerQueue[printerQueue.length-1]

//queue 속의 용량 값이 0이 되면 반복문을 종료하도록 한다 (더 이상 프린트 할 문서가 없을 때)
  while(sum>0){
    //아래의 sum 변경은 queue의 맨 앞에 있던 문서가 프린트되어 진 뒤에 queue에 남은 용량을 계산한다 
    //처음에는 sum - 0이겠지만, 점점 문서가 이동해서 queue의 맨 첫번째 자리에 오고, 프린트가 되면 sum에서 해당 용량이 제거됨
    sum = sum - printerQueue.shift()

    //프린트 된 문서의 용량이 제거되고 난 뒤에 sum과 새롭게 queue에 들어오고 싶어하는 documents[0]의 합이 capacities보다 큰지 확인한다
    //만약 용량제한보다 크면 queue에 추가할 수 없고, 새로운 문서가 들어오지 않은 자리에는 0을 넣어준다. 
    //만약 용량제한보다 작거나 같아서 queue에 추가할 수 있게 되면 documents에서 첫번째 요소를 제거하면서 printerQueue에 넣어준다 
    //두 경우 다 시간을 증가시켜주어야 한다.  
    if(documents.length>0 && sum + documents[0] <= capacities){
      sum = sum + documents[0];
      printerQueue.push(documents.shift());
      time += 1;
    }else{
      printerQueue.push(0);
      time+= 1;
    }
  }
  return time;
  }

과제 : 클래스로 Stack과 Queue 구현

자료구조라는 건 데이터를 다루는 구조 그 자체를 뜻하는 거라 구현하는 방식에는 제약이 없다.

과제에서는 우선 클래스로 stack과 queue를 구현했지만, 배열로도 stack 자료구조를 구현하거나, queue 자료구조를 구현할 수 있음.

//Stack 구현 
class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 포인터 변수를 초기화 
  }

  //스택의 크기를 반환하는 매서드 
  size() {
    return Object.keys(this.storage).length;
  }

	// 데이터를 추가하는 매서드 
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	// 데이터 추출하는 매서드 
  pop() {
    // 빈 스택에 pop 연산을 적용하는 경우 제외하기 
    if (Object.keys(this.storage).length === 0) {
      return;
    }
  
    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    
    return result;
  }
}

//Queue 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return Object.keys(this.storage).length
  }
  
  // 큐에 데이터를 추가 하는 매서드
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  
  // 데이터를 추출하는 매서드 
  dequeue() {
    // 빈 큐에 dequeue 매서드 사용하는 경우 제외하기 
    if (Object.keys(this.storage).length === 0) {
      return;
    }

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

    return result;
  }
}