[2022.12.25 ~ 2022.12.31] 스택 큐

스택과 큐 요약

개념

• 스택
  • 후입선출 형태 : 마지막에 들어간 원소가 먼저 나옴
  • 아래부터 위로 쌓이는 구조
  • 데이터 입출력이 한 종단점에서 이루어짐(top)
  • 스택이 비었을때 꺼냄→ stackunderflow
  • 스택이 꽉찼는데 넣음→ stackoverflow
• 큐
  • 선입선출 : 먼저 들어간 원소가 먼저 나옴
  • 입출력이 양 끝단에서 이루어짐 : rear로 들어와(삽입, enqueue) front(삭제, dequeue)로 빠짐

시간 복잡도

• 스택
  • 삽입(push), 삭제(pop) 모두 O(1)
• 큐
  • 삽입(enqueue), 삭제(dequeue) 모두 O(1)(** JS 내장메소드 shift사용시 O(N)임!)

장점

• 스택
  • top을 통해서만 데이터에 접근하기에 삽입, 삭제 빠름
• 큐
  • 삽입, 삭제가 빠름

단점

• 스택
  • top 이외에는 접근할 수 없어 탐색이 힘듬. 탐색하려면 다 꺼내보면서 진행해야함
• 큐
  • 탐색이 힘듬

어떤 형태의 문제를 풀 수 있을지

• 스택
  • 역추적 작업(뒤로가기, undo)
• 큐
  • 주로 데이터를 입력된 시간 순서대로 처리해야할 때 사용

Use case

• 스택
  • 컴파일러 : 변수나 메소드 호출을 컴퓨터 메모리에 저장할 때 쓰임
  • 브라우저 뒤로가기: 가장 마지막에 열린 페이지부터 다시 보여줌(undo도 비슷한 원리)
  • 함수 콜스택(재귀 알고리즘)데이터 역순 출력
  • 깊이우선탐색(DFS)
• 큐
  • 프린터 출력 대기
  • 프로세스 관리
  • 캐시 구현
  • 너비 우선 탐색(BFS)

연결리스트로 스택/큐 구현해보기

스택

• 연결리스트로 스택을 구현 할 시, O(1)의 삽입/삭제 시간복잡도를 갖도록 해야합니다.

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

class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  push(val) {
    const newNode = new Node(val);

    this.size++;

    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      const temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }

    return ++this.size;
  }

  pop() {
    if (!this.first) {
      return null;
    }

    if (!this.size) {
      this.last = null;
    }

    const temp = this.first;

    this.first = this.first.next;
    this.size--;

    return temp.value;
  }
}

큐

• 배열로 큐를 구현하는 경우, Array.shift/ Array 메소드가 O(n)의 시간 복잡도를 가지게 됩니다.
• 따라서 연결리스트로 구현할 경우 O(1)의 시간복잡도로 삽입/삭제를 구현할 수 있습니다.

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

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);

    if (!this.size) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }

    return ++this.size;
  }

  dequeue() {
    if (!this.size) return null;

    if (this.size === 1) {
      this.last = null;
    }

    const temp = this.first;
    this.first = this.first.next;
    this.size--;

    return temp.value;
  }
}

어떤 문제에서 스택과 큐를 사용할 수 있을까?

스택

• 가장 최근의 데이터가 필요한 경우에 많이 사용합니다. 이를 시간지역성을 활용할 수 있다고 표현할 수 있습니다.
• 자료구조를 뒤집을 때 많이 사용합니다. 들어가는 역순으로 데이터가 나오게 되어 데이터를 뒤집을 때 유용합니다.
• 스택을 동적으로 사용하는 경우, 중첩된 구조를 파악 할 때도 사용할 수 있습니다. 이를 테면 html의 구조를 생성할 경우 스택에 태그가 열리는 정보와 닫히는 정보를 스택으로 관리할 수 있듯이요.

큐

• 우선순위가 중요한 데이터를 다룰 때 많이 사용하게 됩니다.
• 주로 데이터를 입력된 시간 순서대로 처리해야할 때 사용하게 됩니다.
• 큐를 동적으로 사용하는 경우, 연속된 서브 배열을 구하는 경우에 용이합니다.