[2023-09-22] TIL - 스택

스택

Last In First Out이라는 개념을 가진 선형 자료구조

https://beenii.tistory.com/161

 

 

스택 메모리

 

스택을 Array로 표현하기

push : 배열에 순차적으로 값을 삽입한다.

pop : 가장 마지막 요소를 제거한다.

이런 방식은 배열의 단점인 중간요소 추가, 삭제 로직이 전혀 사용되지 않기 때문에 굉장히 유리한 방식이다.

 

또한 자바스크립트에서는 배열의 크기가 동적으로 변하기때문에 더 편하게 구현이 가능하다.

물론 자바스크립트의 배열은 Array타입은 아니므로 컴파일러언어보다는 성능이 떨어질 수 있다.

 

 

Linked List로 표현하기

스택을 Linked List로 표현할 수 있다.

이 경우 연길리스트의 haed가 Top이라고 할 수 있다.

 

자바스크립트에서 stack 사용법

const stack = [];

// Push 사용법
stack.push(1);

// Pop 사용법
stack.pop();

// Get Top
console.log(stack[stack.length -1]);

 

 

Linked List로 구현

class Node {
	constrictor(value){
    	this.value = value;
        this.next = null;
    }
}

class Stack {
	constructor(){
    	this.top = null;
        this.size = 0;
    }
    
    push(value) {
    	const node = new Node(value);
        node.next = this.top;
        this.top - node;
        this.size +=1;
    }
    
    pop(){
    	const value = this.top.value;
        this.top = this.top.next;
        this.size -= 1;
        return value;
    }
    
    
   	size() {
    	return this.size;
    }
}

const stack = new Stack();
stack.push(1);
stack.pop();

 

 

전위 순회

// 후위 순회 배열 스택
function PostOrderStack(s) {
  let answer;
  let stack = [];
  for (let x of s) {
    if (!isNaN(x)) stack.push(Number(x));
    else {
      let rt = stack.pop();
      let lt = stack.pop();
      if (x === "+") stack.push(lt + rt);
      else if (x === "-") stack.push(lt - rt);
      else if (x === "*") stack.push(lt * rt);
      else if (x === "/") stack.push(lt / rt);
    }
  }
  answer = stack[0];
  return answer;
}

let str1 = "35*2+9-";
console.log(PostOrderStack(str1));

후위 순회

// 전위 순회 배열 스택
function PreOrderStack(s) {
  let answer;
  let stack = [];
  for (let i = s.length - 1; i >= 0; i--) {
    if (!isNaN(s[i])) stack.push(Number(s[i]));
    else {
      let lt = stack.pop();
      let rt = stack.pop();
      if (s[i] === "+") stack.push(lt + rt);
      else if (s[i] === "-") stack.push(lt - rt);
      else if (s[i] === "*") stack.push(lt * rt);
      else if (s[i] === "/") stack.push(lt / rt);
    }
  }
  answer = stack[0];
  return answer;
}

let str2 = "-+*3529";
console.log(PreOrderStack(str2));