스택

스택의 이해

---

스택의 개념과 구조

---

스택 자료구조는 지층이 쌓이듯 데이터를 차곡 쌓아올린 형태로 자료를 구성합니다.

예를 들어 프링글스처럼 통안에 들어있는 감자칩과 비슷한 개념이라고 볼 수 있습니다.

 

스택은 정해진 방향으로 데이터가 입력되고 top은 새로 입력된 데이터를 가리키게 새로 갱신됩니다. 따라서 top은 항상 가장 마지막에 들어온 데이터를 가리키게 됩니다.

스택은 top으로 정한 곳에서만 삽입과 삭제가 이루어지기 때문에 가장 마지막에 들어온 데이터가 가장 먼저 삭제된다는 후힙선출(Last-In-First-Out) 동작 구조를 가집니다.

스택의 동작 방식은 위에 사진과 같습니다.

push를 실행하면 top 위치에 데이터가 들어가고 top은 1이 증가하게 됩니다. pop의 경우에는 top 위치 데이터를 삭제하고 top을 1 감소 시킵니다.

 

스택의 추상 자료형

// 스택이 공백인지 확인
isEmpty();

// 스택이 가득찼는지 확인
isFull();

// 스택에 삽입
push(data);

// 스택에 삭제
pop();

 

push() 알고리즘

push(data) {
    if(isFull) // 스택이 가득찼으므로 데이터가 들어갈 수 없음
        return ERROR(overflow);
    else
        stack[top++] = data;
}

일단 스택에 데이터를 넣기 전에 스택이 가득찼는지 isFull을 사용해서 확인합니다. 만약 가득찼다면 스택에 데이터를 삽입하는 행동을 멈추게 됩니다. 그렇지 않고 아직 스택이 널널하다면 stack에 데이터를 삽입하고 top을 1 증가 시킵니다.

 

pop() 알고리즘

pop() {
    if(isEmpty) // 스택이 비었기 때문에 더 이상 데이터를 뺄 수 없다.
        return ERROR(underflow);
    else
        return stack(top--);
}

일단 데이터를 삭제하기 전에 스택에 데이터가 비었는지 확인 합니다. 만약 데이터가 없다면 삭제 행동을 하지 않고 에러를 리턴합니다. 그렇지 않으면 스택에 값을 빼고 top을 1 감소 시킵니다.

 

 

스택의 구현

---

 

깃허브(순차자료구조와연결자료구조구현)

DataStructure/STACK at main · hosunghyun/DataStructure