[자료구조] Stack, Queue

Stack이란

Stack은 쌓여있는 접시 더미와 같이 작동합니다.
새로운 접시가 쌓일 때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가지고 가는 것과 같습니다.

• LIFO: last in, first out (가장 늦게 들어온 자료가 가장 먼저 나가는 구조)
  

장점
1. 구현이 쉽다
2. 데이터의 삽입과 삭제가 빠르다

단점
1. 데이터의 최대 갯수를 미리 정해야 한다
2. 탐색을 하려면 원소를 하나하나 꺼내서 옮겨가면서 해야함.
3. 맨 위의 원소만 접근 가능하다.

언제 사용하는가
1. 재귀 사용시 유용함
2. 역추적시 유용함

삽입(push)
현재 형태를 (가)라고 가정하면 push을 통해 (나)라는 결과를 보여준다 이때 S 자료 위에 X라는 새로운 자료가 올라가는 걸 볼 수 있다 top S => top X

삭제(pop)
현재 형태를 (나)라고 가정하면 pop을 통해 (다)라는 결과를 보여준다 이때 위에 있던 X라는 자료가 제거되서 최상단에는 S라는 자료가 있는 걸 볼 수 있다 top X => top S

읽기(peek)
마지막 위치에 해당하는 자료를 읽습니다. 이 때, top의 변화는 없습니다.

코드로 구현 해보자

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

  size() { // 현재 크기
    return this.top
  }
  
  push(element) {
    // element를 storage에 넣는다
    // key는 인덱스이고 value는 element이다
    // top의 값을 1씩 더 해준다
    this.storage[this.top + 1] = element
    this.top = this.top + 1 
  }
  
  pop() {
    //top 값의 key를 가진 value를 제거하고 반환한다
    if(this.top !== 0) { 
      let deleted = this.storage[this.top] 
      delete this.storage[this.top] 
      this.top = this.top - 1
      return deleted
    }
  }
}
 let stack = new Stack()

Queue 란

Queue는 놀이공원에서 서는 줄과 같이 작동합니다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같습니다.

• FIFO: first in, first out 가장 먼저 들어 온 자료가 가장 먼저 나가는 구조

  

장점
1. 데이터의 삽입/삭제가 빠르다.
2. 크기가 가변적이다
3. 앞 뒤 데이터 삽입/삭제 가능함
4. 새로운 원소 삽입 시에 메모리에 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당 함

단점
1. queue의 중간에 위치한 데이터로의 접근이 어렵다
2. 한개를 제거 했다고 하면 한칸 당겨야함

언제 사용하는가
1. 데이터를 입력된 순서대로 처리할때

삽입(enqueue)
현재 형태를 A라고 가정시 enqueue 과정을 통해 B라는 결과를 보여준다 rear부분에 X라는 자료가 추가된 걸 볼 수 있다 rear E => rear X

삭제(dequeue)
현재 형태를 B라고 가정시 dequeue 과정을 통해 C라는 결과를 보여준다 front부분에서 Q라는 자료가 삭제 된걸 볼 수 있다 front Q => front U

코드로 구현 해보자

class Queue {
  constructor() {
    this.storage = {}
    this.front = 0
    this.rear = 0
  }
  
  size() {
   return this.rear - this.front
  }
  
  enqueue(element) {
   this.storage[this.rear + 1] = element
   this.rear = this.rear + 1
  }
  
  dequeue() {
    if(this.size() !== 0){
      delete this.storage[this.front]
      this.front = this.front + 1
      return this.storage[this.front]
    } 
  }
}

let queue = new Queue()