Stack

Data Structure란?

Data Structure는 데이터 구성,관리 및 저장 형식을 효율적으로 엑세스 및 수정을 하게 끔 모아둔 자료들을 의미한다.

 

Stack

Stack의 개념

push를 하면 처음 push 가 되었던 Data A가 쌓인다

pop()을 하게 되면 맨 위에서 부터 빠져나온다

위의 그림같이 진행 되는걸 LIFO(Last In First Out)이라고 한다
맨 처음 push 됬던게 제일 마지막에 빠져 나온것 이라고 보면 된다

stack은 할당된 공간이 있으며 할당된 공간이 모두 사용된 경우 push를 사용할수없게 된다
할당된 공간이 모두 사용되었지만 그럼에도 불구하고 push를 한경우 stack overflow가 발생된다
또한 할당된 공간이 비어있을때 pop이 시도 될때 stack underflow가 발생된다

 

JavaScript를 사용해서 구현

youtu.be/D_NbDvvuTOM

class Stack {
  constructor() {
  	//data 저장 공간
    this.storage = {};
    //최근의 data 위치(?) ===  저장공간의 key
    this.top = -1;
  }
	//data의 사이즈(길이)를 표현
  size() {return Object.keys(this.storage).length}
  
  //(중요)push 는 push 했을때 저장공간을 나타내야 한다
  push(element) {
  	//push가 됬으므로 저장공간의 data 위치 +1
    this.top++
    //obj 형식이니 obj 형식대로 추가
	//key는 top의 값으로 value는 element로 넣어줌
    this.storage[this.top] = element
  }
	//(중요)pop은 pop 했을때 제거된 항목을 저장하므로 저장공간을 나타내는게 아님 
  pop() {
  	//변수선언 remove data 저장공간[최근 data 위치]
    let remove = this.storage[this.top]
    //없애준다 최근 data를
    delete this.storage[this.top]
    //data 저장공간에서 없어졌으니 top도 변화가 필요함 -1
    this.top--
    //없애준 data 반환해야하니 return remove
    return remove
  }
}

pop에 대해서 자세하게 살펴 봅시다

 pop() {
    let remove = this.storage[this.top]
    delete this.storage[this.top]
    this.top--
    return remove
  }
  
  const stack = new Stack()

  stack.push('a')//{0:'a'}
  stack.push('b')//{0:'a',1:'b'}
  stack.push('c')//{0:'a',1:'b',2:'c'}
  stack.pop()//{2:'c'}

여기서 왜 remove 변수를 선언 했냐면
일단 remove는 {2:'c'}를 가리킵니다 그럼 remove 변수 안에 값이 저장이 되어 있죠
그런데 다음으로 storage안에 있는 값을 삭제를 시켜줍니다
그럼 remove 변수는 어떻게 되었을까요?

 

한가지 예제를 보여드리도록 하겠습니다

이런식으로 temp는 1을 가지고 있습니다 a를 변화 시킨다면요?

a를 변화를 시켜주어도 temp는 전에 있던 a의 값인 1을 가지고 있습니다 a는 2를 가지고 있는데도요

 pop() {
    let remove = this.storage[this.top]
    delete this.storage[this.top]
    this.top--
    return remove
  }
  
  const stack = new Stack()

  stack.push('a')//{0:'a'}
  stack.push('b')//{0:'a',1:'b'}
  stack.push('c')//{0:'a',1:'b',2:'c'}
  stack.pop()//{2:'c'}

그렇다면 여기서 변수 remove는 this.storage[this.top]을 가지고 있는 상태에서
this.storage[this.top]을 삭제를 시켜줘도 변화가 없는것이죠

그렇다면 remove를 반환을 시켜주면 전에 삭제를 시켰던 this.storage[this.top]가 반환이 되는것이죠

 

 

 

 

 

참고 문서

en.wikipedia.org/wiki/Data_structure

Data structure - Wikipedia

en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

Data Structures/Stacks and Queues - Wikibooks, open books for an open world

www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

Data Structure and Algorithms - Stack - Tutorialspoint