Stack in Date structure

Stack

일반적으로 접시를 쌓을 때, 아래에서 부터 위로 쌓고,

사용할 때에는 위에 있는 접시 먼저 사용한다.

(LIFO : Last in, First out 후입 선출의 개념)

한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조

//제일 마지막에 들어온 데이터가 제일 빨리 나가는 방식

 

스택은 이처럼 쌓여있는 접시더미와 같이 작동하는 자료구조다.

 

 

Stack 그림예제_출처 : 코드스테이츠

스택이 가지고 있는 method

push(element) - 요소를 스택의 최상단에 추가한다.
pop() - 스택의 최상단에서 요소를 제거하고 반환한다.
size() - 스택의 현재 요소 개수를 반환한다.
top() - 가장 위에 있는 데이터

//peek, head라고도 불린다.
isempty() - 스택에 원소가 없으면 true, 있으면 false

 

코드로 구현해보기_Array(배열) in Javascript

class Stack{
  constructor() {
    this.storage = []
    this.top = 0; // 배열의 젤 뒤의 값
  }
  
  size(){
    return this.top
  }//현재 탑의 값을 return
  
  push(element){
    this.storage.push(element)
    this.top++//추가될 때, size+
  } //element를 Stack에 추가
  
  pop(){
    this.top--//제거될 때, size-
    return this.storage.pop()
    }//탑의 값을 제거하고 그 요소의 값을 return
    
  isempty(){
    if(this.top === 0){
      return true;
    } return false;  
  }
  //Stack안에 요소가 있는지 확인
  //없으면 true, 있으면 fasle

} 

<-- 사용해보기 -->

let stack = new Stack;

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

stack; 
//Stack{storage : Array(4), top : 4}
//storage : (4)[1,2,3,4] , top : 4

stack.pop(); // 4

stack.size(); // 3

stack;
//Stack{storage : Array(3), top : 3}
//storage : (3)[1,2,3] , top : 3

stack.isempty(); //false

코드로 구현해보기_Object(객체) in Javascript

class Stack{
  constructor() {
    this.storage = {}
    this.top = 0; // 객체의 젤 위의 값
  }
  size(){
    return this.top
  }//현재 탑의 값을 return
  
  push(element){
    this.storage[this.top] = element
    this.top++//추가될 때, size+
  } //element를 Stack에 추가
  
  pop(){
    this.top--//제거될 때, size-
    let result = this.storage[this.top];
    delete this.storage[this.top];
    return result;
    }//요소 하나를 제거하고 그 요소의 값을 return
    
  isempty(){
    if(this.top === 0){
      return true;
    } return false;  
  }
  //Stack안에 요소가 있는지 확인
  //없으면 true, 있으면 fasle

} 

//사용법은 동일하나, storage가 객체인 것만 다르다.

 

스택의 시간복잡도

추가하기 : O(1)

삭제하기 : O(1)

가져오기 : O(n)

//top을 하나씩 까면서 조회해야 하기 때문

 

스택을 이용한 예

[뒤로 가기, 앞으로 가기], 재생목록 관리, 런타임에서 함수의 호출을 관리 등..