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

이번에는 앞서 구현했던 원형 연결 리스트를 바탕으로 스택을 구현해 봅니다. 아래에 제시되는 CLinkedList.h 파일과 CLinkedList.c 파일을 변경하지 않고 그저 활용만 해서 스택을 구현하는 것이 문제입니다.

//CLinkedList.h 헤더 파일로 저장
#ifndef C_LINKEDLIST_H
#define C_LINKEDLIST_H

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct Node
{
	Data data;
	struct Node* next;
} Node;

typedef struct
{
	Node* tail;
	Node* cur;
	Node* before;
	int numOfData;
}CList;

typedef CList List;

void ListInit(List* plist);
void LInsert(List* plist, Data data);         //꼬리에 노드 추가
void LInsertFront(List* plist, Data data);    //머리에 노드 추가
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);

#endif

//CLinkedList.c 소스 파일로 저장
#include "CLinkedList.h"
#include <stdio.h>
#include <stdlib.h>

void ListInit(List* plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}
void LInsert(List* plist, Data data)         //꼬리에 노드 추가
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}
	newNode->data = data;

	if (plist->tail == NULL)
	{
		plist->tail = newNode;
		newNode->next = plist->tail;
	}
	else
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;    //유일한 차이점
	}
	
	plist->numOfData++;
}
void LInsertFront(List* plist, Data data)    //머리에 노드 추가
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다.\n");
		exit(1);
	}
	newNode->data = data;

	if (plist->tail == NULL)
	{
		plist->tail = newNode;
		newNode->next = plist->tail;
	}
	else
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
	}

	plist->numOfData++;
}
int LFirst(List* plist, Data* pdata)
{
	if (plist->tail == NULL) return FALSE;

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

	*pdata = plist->cur->data;
	return TRUE;
}
int LNext(List* plist, Data* pdata)
{
	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}
Data LRemove(List* plist)
{
	Node* delNode = plist->cur;
	Data delData = delNode->data;

	if (plist->tail == plist->cur)
	{
		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(delNode);
	plist->numOfData--;

	return delData;
}
int LCount(List* plist)
{
	return plist->numOfData;
}

---

제가 작성한 코드는 아래의 '더보기'를 클릭하여 확인할 수 있습니다.

혹시 이해가 가지 않거나 추가 설명이 필요하다면 언제든지 물어보길 바랍니다.

CLinkedList.h 파일과 CLinkedList.c 파일은 앞서 소개가 되었으므로 main.c 파일과 실행결과만 보이겠습니다.

//main.c 소스 파일로 저장
#include "CLickedList.h"
#include <stdio.h>

int main(void)
{
	List list;
	int data;
	ListInit(&list);

	//데이터 넣기
	LInsertFront(&list, 1);
	LInsertFront(&list, 2);
	LInsertFront(&list, 3);
	LInsertFront(&list, 4);
	LInsertFront(&list, 5);

	//데이터 꺼내기
	while (LFirst(&list, &data))
	{
		printf("%d ", data);
		LRemove(&list);
	}

	return 0;
}

/*
실행결과

5 4 3 2 1

*/