스택(Stack), 큐(Queue)

 

[스택 / 큐]

 

---

 

<STUDY>

 

스택 (Stack)

후입선출(LIFO) 원칙을 따르는 데이터들의 모임

• 스택에 가장 마지막으로 추가된 요소가 가장 먼저 제거됨
• 삽입, 삭제 시간 복잡도 : O(1)
• 예시 : 호출스택, 실행 취소, 다시실행, 브라우저 접속 기록 추적 등 (뒤로가기)

 

배열을 이용한 스택 구현

• 프로그래밍 언어 자체에 스택이라는 데이터 종류가 내장되어 있기도 함 (JS 지원 X)
• push, pop을 이용하여 구현 (시간 복잡도 면에서 더 효율적임)
• unshift, shift를 이용하여 구현

let stack = [];
stack.push("google");
stack.push("instagram");
stack.push("youtube");

console.log(stack) // ["google", "instagram", "youtube"]

stack.pop(); // youtube

console.log(stack) // ["google", "instagram"]

 

클래스를 이용한 스택 구현

• push, pop 메소드

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

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

  push(value) {
    let newNode = new Node(value);
    if (!this.size) {
      this.first = newNode;
      this.last = newNode;
    } else {
      newNode.next = this.first;
      this.first = newNode;
    }

    return ++this.size;
  }

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

    const removeNode = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = removeNode.next;
    removeNode.next = null;

    this.size--;
    return removeNode.value;
  }
}

 

# 단일 연결 리스트와의 차이점

• 단일 연결 리스트의 pop 메소드는 앞에서부터 순회하면서 맨 뒤에서 2번째 노드를 찾아야 하기 때문에 O(1)을 가지지 않음
• 스택은 push와 pop 메소드 모두 O(1)의 시간 복잡도를 가짐

 

Big O
삽입	O(1)
삭제	O(1)
탐색	O(n)
접근	O(n)

 

큐 (Queue)

선입선출(FIFO) 원칙을 따르는 데이터들의 모임

• 큐에 가장 먼저 추가된 요소가 가장 먼저 제거됨
• 삽입, 삭제 시간 복잡도 : O(1)
• 예시 : 인쇄, 줄서기 등

 

배열을 이용한 큐 구현

• 프로그래밍 언어 자체에 큐라는 데이터 종류가 내장되어 있기도 함 (JS 지원 X)
• push, shift를 이용하여 구현
• unshift, pop을 이용하여 구현

let q = [];
q.push("first");
q.push("second");
q.push("third");

console.log(q) // ["first", "second", "third"]

q.shift(); // first

console.log(q) // ["second", "third"]

 

클래스를 이용한 큐 구현

• enqueue, dequeue 메소드

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

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

  enqueue(value) {
    let 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;

    let removeNode = this.first;
    if (this.size === 1) {
      this.last.next = null;
    }
    this.first = removeNode.next;
    removeNode.next = null;
    this.size--;

    return removeNode.value;
  }
}

 

Big O
삽입	O(1)
삭제	O(1)
탐색	O(n)
접근	O(n)

 

---

 

👉노트 보러가기👈

 

GitHub - ez1n/coding-test: 알고리즘 공부