210119_TIL.. 자료구조(Stack, Queue)

오늘한 일

• Data Structure_1
• Stack, Queue 개념 이해와 코드로 구현해보기
• 자료 구조의 모양을 추상적으로 표현해보기(그림)
• 스택과 재귀호출의 연관성에 대한 학습
• Javascript 에서 Stack, Queue 자료구조가 가지고 있는 property 와 method 찾기

 

 

 Stack 

Stack(스택)은 가장 나중에 삽입된 데이터가 먼저 삭제되는 특성의 자료형을 추상화한 것이다.

LIFO(Last In First Out), 후입선출

ex) 식상에서 식판을 쌓는 것, 책을 위로 쌓아 놓는 것, 벽돌을 샇아 올리는 것, 프링글스 통 안에 감자칩

우리가 프링글스 통안에 든 감자칩을 먹기 위해서는 가장 위에 있는 감자칩부터 꺼낸다. => LIFO 구조이다.

이 처럼 Stack 은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

 

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. - 위키백과, "스택"

 

밑이 막혀 있는 프링글스 통안을 생각해보면, 밑이 막혔으니 위로만 감자칩을 집어 넣을 수 있고, 뺄 수가 있다.

 

 

1. Stack 연산

• pop() : 가장 위에 있는 item을 꺼낸다.
• push(item) : 가장 위에 item을 쌓는다.
• peek() : 스택에서 가장 위에 있는 항목을 반환한다. 이때, 마지막 위치인 pop 과 push 가 일어나는 곳을 top 이라고 한다. top 은 항상 맨위를 가리킨다. top은 스택의 크기와 같다.

 

 

2. Stack 응용

• undo, 가장 최근에 실행한 명령어를 취소하는 것, Ctrl + Z : 가장 최근에 실행한 명령어를 취소해야하기 때문에 마지막에 들어간 자료가 먼저 나오는 스택 구조
• 웹 브라우저 뒤로가기 버튼 : 방문기록에서 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 수식의 괄호 검사 : 연산자 우선순위 표현을 위한 괄호 검사

 

 

3. Stack 구현(Javascript)

• 빈 스택의 크기는 0, top은 -1 이다.
• 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 한다.
• pop 연산은 가장 최근에 추가된 요소를 제거(LIFO)해야 한다.
• top은 가장 최근의 요소의 위치를 가리켜야 한다.
• 스택의 크기 이상의 pop 연산을 실행해도 문제없이 빈 스택이 되어야 한다.
• push와 pop은 후입선출(LIFO)을 구현해야 한다.

 

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1;
  }

  size() {
    return Object.keys(this.storage).length;
  }

  push(element) {
    this.top++;
    this.storage[this.top] = element; //-1 0 1 2 3
    return this.size();
  }

  pop() {
    let result = this.storage[this.top];
    delete this.storage[this.top];
    this.top--;
    return result;
  }
}

 

Stack 관련 '카카오톡' 코딩테스트 문제

 

 

 Queue 

큐는 스택과 다르게 'FIFO, 선입선출'의 구조를 가지고 있다.

스택은 막힌 통안에 먼저 들어온 것이 가장 나중에 나가는 구조라면,

큐는 양쪽으로 뚫려 있는 통안에서 먼저 들어온 것이 먼저 나가는 구조이다.

 

 

 

 

1. Queue 연산

• Enqueue() : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표를 발부
• Dequeue() : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제
• front : 큐의 맨앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호
• rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호
• isFull() : 큐가 꽉 찼는지 확인. rear = n-1 즉 rear가 마지막 인덱스이면 꽉 찬것 (선형 큐)
• isEmpty() : 큐가 비었는지 확인. front = rear 이면 큐가 비었다고 판단 (선형 큐)

 

 

2. Queue 구현(Javascript)

• 빈 큐의 크기, front, rear는 모두 0이다.
• 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 한다.
• dequeue는 가장 먼저 저장된 요소를 제거(FIFO)해야 한다.
• front는 가장 오랜된 요소의 위치, rear는 다음에 추가될 요소의 위치를 가리켜야 한다.
• 큐의 크기 이상의 dequeue 연산을 실행해도 문제없이 빈 큐가 되어야 한다.
• enqueue와 dequeue는 선입선출(FIFO)을 구현해야 한다.

 

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0; // 삭제
    this.rear = 0;  // 삽입
  }

  size() {
    return Object.keys(this.storage).length;
  }

  enqueue(element) {  //삽입
    this.storage[this.rear] = element;
    this.rear++;
    return this.size();
  }

  dequeue() { //삭제

    if (this.size() === 0) {
      return this.storage;
    }

    let result = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    return result;
  }
}

 

 

Queue 관련 코딩테스트 문제