2. Stack #1 ADT && structure

6-1 스택의 이해와 ADT 정의

1) 스택의 이해

• “ 후입선출”
•  

책에 나온 돈돈초콜릿 난 첨봤음

 

프루팁스 통 안에서 섞이지 않는다는 전제 하에 이렇게 젤리를 넣었다고 가정하자

1→ 2→ 3→ 4

그렇다면 마지막에 넣은 것부터 꺼내야 할 것이다

4 → 3 → 2 → 1

이렇게 마지막에 넣은 녀석부터 꺼내서 쓰는 자료구조가 Stack이다.

 

 

2) ADT 정의

• void StackInit(Stack* pstack);
  • 기능 : 초기화
  • 특징 : 스택 생성 후 가장 먼저 호출
• int SIsEmpty(Stack* pstack);
  • 기능 : empty → 1, filled → 0
• void SPush(Stack* pstack, Data data)
  • 기능 : 스택에 데이터 저장
• Data SPop(Stack* pstack)
  • 기능 : 마지막 저장된 요소 삭제+반환 (LRemove와 유사함)
• Data SPeek(Stack* pstack)
  • 기능 : 마지막에 저장된 요소 반환

 

6-3 Stack based on Linked List

1) Linked List

앞에서 했던 arr 기반 스택은 적지 않겠다. 하지만, 여기서 제시했던 스택의 구조 모양을 연결리스트 기반 구현에서도 사용하면 좋을 거 같아 그림은 가져오려고 한다.

이렇게 화살표 방향이 아래를 향해있는 연결 리스트를 작성하면 Stack을 구현할 수 있다.

 

2) Stack Reset, count

(1) Reset

void StackInit(Stack *pstack)
{
    pstack->head = NULL;  
}

stack 안에는 head 노드 포인터밖에 존재하지 않기 때문에 초기화해줄 때는 이 포인터를 NULL에 세팅해주기만 하면 된다

(2) count

int IsEmpty(Stack *pstack)
{
    if (pstack->head == NULL)  // 스택이 비면 head에 NULL저장
        return TRUE;
    else
        return FALSE;
}

1. pstack->head == NULL : head포인터가 NULL을 가리키고 있는 경우에는, 스택이 비어있는 상황밖에 없다. 비어있는 경우 → true를 보낸다
2. is~~인 값은 → 결국 if문의 조건문으로 넣어서 사용할 수 있다.

 

3) Stack Insert, Delete

(1) Insert

void SPush(Stack *pstack, Data data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));  
    newNode->data = data;  //1. 

    newNode->next = pstack->head;                 
    pstack->head = newNode;                      
}

1. newNode : 새로운 노드 만들어서 data를 값 안에 넣어두기
2. new→next = head : newNode의 화살표가, 현재 head 가 가리키고 있는 가장 외각의 요소를 가리키도록 하기
3. head = newNode : head가 방금 생긴 새로운 최외각 노드인 head를 가리키도록 하기

따라서 호출할 때 대상이 되는 스택 리스트와, 삽입해야 할 데이터를 함께 호출하면 된다.

(2) Delete

Data SPop(Stack *pstack)
{
    Data rdata;
    Node *rnode;

    if (IsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }

    rdata = pstack->head->data;    
    rnode = pstack->head;             // 1. 

    pstack->head = pstack->head->next; // head가 다음 노드를 가리킴
    free(rnode);                      // 노드 삭제
    return rdata;                     // 삭제 데이터 반환
}

1. rdata, rnode : 삭제할 데이터와(=head→data) 노드를(=head) 임시로 저장한다
2. head = head→next : head가 기존에 가리키던 것 아래 있는 노드( 한 칸 안에 있는)를 가리키도록

사실 스택에서 데이터를 삭제했다는 것은 그냥 head 가 가리키는 데이터가 한 칸 밀린 것만으로 생각해도 된다.

근데 생각해보면 그냥 next로 타고 가면 중간에 있는 데이터를 삭제할 수도 있을 거 같은데, 문제는 before처럼 포인터 노드가 여러 개 있는 것도 아니고, 다시 끝으로 돌아올 수가 없기 때문에 중간 조회 시도를 안하는 것 같다.

4) Stack Check

SPop의 반환값을 사용하면 최외곽에 있는 데이터를 조회할 수 있지만, 조회할 때 마다 노드가 사라진다는 불상사를 겪을 수 있다. 그렇기 때문에 단순히 조회만 하는 함수도 만들어보자

Data SPeek(Stack *pstack)
{
    if (IsEmpty(pstack)) {
        printf("Stack Memory Error!");
        exit(-1);
    }
    return pstack->head->data;  
}

1. pstack->head->data : 그냥 head가 가리키는 데이터를 반환하는 코드이다

 

 

6-2에서는 계산기 프로그램을 만들어보려고 한다. 그런데, 이 프로그램의 코드를 구현하려면 ‘후위 표기법’과 이 원리를 파악하고 있어야 하기 때문에, 글이 길어질 것 같아 뒷부분은 다른 글에 적어보려고 한다.