[자료구조/알고리즘][Codestates] Stack

자료구조 Stack과 Queue에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다.

코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다.

Achievement Goals

• 자료구조에 대해 이해한다.
• Stack , Queue 자료구조에 대해 이해한다
  • 각 자료구조가 가진 특징을 학습한다.
  • 각 자료구조를 사용하기 적합한 상황을 이해한다
  • 다른 자료구조와의 차이점을 이해하기 위해 자료 구조 내부를 직접 구현한다.
  • 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체해볼 수 있다.

0. 추상 자료형 (ADT : Abstract Data Type )

자료구조를 공부하기에 앞서 추상 자료형 ADT를 먼저 이해하고 시작해야 한다.

추상 자료형은 Computer Science에서 자주 등장하는 용어이다. 영역에 따라 의미의 차이가 조금씩 있지만 자료구조의 관점에서의 ADT를 알아보자.

구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것

즉, 추상데이터타입은 자료형을 추상적으로 정의하는 것을 의미하며, 데이터의 선언과 연산의 선언으로 이루어진다.

아래와 같이 Integer라는 자료형이 있을 때 data와 method의 선언으로 이루어진다.

참고사이트

function Integer(X){
    //멤버변수
    this.data = X;
    //메소드
    this.ADD = ADD;
    this.SUB = SUB;
    this.MUL = MUL;
    this.DIV = DIV;
    this.MOD = MOD;
}
Integer.prototype.ADD(X,Y) { return X+Y; }
Integer.prototype.SUB(X,Y) { return X-Y; }
Integer.prototype.MUL(X,Y) { return X*Y; }
Integer.prototype.DIV(X,Y) { if(Y==0) return null; else return X/Y; }
Integer.prototype.ADD(X,Y) { if(Y==0) return null; else return X%Y; }

1. 자료구조 (Data structure)

• 자료구조란?
  • 자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명한다.
  • 프로그램은 데이터를 표현하고(저장 포함) , 그렇게 표현된 데이터를 처리하는 것이다.
  • 데이터의 저장을 담당하는 것이 자료구조이다.
• 자료구조는 왜 필요한가?
  • 필요에 따라 데이터의 특징을 분석하여 정리하고 활용해야 한다.
  • 데이터를 체계적으로 정리하여 저장해두고 활용하기 위해 만들어졌다.
  • 다양한 상황에 맞는 데이터를 효율적으로 다루기 위해 필요하다.
  • 대부분의 자료구조는 특정한 상황에 놓인 문제를 해야 하는 데에 특화되어있다.
  • 많은 자료구조를 알아두면, 특정 문제를 해결하는데 적합한 자료구조를 빠르게 찾아 문제를 해결할 수 있다.
  • 자료구조가 정해져야 그레 따른 효율적인 알고리즘을 결정할 수 있다.
  • 자료구조는 아래와 같이 분류할 수 있다.

**Stack** 이란

-   Stack은 단어의 뜻과 비슷하게 **데이터를 순서대로 쌓는 자료구조** 이다.

-   나중에 들어간 데이터가 먼저 나오는 구조이면 후입선출 , Last-In-First-Out(LIFO) 자료구조 라고도 불린다.

**Stack의 실 사용**

"브라우저의 뒤로가기, 앞으로가기" 를 예로 들 수 있다.  
현재 페이지에서 이전 페이지로 갈 때 현재 페이지를 Next Stack 에 보관하고 Prev Stack에 저장되어있는 이전에 봤던 페이지를 가져온다. 
앞으로 이동할 때에는 Next Stack의 가장 마지막으로 보관된 페이지를 가져온다 

 

**Stack의 시간 복잡도 (Big-O)**

-   데이터 삽입 : 맨 뒤에 데이터를 추가하므로 시간 복잡도는 O(1)이다.

-   데이터 삭제 : 맨 뒤에 데이터를 삭제하므로 시간 복잡도는 O(1)이다.

-   데이터 탐색 : 모든 데이터를 확인해야하므로 시간 복잡도는 O(n)이다.


**Stack ADT의 정의**

-   Stack : 배열 또는 Object로 정의됨 stack 그 자체

-   Stack을 대표하는 연산

    -   push : Stack을 쌓음

    -   pop : Stack을 꺼냄

    -   peek : Stack의 맨 위의 요소를 확인

    -   lefts : Stack에 있는 모든 요소 문자열로 반환

    -   clear : stack에 있는 모든 요소 삭제

    -   empty : Stack의 남은 요소가 있는지 확인

이 ADT를 기반으로 Satck을 구현해보자. 먼저 Class로 구현을 해보고 JS Array로 구현을 해본다.

**Stack의 구현**

-   **Class를 사용하여 Stack을 구현**

        class Stack {
          constructor() {
            this.storage = {};
            this.top = 0; //  Stack의 가장 상단을 가리키는 포인터 변수를 초기화한다.
          }

          size() {
            return this.top;
          }

          push(element) {
            this.storage[this.top] = element;
            this.top += 1;
          }
          // 가장 나중에 추가된 데이터가 먼저 추출되어야 한다.
          // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 말아야 한다.
          pop() {
            if (!this.size()) return;

            const result = this.storage[this.top - 1];
            delete this.storage[this.top - 1];
            this.top -= 1;
            return result;
          }
          peek() {
            return this.storage[this.top - 1];
          }

          lefts() {
            const str = Object.values(this.storage).toString();
            return str;
          }

          empty() {
            return !this.size() ? true : false;
          }
          clear() {
            this.storage = "";
            return "This Stack is cleared";
          }
        }

        const stack = new Stack();
        console.log(stack.size()); //0
        console.log(stack.empty());
        for (let i = 1; i < 10; i++) stack.push(i);

        console.log(stack.pop()); //9
        console.log(stack.pop()); // 8
        console.log(stack.size()); // 7
        console.log(stack.push(8));
        console.log(stack.size()); // 8
        console.log(stack.peek());
        console.log(stack.lefts());
        console.log(stack.clear());
    ```




    -

**Array를 사용하여 Stack 구현**

Array의 몇 가지 메서드로 Stack을 구현한 수 있으며, 구현하는 시간을 절약할 수 있다.

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; //  Stack의 가장 상단을 가리키는 포인터 변수를 초기화한다.
  }

  size() {
    return this.top;
  }

  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
  // 가장 나중에 추가된 데이터가 먼저 추출되어야 한다.
  // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 말아야 한다.
  pop() {
    if (!this.size()) return;

    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    return result;
  }
  peek() {
    return this.storage[this.top - 1];
  }

  lefts() {
    const str = Object.values(this.storage).toString();
    return str;
  }

  empty() {
    return !this.size() ? true : false;
  }
  clear() {
    this.storage = "";
    return "This Stack is cleared";
  }
}

const stack = new Stack();
console.log(stack.size()); //0
console.log(stack.empty());
for (let i = 1; i < 10; i++) stack.push(i);

console.log(stack.pop()); //9
console.log(stack.pop()); // 8
console.log(stack.size()); // 7
console.log(stack.push(8));
console.log(stack.size()); // 8
console.log(stack.peek());
console.log(stack.lefts());
console.log(stack.clear());

**생각해 볼 주제들**

-   배열로 Stack, Queue를 사용할 때 주의해야 할 사항은 어떤 것들이 있나요?.
    -   Queue를 배열로 구현할 때에는 Overflow를 주의해야한다 front와 reat 포인터는 계속 증가하기 때문이다.

-   JavaScript의 배열과 Stack, Queue는 어떤 차이가 있나요?

    -   Stack은 LIFO 추상 데이터 유형이면 선형 데이터 구조이다

    -   반면 배열은 적어도 하나의 배열 인덱스 또는 키로 식별되는 요소모음으로 구성된 데이터 구조이다

    -   배열은 항상 처음부터 참조되지만 스택은 항상 일부 작업 끝 위치에서 참조된다.

참고자료