스택 - 구현

📌 스택에 필요한 추상자료형

puch : 데이터 삽입
pop : 데이터 제거
peek : 데이터 참조
isEmpty : 비었는지 체크

이 네개의 기능을 연결리스트를 이용해서 구현해보자.

[파일구조]

[stack.mjs]

// 이전에 만든 연결리스트 import
import { LinkedList } from "../LnkedList/LinkedList.mjs";

// stack class 생성
class Stack {
  // 생성자를 만들어 스택이 초기화할 때 빈 리스트 생성
  constructor() {
    this.list = new LinkedList();
  }

  // 📌 push()
  // push() 함수는 연결리스트의 head에 삽입하는데
  // 이는 연결리스트의 insertAt() 함수로 indexO에 데이터를 삽입한다.
  push(data) {
    this.list.insertAt(0, data);
  }

  // 📌 pop()
  // 연결리스트의 head에서 꺼내면 되기 때문에
  // deleteAt() 함수로 index O를 제거하면 된다.
  pop() {
    // 제거된 노드는 return 으로 반환
    // 예외가 발생하면 nulld을 return
    // return을 try로 감싸주고 에러를 캐치하면 null return
    try {
      return this.list.deleteAt(0);
    } catch (e) {
      return null;
    }
  }

  // 📌 peek()
  // 스택의 top에 있는 데이터를 참조만 하고 데이터를 제거하지 않는다.
  // 연결리스트의 getNodeAt() 함수로 첫 번째 데이터를 읽어오고 리턴
  peek() {
    return this.list.getNodeAt(0);
  }

  // 📌 isEmpty()
  // 스택이 비었으면 true, 비어있지 않으면 false 리턴
  // 이는 연결리스트의 count 0와 비교하면 알 수 있다.
  isEmpty() {
    return this.list.count == 0;
  }
}
export { Stack };

• 연결리스트를 이미 구현해놨기 때문에 간단하게 구현할 수 있었다.

[test_stack.mjs]

// stack import
import { Stack } from "../Stack/stack.mjs";

// Stack 인스턴스화
let stack = new Stack();

console.log("=== 첫 번째 출력 ===");
// 스택에 데이터 네 번 push
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4); // 4가 스택의 맨 꼭대기

// pop을 통해 4부터 출력되는지 확인해보자.
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);

// peek() 함수와 isEmpty() 함수의 테스트 코드 작성
console.log("=== 두 번째 출력 ===");
// 현재 스택은 비어있기 때문에 네 번 삽입
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
// peek()함수로 top에 있는 데이터 확인
// peek()함수로 호출했더라도 스택에서는 데이터는 제거되지 않는다.
console.log(stack.peek().data);

// top에 있던 4를 pop()함수로 제거
stack.pop();
// 다시 peek()함수로 3이 출력되는지 확인
console.log(stack.peek().data);

// 이제 isEmpty() 함수로 스택이 비었는지 확인
// 1부터 3까지 세 개의 노드가 있기 때문에 false가 출력된다.
console.log(`isEmpty: ${stack.isEmpty()}`);

//pop() 함수를 세 번 호출해서 스택을 비워준다.
stack.pop();
stack.pop();
stack.pop();

// 다시 isEmpty() 함수로 스택이 비었는지 확인
console.log(`isEmpty: ${stack.isEmpty()}`);
// pop() 함수로 데이터를 전부 제거했기 때문에 true 출력

// 빈 스택을 pop 해보기
// 이는 pop()함수의 예외처리가 잘 됐는지 확인하기 위한 것
// 빈 스택을 pop하면 에러가 아니라 null이 출력
console.log(stack.pop());

• 결과 확인! 굿!
  

with 그림으로 쉽게 배우는 자료구조와 알고리즘