스택(Stack)과 큐(Queue)의 개념 정리_(1) Stack

Stack(접시)을 나타내는 이미지

1. 스택(Stack)의 개념

• 스택은 쌓여있는 접시 더미와 같다.
  : 새로운 접시가 쌓일 때도 맨위에서 쌓이고, 접시를 가져갈 때도 맨위에서 가지고 간다.
• 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조적 특징을 가진다.
  : LIFO ( Last In, First Out )
• top은 스택에서 삽입과 삭제가 일어나는 지점으로, 가장 최근에 들어온 자료를 가르킨다.
  : 스택에서 top을 삽입하는 연산을 'push', top을 삭제하는 연산을 'pop' 이라고 한다.
• 자료를 삽입할 경우 top을 증가시키고, 삭제 시 감소 시킨다.

2. 스택의 활용 예시

• 웹브라우저의 방문기록(뒤로가기)
  : 가장 나중에 열린 페이지부터 보여준다.
• 역순 문자열 만들기
  : 가장 나중에 입력된 문자부터 출력
• 실행 취소 (undo)
  : 가장 나중에 실행된 것 부터 실행 취소
• 후위 표기법 계산
• 수식의 괄호 검사 ( 연산자 우선순위 표현을 위한 괄호 검사)

3. 스택을 객체와 함수로 구현해보기

stack에 쌓이는 자료들을 모은 것을 하나의 객체로 표현을 하고,
스택에 자료를 넣고, 빼는 것을 push( ), pop( ) 함수로 구현해볼 수 있다.

 

3-1. 스택의 생성 

스택은 인덱스와 값으로 연결된 하나의 객체로 표현해 볼 수 있다.

초기의 스택은 비어있으며, 이때   top = -1  로 지정하여, 객체에서 그무엇도 가르키지 않는다.

 

 

 

 

3-2. 스택의 추가 (Push)

 

push(element) {
  this.top += 1;
  this.storage[this.top] = element;
}

스택이 추가 될 경우 top이 가르키고 있는 인덱스주소를 1 증가시키고, 해당하는 인덱스주소에 받은 자료값을 저장하여 준다.

 

3.2 스택의 삭제 (Pop)

pop() {
    let topValue = this.storage[this.top]

    if (this.top === -1) {
      return undefined;
    }
    else {
      delete this.storage[this.top];
      this.top -= 1;
      return topValue;
    }
  }

스택의 삭제연산이 실행될 경우  top의 값이 -1 이여서 빈객체일 때의 예외처리를 먼저해준다.
1) 일반적인 경우 현재 top의 주소를 삭제하여, 저장되어 있는 top의 값을 포함한 스택을 삭제하여 준다.
2) 이후 top의 값을 1 감소 시켜, top이 현재 최상단에 위치한 stack의 주소값을 가르키도록 한다.

 

3.3. 클래스로 나타낸 스택의 코드

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1;
  }
  // size() - 스택의 현재 요소 개수를 반환합니다.
  size() {
    return Object.keys(this.storage).length;
  }

  //  push(element) - 요소를 스택의 최상단에 추가합니다.
  push(element) {
    this.top += 1;
    this.storage[this.top + 1] = element;
  }

  // pop() - 스택의 최상단에서 요소를 제거하고 반환합니다.
  pop() {
    let result = this.storage[this.top]

    if (this.top < 0) {
      return undefined;
    }
    else {
      delete this.storage[this.top];
      this.top -= 1;
      return result;

    }
  }
}

 

출처 및 참고

www.atoz-develop.tistory.com/

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

 

4. 스택과 관련된 프로그래머스 문제 풀어보기

programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임