[자료구조] 스택

포스팅 옮기는 중

---

github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/stack

trekhleb/javascript-algorithms

Stack

스택은 추상 자료형( ADT - abstract data type )이다
스택은 LIFO이다
스택은 선형 데이터 자료구조( linear data structures ) 이다.

추상 자료형

추상적 자료형은 구현 방법을 명시하고 있지 않다.
추상적 자료형은 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다.

예를 들어, 
전기 밥솥을 추상적 자료형에 비유한다면, 그 속에 들어가는 밥은 자료가 되고, 밥솥에 있는 취사, 예약취사 버튼들과 남은 시간을 표시하는 디스플레이에 어떤 내용들이 표시되어야 하는지를 명기한 것이다.
추상적 자료형에서는 이것들이 어떻게 구성되는지 관심이 없고, 몇 와트의 전기를 소모하는지에 대해서도 관심이 없다.

스택은 두가지 주요 연산을 가진다

• 요소(element)를 추가하는 push
• 가장 최근에 추가된 요소를 삭제하는 pop

가장 최근에 들어온 요소(element)가 가장 먼저 나간다. = LIFO ( Last in, First out ) 

https://github.com/trekhleb/javascript-algorithms/tree/master/src/data-structures/stack

자바스크립트로 스택 구현하기

class Stack{
	constructor(){
    	this.items = []; // 스택
        this.count = 0; // 스택 안에 있는 데이터 개수, 스택 top 위치 - 1
    }
    
    // push
    push(element){
    	// 스택에 추가
    	this.items[this.count] = element;
        // 추가되었으니 count에 +1
        this.count++;
        console.log(`${element} added to ${this.count}`);
        
        return this.count - 1;
    }
    // pop
    pop(){
    	// 스택이 비었을 경우
    	if(this.count == 0) return undefined;
        // 배열은 0부터 시작이라서  this.count - 1
    	let deleteItem = this.items[this.count-1];
        // 삭제했으니 this.count - 1
        this.count--;
        console.log(`${deleteItem} removed`);
        return deleteItem;
    }
    
    // isEmpty ? 스택이 비었는지 확인하기
    isEmpty(){
    	console.log(this.count==0 ? 'is Empty' : 'is Not Empty');
        return this.count == 0; 
    }
    
    // peek, 가장 위에있는 요소를 확인하기 ( 삭제 아님 )
    peek(){
    	if(this.isEmpty){
        	console.log("Stack is Empty");
      		return this.isEmpty;
        }
    	console.log(`Top element is ${this.items[this.count - 1]}`);
		return this.items[this.count -1];
    }
    
    // print, 스택의 내용을 보여줌
    print(){
    	let str='';
        this.items.forEach((element)=>{
        	str += element + " ";
        });
        return str;
    }
    
    // clear, 스택을 비움
    clear(){
    	this.items = [];
        this.count = 0;
        console.log("Stack cleared..");
        return this.items;
    }
}