[Data-Structure] Stack과 Queue

오늘은 Stack과 Queue에 대해서 공부했다. 

스택(Stack)이란 LIFO(Last In First Out) 후입 선출 구조로 자료의 한쪽 끝에서만 데이터의 입출력이 일어나는데 흔히들 말하는 '접시 쌓기'처럼 맨 마지막에 들어온 데이터가 가장 먼저 밖으로 나오는 구조이다.

스택에 대해서 알아보기 위해 JS로 간단하게 구현해보았다. 

Stack이라는 클래스를 선언해준다음에 생성자 함수로 데이터를 넣어줄 부분을 초기화 해준 뒤, 메소드들을 정의했다. 

정의된 메소드들은 다음과 같다. 

• size() : 현재 스택에 들어온 요소들의 개수를 반환한다.
• push() : 스택에 데이터를 삽입한다.
• pop() : 현재 스택에서 가장 위에 있는 데이터를 반환 및 삭제한다.

class Stack {
    constructor() {
      this.storage = {}; // 데이터가 저장될 객체
      this.top = 0; // 가장 위에 있는 데이터의 값
      this.index = 0; // 현재 인덱스
    }
  
    // 스택의 현재 요소 개수를 반환
    size() {
      if(this.index === 0){
        return 0;
      }
      return this.index;
    }
  
    // 요소를 스택의 최상단에 추가
    push(element) {
      this.storage[this.index] = element;
      this.index += 1;
      this.top = element;
    }
  
    // 스택의 최상단에서 요소를 제거하고 반환
    pop() {
      if(this.index === 0){ // index가 -가 되지않도록 0일때 더이상 pop을 시키지 않는다.
        return
      }
      delete this.storage[this.index]; // 맨 위 요소 제거  
      this.index = this.index - 1; // 인덱스 감소
      this.top = this.storage[this.index]; // top이 가리키는 값 변경
      return this.top;
    }
  }
  

스택을 간단하게 실행해보면

let a = new Stack(); // a라는 스택 생성

a.push("b") // a라는 스택에 b라는 원소를 삽입
a.push("c") 
a.size() // 2 

a.pop() // "c" 반환
a.size() // 1

a.pop() // "b" 반환
a.size() // 0

 

이렇게 데이터를 넣으면 가장 나중에 들어온 데이터가 먼저 나오는 것을 볼 수 있다. 

다음은 큐(Queue)에 대해서 알아보겠다.

큐(Queue)란 FIFO(First In First Out) 선입 선출 구조로 자료의 한쪽 끝에서는 데이터의 입력이 또 다른 한쪽 끝에서는 출력이 일어나며 '선착순 줄'처럼 처럼 맨 처음에 들어온 데이터가 가장 먼저 밖으로 나오는 구조이다.

이때, 삽입이 일어나는 쪽이 rear이고 출력이 일어나는 쪽이 front라고 부른다.

큐 역시 공부를 위해 JS로 간단하게 구현해보았다.

Queue이라는 클래스를 선언해준다음에 생성자 함수로 데이터를 넣어줄 부분을 초기화 해준 뒤, 메소드들을 정의했다. 

정의된 메소드들은 다음과 같다. 

• size() : 현재 큐에 들어온 요소들의 개수를 반환한다.
• enqueue() : 큐(rear)에 데이터를 삽입한다. 
• dequeue() : 현재 큐에서 가장 앞(front)에 있는 데이터를 반환 및 삭제한다.

class Queue {
    constructor() {
      this.storage = {}; // 데이터가 저장될 queue
      this.front = 0; // 가장 앞의 데이터
      this.rear = 0; // 가장 뒤의 데이터
      this.index = 0; // 현재 인덱스
    }
  
    // 큐의 현재 요소 개수를 반환
    size() {
      if(this.index === 0){
        return 0;
      }
      return this.index;
    }
  
    // 요소를 큐의 뒤에 추가
    enqueue(element) {
      this.storage[this.index] = element;
      this.index += 1;
      this.front = this.storage['0']; // 줄 맨앞에 있는 요소
      this.rear = element; // 맨 마지막에 들어온 요소
    }
  
    // 요소를 큐의 앞에서 제거하고 반환
    dequeue() {
      if(this.index === 0){
        return
      }
      let result = this.front; // 맨 앞 요소 저장
      delete this.storage['0']; // 맨 앞 요소 제거  
      this.index = this.index - 1; // 인덱스 감소 (전체 요소 개수)
      for(let i = 0; i < Object.keys(this.storage).length; i++){
        this.storage[i] = this.storage[i+1]; // i 번째에 i + 1번째 값 넣기 -> 인덱스를 한 칸씩 앞으로 당겨주기
      }
      this.front = this.storage['0']; // front가 가리키는 값 변경 -> 맨 앞에 요소로 변경
      return result;
    }
  }
  

큐를 간단하게 실행해보면

let a = new Queue() // a라는 큐 생성

a.enqueue("b") // a라는 큐에 b라는 원소 삽입
a.enqueue("c")
a.size() // 2

a.dequeue() // "b" 반환
a.size() // 1

a.dequeue() // "c" 반환
a.size() // 0

 

스택을 이해하면 재귀함수의 구조도 이해할 수 있다. 

재귀 함수는 재귀 구조 중 가장 마지막에 호출된 재귀 함수 먼저 리턴이 일어나고 그다음 리턴이 일어나고... 가장 처음에 호출된 함수에서 리턴이 일어난다.

또한 큐를 이해하면 선입선출이 일어나는 구조들(데이터가 입력된 시간순서대로 처리해야 하는 구조들)을 이해할 수 있다. 

프린터기의 인쇄 대기열은 먼저 인쇄가 요청된 문서들 먼저 인쇄가 진행된다. 이것 역시 큐의 구조이다.
또한 가게나 편의점에서 물건을 선입선출로 판매하는 것을 연상해 볼 수 있다.

이렇듯 스택과 큐를 이해하면 다양한 구조들을 이해할 수 있게된다.