Stack

1. 스택이란 ?

---

---

• 스택(Stack)은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.
• Stack은 직역 그대로, 데이터(data)를 순서대로 쌓는 자료구조이다.
• Stack의 특징 : 입력과 출력이 하나의 방향으로 이루어져 접근이 제한적이다.
• 이러한 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다.

❗️일상 생활에서 Stack의 실사용 예

• 프루팁스 사탕 통을 예로 들 수 있다.
• 사탕 통을 자료구조 Stack, 사탕을 데이터(data)로 비유할 수 있다.
• 가장 먼저 들어간 사탕은 가장 나중에 나올 수 있다.
• 다시 말해, 가장 나중에 들어간 사탕이 가장 먼저 나올 수 있다.

❗️컴퓨터에서 Stack의 실사용 예

• 함수 호출 및 반환 관리: 컴퓨터 프로그램에서 함수의 호출 스택을 관리하는 데 사용됩니다.
• 역순 문자열 생성: 문자열을 역순으로 바꾸는 데 유용합니다.
• 괄호 검사: 프로그래밍에서 괄호가 올바르게 닫혔는지 확인하는 데 사용됩니다.
• 재귀 알고리즘 처리: 재귀 호출을 처리할 때 내부적으로 스택을 사용합니다.
• 대표적으로 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 스택이 활용된다. 브라우저에서 자료구조 Stack이 사용될 때에는 다음과 같은 순서를 거친다.
  1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
  2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
  3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
  4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.
  

2. 스택 코드 구현

---

****2-1. 클래스로 구현

• 사용자 정의 데이터 타입으로 stack를 정의하면, new 키워드를 통해 인스턴스를 만들 수 있다.
• 그리고 생성한 인스턴스를 통해 다양한 메서드를 사용할 수 있다.

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

  // 요소를 스택에 추가
  push(element) {
    this.items.push(element);
  }

  // 스택에서 요소 제거 및 반환
  pop() {
    if (this.items.length === 0) {
      return "Underflow"; // 스택이 비었을 때
    }
    return this.items.pop();
  }

  // 스택의 맨 위 요소 확인
  peek() {
    return this.items[this.items.length - 1];
  }

  // 스택이 비었는지 확인
  isEmpty() {
    return this.items.length === 0;
  }
}

// 스택 사용 예
let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.peek()); // 2

// 문자열을 역순으로 바꾸는 함수
function reverseString(str) {
  let stack = new Stack();

  // 문자열의 각 문자를 스택에 삽입
  for (let i = 0; i < str.length; i++) {
    stack.push(str[i]);
  }

  let reverseStr = "";
  // 스택이 비어있지 않을 때까지 모든 요소를 꺼내서 새 문자열 생성
  while (!stack.isEmpty()) {
    reverseStr += stack.pop();
  }

  return reverseStr;
}

console.log(reverseString("Hello")); // olleH

2-2. 일반 배열로 구현

• Array를 사용하면 사용자 정의 데이터 타입을 구현하지 않고도 몇 가지의 메서드로 stack 처럼 동작하도록 사용할 수 있다.
• 자료구조로써 stack의 특성만 이해한다면, Array를 활용하여 stack로 사용할 수 있다.
• 자료구조는 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없다.

let stack = [];

// 요소 추가
stack.push(1);
stack.push(2);
stack.push(3);

// 요소 제거 및 출력
console.log(stack.pop()); // 3
console.log(stack.pop()); // 2

// 스택 출력
console.log(stack); // [1]