스택 & 큐

스택

• 가장 나중에 집어넣은 데이터를 가장 먼저 추출하는 LIFO(Last In First Out)
• 배열에서 push, pop이 해당한다. 
• 가장 마지막에 있는 데이터를 확인할 수 있다.(보통 stackTop이라고 부른다)

class Node {
   constructor(data, next) {
      this.data = data;
      this.next = null
   }
}

class Stack {
   constructor(top, count) {
      // 가장 마지막에 들어온 top에 해당하는 값
      this.top = null;
      this.count = 0;
   }

   push() {
      // return 값으로는 증가한 배열의 길이를 담는다.
   }

   pop() {
      // return 값으로는 top에서 나온 값 그 자체를 담는다. 여기서는 data!
   }

   stackTop() {
      // return 값으로는 가장 마지막에 있는 값을 담는다.
   }
}

이제 작성해야 하는 것은 Stack 객체의 각각의 메소드 구현이다.

• push 메소드는 기존에 아는 것 처럼 새로운 노드를 추가하고, 그 안에 값을 담는 것이다. 맨 마지막 노드가 만들어지는 것이고 스텍의 길이가 1 커져야 한다.
• pop 메소드는 역시 맨 마지막 노드의 값 자체를 빼야하는 메소드이다. 길이를 1 줄이고, 빼낸 값 그 자체를 리턴해야 한다.
• stackTop 메소드는 현재 stack 객체의 마지막 노드에 담긴 값을 리턴해야 한다. this.data를 이용하면 될 것이다.

 push(data) {
      let node = new Node(data);

      // 새롭게 생성된 노드는 이전의 top 값과 연결된다. 
      node.next = this.top;
      this.top = node;

      // push 메소드 자체가 리턴하는 값은 늘어난 stack의 크기
      return this.count += 1
   }


   pop() {
      // top 값이 없다면, false
      if (!this.top) {
         return false;
      }

      // top 값이 있다면
      // 맨 끝에 있는 data를 뽑아내고, top에는 바로 앞에 있는 값을 연결시킨다.
      let data = this.top.data;
      this.top = this.top.next

      this.count -= 1;

      return data;
   }


   stackTop() {
      // 현재 top 값으로 있는 것을 리턴
      return this.top.data;
   }

---

큐

• 가장 먼저 들어온 데이터가 가장 먼제 밖으로 나온다. FIFO 방식 (First In First Out)
• 배열에서 push 하고, shift로 꺼내는 방식 > 큐 개념에서는 enqueue, dequeue라고 한다.
• 가장 앞의 값을 알 수 있는 front가 있다.

class Node {
   constructor(data, next) {
      this.data = data;
      this.next = null;
   }
}

class Queue {
   constructor(count, head, rear) {
      // rear는 맨 끝을 의미한다.
      this.count = 0;
      this.head = null;
      this.rear = null;
   }  
}

이제 생각해봐야 하는 것은 Queue에서 사용되는 메소드 들이다.

• enqueue : 새로운 데이터를 가장 뒤에 집어넣는 형태, 생성된 노드가 없다면 가장 첫 값을 넣는다고 생각하면 된다. 즉 이 경우에는 head에 새로운 노드가 연결되는 것!
• dequeue : 제일 앞에 있는 데이터를 빼내는 것, 배열의 shift 메소드와 동일하다.
• front : 객체의 제일 앞에 있는 요소를 뱉어내는 것.

enqueue(data) {
      let node = new Node(data);

      // 첫 시작하는 값이 없다면,
      if (!this.head) {
         this.head = node;
      } else {
         this.rear.next = node;
      }

      this.rear = node;
      return this.count += 1; // 결국에는 크기를 1 늘려준 부분을 보여줘야 한다.
   }


   dequeue() {
      // 만약 연결된 값이 없다면, 즉 enqueue된 값이 없다면
      if (!this.head) {
         return false;
      }

      // head에 다음 요소를 연결시키고 크기 1 줄이기
      let data = this.head.data;
      this.head = this.head.next;
      this.count -= 1;

      return data;
   }


   front() {
      return this.head.data;
   }