알고리즘 특강 - 3. 스택, 큐

스택

LIFO(Last In First Out) 성격을 가짐

StackOverflow: 반복문에서 종료 조건을 지정하지 않거나 잘못된 종료조건을 지정하여 무한 루프가 발생하면 메모리의 스택영역이 쌓이고 쌓이다 터짐

 

역순의 성질을 사용해야 될 때 유용함

모바일 앱을 사용하면 뒤로 가기 버튼을 꽤 많이 누르게 되는데 이때 활용하는 자료구조가 스택. 뒤로 가기 버튼을 누르면 직전에 호출했던 스크린을 호출해야되는 특성때문.

Undo/Redo와 같은 기능도 스택을 이용.

 

• 픽(peek): 스택의 Top(맨 위) 데이터를 보는 것
• 푸시: 스택에 원소를 삽입하는 행위! 원소는 Top에 들어감
• 팝: 스택의 Top에서 원소를 가져오는 행위! 방금 위에서 넣었던 푸시된 원소가 나오게 됨

 

[링크드리스트 기반 구현 예제]

class Node {

    constructor(value) {

      this.value = value;

      this.next = null;

    }

  }

 

  class Stack {

    constructor() {

      this.head = null;

    }

 

    peek() {

      if (this.head === null) {

        return null;

      }

      return this.head.value;

    }

 

    push(value) { // 현재 [4] 밖에 없다면

      let newNode = new Node(value); // [3] 을 만들고!

      newNode.next = this.head; // [3] -> [4] 로 만든다음에

      this.head = newNode; // [3] -> [4] 로 만든다음에

    }

 

    pop() {

      if (this.head === null) { // 스택이 비어있으면

        return null; // 여기서도 메시지를 리턴하지말고 null 리턴!

      }

      let deleteHead = this.head; // 제거할 node 를 변수에 잡습니다.

      this.head = this.head.next; // 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.

      return deleteHead.value; // 그리고 제거할 node 반환

    }

  }

 

  let stack = new Stack();

 

  console.log(stack.peek()); // null, 스택이 비어 있음

 

  stack.push(1);

  console.log(stack.peek()); // 1

 

  stack.push(2);

  console.log(stack.peek()); // 2, 스택의 top이 2로 변경됨

 

  console.log(stack.pop()); // 2, pop()으로 인해 2를 제거하고 반환

  console.log(stack.peek()); // 1, 스택의 top이 1로 변경됨

 

  console.log(stack.pop()); // 1, pop()으로 인해 1을 제거하고 반환

  console.log(stack.peek()); // null, 스택이 비어 있음

 

  console.log(stack.pop()); // null, 스택이 비어 있으므로 null 반환

 

 

 

---

큐

FIFO(First In First Out)의 성격을 가짐

서버 접속 대기열 큐, 인쇄 대기열 큐 등에서 이용

 

픽(peek): 큐의 Front(맨 앞) 데이터를 보는 것

enqueue(삽입) : 큐에 원소를 삽입하는 행위! 원소는 Rear(맨 뒤)에 들어감

dequeue (뽑기): 큐에서 원소를 뽑아오는 행위! FIFO 자료구조니 Front에 위치한 원소를 뽑아옴

 

[링크드리스트 기반 구현 예제]

  class Node {

    constructor(value) {

      this.value = value;

      this.next = null;

    }

  }

 

  class Queue {

    constructor() {

      this.head = null;

      this.tail = null;

    }

 

    enqueue(value) {

      const newNode = new Node(value);

      if (this.head === null) { // 만약 비어있다면,

        this.head = newNode; // head(Front)에 new_node를

        this.tail = newNode; // tail(Rear)에 new_node를 넣어줍니다!

      } else {  // 비어있지 않다면 기존 tail에 새 노드를 포인터로 연결하고요!

        this.tail.next = newNode;

        this.tail = newNode; // 새 노드를 tail로 설정해요!

      }

    }

 

    dequeue() {

      if (this.head === null) {

        return null;

      }

      const deleteHead = this.head; // 제거할 node를 변수에 잡습니다.

     

      this.head = this.head.next; // 그리고 head(Front)를 현재 head의 다음 걸로 잡으면 됩니다.

 

      return deleteHead.value; // 그리고 제거할 node 반환을 해요!

    }

  }

 

  const queue = new Queue();

  queue.enqueue(1);

  queue.enqueue(2);

  queue.enqueue(3);

  console.log(queue.dequeue()); // 1

  console.log(queue.dequeue()); // 2

  console.log(queue.dequeue()); // 3

  console.log(queue.dequeue()); // null