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

문제 : 원형 연결리스트를 이용해서 스택을 구현해보자.

// CLInkedList. h

#include <stdio.h>

#include <stdlib.h>

typedef struct _node

{

int data;

struct _node * next;

}Node;

typedef struct _list

{

Node * head;

Node * tail;

Node * before;

Node * cur;

int numOfdata;

}List;

void InitList(List * plist)

{

plist->tail = NULL;

plist->numOfdata = 0;

}

void LInsert(List * plist, int data)

{

Node * newnode = (Node*)malloc(sizeof(Node));

newnode->data = data;

if (plist->tail == NULL)

{

plist->tail = newnode;

newnode->next = newnode;

}

else

{

newnode->next = plist->tail->next;

plist->tail->next = newnode;

plist->tail = newnode;

}

(plist->numOfdata)++;

}

void LInsertFront(List * plist, int data)

{

Node * newnode = (Node*)malloc(sizeof(Node));

newnode->data = data;

if (plist->tail == NULL)

{

plist->tail = newnode;

newnode->next = newnode;

}

else

{

newnode->next = plist->tail->next;

plist->tail->next = newnode;

}

(plist->numOfdata)++;

}

int LFirst(List * plist, int * data)

{

if (plist->tail == NULL)

return 0;

plist->cur = plist->tail->next;

plist->before = plist->tail;

*data = plist->cur->data;

return 1;

}

int LNext(List * plist, int * data)

{

if (plist->tail == NULL)

return 0;

plist->before = plist->cur;

plist->cur = plist->cur->next;

*data = plist->cur->data;

return 1;

}

int LRemove(List * plist)

{

Node * rpos = plist->cur;

int temp = plist->cur->data;

if (rpos == plist->tail)

{

if (plist->tail == plist->tail->next)

plist->tail = NULL;

else

plist->tail = plist->before;

}

plist->before->next = plist->cur->next;

plist->cur = plist->before;

free(rpos);

(plist->numOfdata)--;

return temp;

}

int LCount(List * plist)

{

return plist->numOfdata;

}

// CLLBaseStack.h

#include <stdio.h>

#include <stdlib.h>

#include "CLinkedList.h"

typedef struct _listtack

{

List * plist;

}Stack;

void StackInit(Stack * pstack)

{

pstack->plist = (List*)malloc(sizeof(List));

InitList(pstack->plist);

}

int SIsEmpty(Stack * pstack)

{

if (LCount(pstack->plist) == 0)

return 1;

else

return 0;

}

void SPush(Stack * pstack, int data)

{

LInsertFront(pstack->plist, data);

}

int SPop(Stack * pstack)

{

int data;

LFirst(pstack->plist, &data);

LRemove(pstack->plist);

return data;

}

int SPeek(Stack * pstack)

{

int data;

LFirst(pstack->plist, &data);

return data;

}

// Main. c

#include <stdio.h>

#include "CLLBaseStack.h"

int main()

{

Stack stack;

StackInit(&stack);

SPush(&stack, 1);

SPush(&stack, 2);

SPush(&stack, 3);   // 1 2 3 순으로 들어갔음으로 FILO인 스택은 3 2 1  순으로 나와야함

while (!SIsEmpty(&stack))

printf("%d", SPop(&stack));

return 0;

}