2. Data Structure - Stack, Queue

xlsoh·2020년 9월 3일
0

TIL

목록 보기
5/23
post-thumbnail

스택(Stack)

Stack은 한 쪽 끝 (top) 에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 데이터를 저장하는 형식을 말합니다.
가장 먼저 들어온 데이터가 마지막으로 나가게 됩니다.

뷔페에 접시를 쌓아두면, 손님이 제일 위 접시부터 가져가는 맥락입니다. 새로운 접시가 쌓일 때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가지고 가는 것과 같습니다.

스택 활용 예시

  • 프링글스 감자칩
  • 하노이의 탑
  • 재귀 함수
  • 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여줍니다.
  • 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소합니다.
  • 후위 표기법 계산 : 기계가 사용하는 계산법

스택 property

  • Array를 사용한 Stack
    top(데이터 삽입/삭제하는 위치), maxSize(배열의 최대크기), stackArray(배열)
  • Linked list를 사용한 Stack
    top(데이터 삽입/삭제하는 위치), Node(스택을 구성하는 요소)

스택 메서드

  • push(element)
    요소를 스택의 최상단에 추가합니다.
  • pop()
    스택의 최상단에서 요소를 제거하고 반환합니다.
  • size()
    스택의 현재 요소 개수를 반환합니다.
  • peek()
    스택의 최상단에서 요소를 제거하지 않고 반환합니다.(pop은 제거하지만, peek은 제거하지 않습니다.)
  • isEmpty()
    스택이 비어 있으면 true, 그렇지 않으면 false로 반환합니다.

스택 구현

class Stack {
  constructor() {
    this.arr = [];
  }
  push(item) {
    this.arr.push(item);
  }
  pop() {
    return this.arr.pop();
  }
  peek() {
    return this.arr[this.arr.length - 1];
  }
}

const stack = new Stack();

큐 (Queue)

Queue는 자료를 뒤(rear)로 넣고 앞(front)으로 뺄 수 있는 (FIFO - First In First Out)구조로 데이터를 저장하는 형식을 말합니다.
먼저 집어 넣은 데이터가 먼저 나오게 됩니다.
삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정합니다.

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

큐 활용 예시

  • 은행 업무
  • 캐시(Cache) 구현
  • 선입선출이 필요한 대기열 (티켓 카운터)
  • 프로세서 처리
  • 너비 우선 탐색(BFS, Breadth-First Search) 구현

큐 property

  • Array를 사용한 Queue
    front(데이터 삭제하는 위치), rear(데이터 삽입하는 위치), size, arrQueue(배열)
  • Linked list를 사용한 Queue
    front, rear

큐 메서드

  • enqueue(element)
    요소를 큐의 뒤에 추가합니다.
  • dequeue()
    요소를 큐의 앞에서 제거하고 반환합니다.
  • size()
    큐의 현재 요소 개수를 반환합니다.
  • peek()
    스택의 front 요소를 제거하지 않고 반환합니다.
  • isEmpty()
    스택이 비어 있으면 true, 그렇지 않으면 false로 반환합니다.

큐 구현

class Queue {
  constructor() {
    this.arr = [];
  }
  enqueue(item) {
    this.arr.push(item);
  }
  dequeue() {
    return this.arr.shift();
  }
}

const queue = new Queue();
  • 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put할 수 없는 경우)를 오버플로우(overflow),
    큐가 비어 있어 자료를 꺼낼 수 없는 경우 (get 할 수 없는 경우)를 언더플로우(Underflow)라 합니다.
profile
주니어 프론트엔드 개발자

0개의 댓글