Data Structures & Algorithms with Javascript : Stacks

 

2024.07.18 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Lists

2024.07.17 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Arrays

2024.07.17 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Intro

 

지난번 포스팅에서는 가장 기본적인 자료 구조인 list에 대해 살펴봤다.
데이터의 정렬 및 저장 순서가 중요하지 않으면 list 자료 구조로 충분히 데이터 관리를 할 수 있다.
하지만 더 복잡한 작업이 필요한 경우에는 부족할 수 있다.

👩🏻‍💻 오늘은 좀 더 복잡한 작업을 도와줄 자료 구조인 Stack에 대해 알아보자.

🥞 Stack 연산

스택 자료 구조는 리스트 맨 끝의 엘리먼트만 접근가능하다. 

스택 연산은 맛있는 팬케이크를 만들어 먹을 때랑 같다.

하나씩 구워서 접시에 쌓아 올리고, 위에 꿀이나 메이플 시럽을 뿌려서 위에서 아래로 한 장씩 먹는다.

스택 자료구조도 마찬가지로 LIFO (last-in-first-out), 마지막에 들어온 엘리먼트를 가장 먼저 접하는 구조다.

따라서 맨 위의 엘리먼트 이외의 엘리먼트에 접근하기 위해서는 먼저 그 위에 있는 모든 엘리먼트들을 제거 후 접근 가능하다.

 

스택 자료 구조에 엘리먼트를 추가하는 연산을 "push", 제거하는 연산을 "pop"이라고 한다.

이 과정을 그림으로 보자면 다음과 같다.

 

엘리먼트 1 push, 데이터 상태: [1]

엘리먼트 2 push , 데이터 상태 : [1 ,2]

엘리먼트 3 push , 데이터 상태 : [1 ,2, 3]

엘리먼트 pop , 데이터 상태 : [1 ,2]

엘리먼트 pop , 데이터 상태 : [1]

엘리먼트 4 push , 데이터 상태 : [1, 4]

 

 

 

 

주요 연산인 push 와 pop 말고도 peek연산이 있다.

스택 자료 구조 맨 위에 있는 엘리먼트를 보는 연산을 "peek"라고 한다.

pop은 맨 위의 엘리먼트를 보고 제거하는 반면, peek는 보기만 하는 연산이다.

🏗️ Stack 구현

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

class Stack{
	constructor(){
		this.dataStore = [];
        this.top = 0; // 맨 위의 엘리먼트의 위치 인덱스
	}
    push(element){
    	this.dataStore[this.top++] =element;
    }
	pop(){
		return this.dataStore[--this.top];
	}
    length(){
    	return this.top;
    }
    clear(){
		this.dataStore = [];
    	this.top = 0;
    }
	peek(){
    	return this.dataStore[this.top-1];
    }
}

const print = (item) => console.log(item);
const stack = new Stack();
stack.push('a');
stack.push('b');
stack.push('c');
print(stack.length()); // 3
print(stack.peek()); // c
const popped = stack.pop();
print(popped); // c
print(stack.peek()); // b
stack.push('d'); 
print(stack.peek()); // d
stack.clear();
print(stack.length()); //0
stack.push('A');
print(stack.peek()); // A

🏋️  Stack 사용해보기 

자릿수 바꾸기

우리는 10진수을 사용하고, 컴퓨터는 2진수로 동작한다.

스택 구조를 활용해 자릿수를 바꾸는 알고리즘을 쉽게 구현할 수 있다.

 

논리 흐름

 

1. 가장 오른쪽 숫자 n의 자릿수는 n% b이다. 이 숫자를 스택에 쌓고,

2. n을 n/b로 대체

3. n=0 가 될 때까지 1,2를 반복

4. 자릿수를 변경한 수가 없을 때까지 스택에서 pop 한다.

 

구현

function mulBase(num, base){
	let stack = new Stack();
	do {
		stack.push(num % base);
		num = Math.floor(num /= base);
	} while (num > 0);
	let convertedNum = '';
    while(s.length()>0){
		convertedNum+= stack.pop();
	}
	return convertedNum;
}

// 10진수 32를 2진수로 숫자 변경
const num32base2 = mulBase(32,2);
print(num32base2) // 100000
const num125base8 = mulBase(125,8);
print(num125base8) // 175

// 내장 함수 toString()으로 같은 걸 확인
print((32).toString(2)); // 100000
print((125).toString(8)); //175

팰린드롬

팰린드롬(회문)은 앞으로 읽나 뒤로 읽나 같은 문자를 뜻한다.

'토마토', '다시 합창합시다', '소주만 병만 주소', '여보 안경 안 보여', 1001 등이 팰린드롬이다.

스택을 활용해서 문자가 팰린드롬인지 여부를 확인할 수 있다.

 

 

논리 흐름

 

1. 원본 문자열에서 문자 하나씩 왼쪽에서 오른쪽으로 스택에 쌓는다.

2. 모든 문자열을 추가하면 스택은 원본 문자열을 역순으로 구성된 리스트다.

3. 스택에서 하나씩 pop 해서 합친 문자열이 원본과 같다면 팰린드롬이다.

 

구현

function isPalindrome(word){
 	const stack = new Stack();
	for(let i=0; i< word.length; i++){
		stack.push(word[i]);
	}
	let reversedWord = '';
	while(stack.length() > 0){
    	reversedWord += stack.pop();
    }
	return word === reversedWord;
}

print(isPalindrome('hello')); //false
print(isPalindrome('racecar')); //true

 

재귀

프로그래밍을 접한 사람이라면 "스택"이라는 말을 종종 들었을 것이다. 스택 오버플로우, 콜 스택, 스택 메모리 할당 등등.

스택은 재귀를 구현하는 데 사용되기도 한다. 재귀의 가장 대표적인 예는 팩토리얼 (factorial)이다.

5! = 5 * 4 * 3 * 2 * 1 = 120

 

팩토리얼은 base(시작점)인 5 자신을 1씩 감소하면서 1이 될 때까지 자신의 값을 곱한 것이다.

코드로 이를 옮겨보자면 다음과 같다.

function recursiveFactorial(n) { 
	if (n === 0) {
		return 1; }
	else {
		return n * factorial(n-1);
	} 
}

 

팩토리얼의 동작을 스택으로 나타내면 다음과 같다.

각 루프에서 n이 1이 될 때까지 스택에 push를 하고, 스택을 pop 하면서 이전 값에 계산을 해주면 위의 재귀 함수와 유사하게 구현할 수 있다.

function factorial(n){
	let stack = new Stack();
    while(n>1){
    	stack.push(n--);
    }
    let product = 1;
    while(stack.length() > 0){
    	product *= stack.pop();
    }
    return product;
}

print(factorial(5)); // 120
print(recursiveFactorial(5)); // 120

 

🍀 마치면서

오늘은 스택 자료 구조에 대해 살펴봤다.
기본적인 내용을 다뤄서 가볍게 읽고 정리할 수 있던 장인 거 같다.
다음에는 거의 짝꿍처럼 붙어 다니는 큐(queue)에 대해 살펴보자.

---

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9