스택

스택 개념

제일 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조.

• LIFO(후입선출): 먼저 들어간 것이 마지막에 나오는 규칙
• push: 스택에 삽입하는 연산
• pop: 스택에서 꺼내는 연산

스택의 정의

스택의 ADT

ADT: 추상자료형. 인터페이스는 존재하나 실제로 구현은 되지 앟는 자료형. 일종의 자료형의 설계도.

스택에 필요한 정의

연산
1. push: 스택에 데이터를 푸시
2. pop: 스택에서 데이터를 팝 하고 데이터를 반환
3. isFull: 스택에 들어있는 데이터 갯수가 가득차있는지 가득찼다면 true 아니면 false
4. isEmpty: 스텍애 데이터가 하나라도 들어있는지 들어있다면 false 없다면 true

상태
5. top: 스택에서 최근에 푸시한 데이터의 위치를 기록
6. data: 스택의 데이터를 관리하는 배열

스택 세부 동작

데이터를 추가 시

1. push() 호출
2. 내부적으로 isFull()을 수행해 data 배열에 데이터가 가득찼는지 확인
3. 가득 차 있지 않을 경우 top 을 1만큼 증가
4. top이 가르키는 위치 data[0]에 추가

데이터를 제거 시

1. pop() 호출
2. 내부적으로 isEmpty()을 수행해 data 배열에 데이터가 존재하는지 확인
3. 데이터가 존재 할 경우 top 을 1만큼 감소
4. 데이터를 반환

스택 구현하기

스택의ADT

const stack = []; // 스택 초기화
const maxSize = 10; // 스택의최대 크기

function isFull(stack) {
  // 스택이 가득 찼는지 확인하는 함수
  return stack.length == maxSize;
}

function isEmpty(stack) {
  // 스택이 비어 있는지 확인하는 함수
  return stack.length === 0;
}

function push(stack, item) {
  // 스택에 데이터를 추가하는 함수
  if (isFull(stack)) {
    console.log("스택이 가득 찼습니다.");
  } else {
    stack.push(item);
    console.log("데이터가 추가되었습니다.");
  }
}
function pop(stack) {
  // 스택에서 데이터를 꺼내는 함수
  if (isEmpty(stack)) {
    console.log("스택이 비어 있습니다.");
    return null;
  } else {
    return stack.pop;
  }
}

위 코드와 같으나 실제로 코드를 구현 할 경우 maxsize, isFull() 는 사용하지 않거나, isEmpty() 함수는 stack.length === 0 같이 검사하기 때문에. 많이 풀어보아 감을 익히는 것이 권장됨