[Linear] Stack

메모리 안의 데이터를 효율적으로 처리하기 위한 자료구조

FILO(First in Last Out), LIFO(Last in First Out) 의 의미.

 

구현방법은 두가지가 있다.

 

1. 정적인 1차원 배열 : 구현하기 쉬우며, 사이즈를 미리 알아야한다.

 

2. Dynamic Array : 리스트이며, 사이즈를 몰라도 되지만, 구현하는데 어렵다.

 

위 그림이 대표적인 스택의 모습이다.

 

또한 우리가 살아오면서 스택을 몸소 실천하면서 살아왔다.

 

전형적인 스택 구현

맨 아래부터 차곡차곡 엎드리고 사람을 쌓으면, 위에있는 사람먼저 내려와야 안전하다.

 

더이상 설명은 안해도 이해할 것으로 믿는다.

 

ADT(추상 데이터 타입)은 push, pop, peek, isEmpty가 있다.

Pseudo 코드
stack arr[10] 생성
Top = 0 생성/초기화

데이터 Push(data)함수 생성
Top이 배열의 길이보다 작으면 배열에 data 삽입,
Top++ 증가.
배열의 길이보다 크면
"스택 오버플로우" 메시지 출력 후 끝.

데이터 Pop() 함수생성
Top이 0보다 작으면 "스택 언더플로우 메시지 출력"
Top이 0보다 크면 Top -- 감소.
result 변수에 stack arr[Top] 값 저장.
stack arr[Top]에 null 저장. 
result 리턴.

peek() 함수생성
stack Arr[stack Arr.length-1] 값을 반환

isEmpty() 함수생성
Top === 0 이면 true 반환

1. functional instantiation

//필요로하는 메서드
//push(element(s))
//pop()
//peek() : 맨 위에 있는 스택 요소 리턴 받음.
//isEmpty() : 스택이 비어있으면 0리턴.
// clear() : 스택의 모든 요소 지워버림
// size() : 스택크기 반환. array의 length와 유사.

function Stack(){
  let items =[];

  this.push = function(element){
    if(items.length === 10){
     console.log("stack overFlow");
    }else{
      items.push(element);  
    }  
  };  

  this.pop = function(){
    if(items.length <= 0){
      console.log("stack underFlow");
    }
    items.pop();
  };    
  
  this.peek = function(){
    return items[items.length-1];
  };   
  
  this.isEmpty = function(){
    return items.length == 0;
  };    

  this.size = function(){
    return items.length;  
  };  

  this.clear = function(){
    items = [];
  };    

  this.print = function(){  
    console.log(items.toString()); 
  };
  
}

let stack = new Stack();
stack.isEmpty();   //true
stack.push(5);
stack.push(8);
stack.peek(); // 8
stack.isEmpty();  //false
stack.clear();  
stack.print(); // ''

2. Pseudoclassical instantiation

class Stack{
  constructor(){
    this.items = [];    
  }  
}

Stack.prototype.push = function(element){
  if(this.items.length === 10){
    console.log("stack overFlow");
  }else{
    this.items.push(element);  
  }  
}  

  Stack.prototype.pop = function(){
  if(this.items.length <= 0){
    console.log("stack underFlow");
  }
  this.items.pop();
};    
  
  Stack.prototype.peek = function(){
  return this.items[this.items.length-1];
};   
  
  Stack.prototype.isEmpty = function(){
  return this.items.length == 0;
};    

  Stack.prototype.size = function(){
 return this.items.length;  
};  

  Stack.prototype.clear = function(){
 this.items = [];
};    

  Stack.prototype.print = function(){    console.log(this.items.toString()); 
};

let stack = new Stack();
stack.push(5);
stack.push(5);
stack.push(5);
stack.push(5);
stack.push(5);
stack.push(5);
stack.push(5);
stack.push(5);
stack.push(5);
stack.push(5);

stack.peek();
stack.size();