Chap06. 연결 리스트 기반 스택

연결 리스트를 기반으로한 스택은 단순히 저장된 순서의 역순으로 조회,삭제가 가능한 연결리스트 일 뿐이다. 

즉 새로운 노드를 꼬리가 아닌 머리에 추가하는 방식의 연결리스트라고 볼 수 있다. 

이렇게 머리에 새 노드를 추가하는 연결리스트에서 push, pop 등의 스택의 연산이 포함된 추상 자료형을 갖는다면 그것이 스택이라고 볼 수 있다. 

 

연결 리스트 기반의 스택에서는 데이터의 추가가 head에서 이뤄지므로, 포인터 변수 head는 항상 새로 추가된 노드를 가르키도록 해야한다.

 

ListBaseStack.h

/*
 * 연결 리스트 기반 스택
 */

#ifndef CHAP06_LISTBASESTACK_LISTBASESTACK_H
#define CHAP06_LISTBASESTACK_LISTBASESTACK_H

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node *next; // 연결 리스트 기반
} Node;

typedef struct _listStack
{
    // head는 항상 스택의 톱을 가르킴. 즉 새로 추가된 노드 가르킴
    Node *head;
} ListStack;

typedef ListStack Stack;

void StackInit(Stack *pstack);
int SIsEmpty(Stack *pstack);

void SPush(Stack *pstack, Data data);
Data SPop(Stack *pstack);
Data SPeek(Stack *pstack);


#endif //CHAP06_LISTBASESTACK_LISTBASESTACK_H

ListBaseStack.c

#include "ListBaseStack.h"
#include <stdio.h>
#include <stdlib.h>

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

int SIsEmpty(Stack *pstack)
{
    if(pstack->head == NULL) return TRUE;
    return FALSE;
}

void SPush(Stack *pstack, Data data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));

    newNode->data = data;
    // 새로운 노드는 head가 가르키고 있던 노드를 가르키도록 한다
    newNode->next = pstack->head;

    // head는 항상 새로 삽입된 노드를 가르켜야 한다
    pstack->head = newNode;
}

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

    if(SIsEmpty(pstack))
    {
        printf("Stack Memory Error");
        exit(-1);
    }
    // 가장 위에 있는 데이터를 지움
    rdata = pstack->head->data;
    rnode = pstack->head;

    pstack->head = pstack->head->next;
    free(rnode);

    return rdata;
}

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

 

---

문제 06-1 [연결 리스트를 이용한 스택의 또 다른 구현]

원형 연결 리스트를 구현한 CLinkedList.h와 CLinkedList.c 를 변경 없이 이용해 스택을 구현 

 

CLinkedListBaseStack.h

/*
 * 원형 연결 리스트 기반 스택
 */

#ifndef CLINKEDLISTBASESTACK_CLINKEDLISTBASESTACK_H
#define CLINKEDLISTBASESTACK_CLINKEDLISTBASESTACK_H

#include "CLinkedList.h"

typedef struct _cListStack
{
    // 원형 연결 리스트 기반
    List *plist;
} CListStack;

typedef CListStack Stack;

void StackInit(Stack *pstack);
int SIsEmpty(Stack *pstack);

void SPush(Stack *pstack, Data data);
Data SPop(Stack *pstack);
Data SPeek(Stack *pstack);


#endif //CLINKEDLISTBASESTACK_CLINKEDLISTBASESTACK_H

CLinkedListBaseStack.c

#include <stdio.h>
#include <stdlib.h>
#include "CLinkedListBaseStack.h"

// 원형 연결 리스트를 초기화
void StackInit(Stack *pstack)
{
    pstack->plist = (List*)malloc(sizeof(List));
    ListInit(pstack->plist);
}

int SIsEmpty(Stack *pstack)
{
    if(LCount(pstack->plist) == 0) return TRUE;
    else return FALSE;
}

void SPush(Stack *pstack, Data data)
{
    // head에 노드 추가
    LInsertFront(pstack->plist, data);
}

Data SPop(Stack *pstack)
{
    Data data;
    // stack의 pop은 head의 노드가 나와야되므로
    LFirst(pstack->plist, &data);
    LRemove(pstack->plist);
    return data;
}

Data SPeek(Stack *pstack)
{
    Data data;
    LFirst(pstack->plist, &data);
    return data;
}

CLinkedListBaseStackMain.c

#include <stdio.h>
#include "CLinkedListBaseStack.h"

int main()
{
    Stack stack;
    StackInit(&stack);
    
    // data input
    SPush(&stack, 1);
    SPush(&stack, 2);
    SPush(&stack, 3);
    SPush(&stack, 4);

    // data pop
    while(!SIsEmpty(&stack))
        printf("%d ", SPop(&stack));
}

 

이미 만들어진 자료구조를 이용해 또 다른 자료구조를 구현하는 것도 필요하다.