TIL - 스택

 

 

First In Last Out (FILO) - 먼저 들어간 데이터가 나중에 나오는 규칙

 

 

스택은 아주 단순한 규칙을 가진 리스트이다. 

 

 

설거지를 하고 접시를 쌓고 있다. 

가장 먼저 세제를 묻힌 접시는 가장 아래 쌓이고 제일 나중에 세제를 묻힌 접시는 가장 맨 위에 올려진다. 

이제 세척을 하자. 쌓인 접시를 사용할 때는 위에 있는 접시 먼저 꺼낸다. 

 

이렇게 먼저 들어온 게 나중에 쓰이는 데이터 구조를 스택이라고 부른다. 

 

일상생활에서도 자료구조를 많이 볼 수 있다. 

엘리베이터의 상황에서 먼저 기다리고 있는 사람은 먼저 들어가고 늦게 도착한 사람은 문 앞에 서게 된다. 

내릴 때는 반대이다. 늦게 도착한 사람이 먼저 내리고 가장 먼저 기다린 사람은 제일 늦게 내린다.

 

스택은 먼저 들어온 게 나중에 나오는 조건만 충족한다면 어떤 자료구조로 구현하던지 상관이 없다. 

 

배열과 연결리스트로 각각 스택을 구현할 수 있다. 

이전에 만들었던 연결리스트는 head 하나로 모든 노드를 연결했었는데, 

헤드를 이용하면 스택을 간단하게 만들 수 있다. 데이터 삽입을 무조건 첫번째 인덱스에 하는 것이다. 

 

데이터 삽입을 무조건 첫 번째 인덱스에 하는 것이다. 

마찬가지로 데이터 제거도 무조건 첫 번째 인덱스에 하는 것이다. 

 

정수 1 ,2, 3, 4를 첫번째 

차례대로 3과 4를 삽입하면 4가 가장 앞에 위치하게 된다.

이제 이 데이터를 제거할 때 head에 있는 노드를 먼저 제거한다. 

 

가장 앞 부분은 4가 된다. 이후로 3 - 2 - 1 이 된다.

 

한쪽으로만 데이터를 삽입, 제거하면 간단하게 스택이 된다.

 

차례가 중요할 때는 스택은 정말 쓸모없는 자료구조이다. 

하지만 스택이 딱 어울리는 상황이 있다. 

ex) 포토샵.

그림을 그리다가 실수할 경우 ctrl + z로 되돌린다. 

우리의 작업을 전부 스택에 기록하기 때문에 가장 최근에 들어온 작업을 버린다. 

자료구조 하나에 담기만 했는데 원하는 기능을 구현할 수 있게 된다.

 

스택을 모르고 있었다면 시행착오가 많았을 것이다. 

 

또다른 상황을 예시들면 

자바스크립트 코드를 작성하면 문법 에러가 없는지 검사를 한다. 

문법검사기는 여는 괄호를 만나면 스택에 넣고, 닫는 괄호를 만나면 스택에서 그와같은 종류의 여는 괄호인지 체크한다. 

{

  let a = ( 1 + 100);

}

 

첫번째로 { 여는 중괄호를 만났기때문에 스택에 넣어준다. 

그다음 ( 여는 소괄호가 등장해 스택에 넣는다. 

그 다음으로는 ) 닫는 소괄호가 등장한다. 닫는 괄호를 만났기 때문에 스택에서 데이터를 꺼내 이 데이터가 여는 데이터인지 확인한다. 

여는 소괄호가 맞기 때문에 통과 된다.

이제 마지막으로 닫는 중괄호가 나타난다. 그럼 스택에서 데이터를 꺼내 이 데이터가 여는 중괄호 인지 체크한다.  여는 중괄호 이기 때문에 통과가 된다. 

이제 더 이상 체크할 코드가 없고 스택도 비어있어서 문법에러가 발생하지 않았다고 판단한다.

만일 스택에 데이터가 남았거나 괄호의 짝이 맞지 않는다면 문법에 문제가 있기때문에 에러가 발생한다. 

 

스택의 특성을 잘 알고 적절한 상황에 써야할 줄 알아야 한다. 

 

스택을 구현해보자. 

 

스택의 추상자료형

 

push: 데이터 삽입

pop: 데이터 제거

peek: 데이터 참조(head)

isEmpty: 비어있는지 체크

 

//스택을 이전에 만들었던 연결리스트로 만들 예정
import { LinkedList } from "./LinkedList.mjs";

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

  //데이터를 삽입하는 함수
  push(data){
    this.list.insertAt(0, data)
  }

  // 데이터를 꺼내는 함수
  // pop은 연결리스트의 head에서 꺼내면 되기 때문에 index 0 을 제거하면 됨.
  pop(){
    try {
      return this.list.deleteAt(0) //제거된 노드는 반환해줌
    } catch (error) {
      return null;
    }
  }

  // 스택의 Top에있는 데이터를 참조만 하고 제거하지는 않음.
  peek(){
    return this.list.getNodeAt(0) //첫번째 노드를 읽어오고 탐색함
  }

  //스택이 비어있으면 true 비어있지 않으면 false
  isEmpty(){
    return (this.list.count == 0)
  }
}

export { Stack }

// 연결리스트를 구현할 때 빈 리스트를 지우면 예외를 던지도록 했는데 예외가 발생하면 null을 리턴해주도록 함

 

 

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

let stack = new Stack()

console.log('============첫 번째 출력 =============')

stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
console.log(stack.pop().data)
console.log(stack.pop().data)
console.log(stack.pop().data)
console.log(stack.pop().data)


console.log('============두 번째 출력 =============')
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)

console.log('stack.peek(): ', stack.peek().data); //4
stack.pop() 
console.log('stack.peek(): ', stack.peek().data); //3

console.log('isEmpty: ', `${stack.isEmpty()}`);
stack.pop() 
stack.pop() 
stack.pop() 
console.log('isEmpty: ', `${stack.isEmpty()}`);
console.log(stack.pop()); //null