Stack

1. 개요

후입선출(後入先出, Last In First Out; LIFO) 의 자료구조로, 상자의 형태를 한 자료구조이다. 데이터의 삽입을 Push, 데이터의 출력을 Pop이라고 하며, 스택을 크게 두 가지로 나누면
Ascending Stack VS Descending Stack으로 나눌 수 있다.

stack_img_1

스택은 배열과 링크드 리스트로 구현할 수 있는데, 여기서는 링크드리스트를 이용한 스택을 구현해 보겠다.

2. 코드 구현

2-1. define structure

typedef struct _stacknode Snode;
struct _stacknode {
    DataType data;
    Snode *next;
};
typedef struct _stack {
    Snode *head;
    Snode *tail;
    Snode *cur;
}Stack;

스택관리구조체 Stack은 링크드리스트 구조체처럼 head와 tail을 고정적으로 가리키는 노드포인터와 현재 노드를 가리키는 cur 포인터로 이루어져있다.

2-2. Init Stack

void initStack(Stack *sPtr) {
    sPtr->head = (Snode *)malloc(sizeof(Snode)); //헤드 노드 생성
    assert(sPtr->head!=NULL);
    sPtr->tail = (Snode *)malloc(sizeof(Snode)); //테일 노드 생성
    assert(sPtr->tail!=NULL);
    /*헤드노드가 테일노드를, 테일노드가 헤드노드를 가리키게 함*/
    sPtr->head->next=sPtr->tail;
    sPtr->tail->next=sPtr->tail;
    sPtr->cur = NULL;
    return ;
}

헤드노드와 테일노드를 메모리 할당해주고 서로 가리키게 해준다

2-3. Push

/* stack에 데이터 저장하기 */
int push(Stack *sPtr, DataType inData) {
    sPtr->cur = (Snode *)malloc(sizeof(Snode)); //새로운 노드 생성
    // 메모리 할당 실패하면 push실패
    if(sPtr->cur==NULL) {
        return FALSE;
    }
    //노드를 헤드노드 바로 뒤에 노드 추가
    sPtr->cur->next=sPtr->head->next;
    sPtr->head->next=sPtr->cur;
    sPtr->cur->data = inData; //데이터 복사
    return TRUE;
}

전달인자로 스택구조체의 주소와 삽입할 데이터를 받는다.
새 노드를 할당하기위해 메모리를 할당하고 위로 쌓이는 것이므로 (처음 삽입하는경우) 헤드노드 바로 뒤에 노드를 추가해주는데, 두 번째 삽입부터는 노드가 이미 하나있기때문에 그 노드의 뒤로 삽입을 해야한다. 따라서, 새로 할당받은 노드의 다음주소에 그 이전 노드를 가리키게 하고 이전 노드는 새로 할당받은 노드를 가리키게 한다.

2-4. Pop

int pop(Stack *sPtr, DataType *popData) {
    // stack이 비어있으면 pop실패
    if(sPtr->head->next == sPtr->tail) {
        return FALSE;
    }
    *popData = sPtr->head->next->data;
    sPtr->cur = sPtr->head->next;
    sPtr->head->next = sPtr->head->next->next;
    free(sPtr->cur);
    return TRUE;
}

제일 위에있는게 먼저 나가야하므로 popData에 가장 위에있는 노드의 data를 넣어주고, 제일 위에 있는 노드에 이어져 있는 선을 끊어주고 다음 노드와 이어주게 한다. 그리고 메모리를 해제

1. 개요#

2. 코드 구현#

2-1. define structure#

2-2. Init Stack#

2-3. Push#

2-4. Pop#