Common Programming/C
간단한 Linked List를 사용한 Stack
WebDev
2013. 10. 23. 03:15
오늘은 Linked List를 사용한 Stack을 구현해 보도록 하겠습니다.
Stack의 기능을 보여주는 역할이기 때문에 코딩은 막 코딩인 점 양해해 주시기 바랍니다.
|
#include <stdio.h>
#include <stdlib.h>
typedef struct _Data
{
int value;
struct _Data *next;
} Data;
Data *head;
Data *tail;
void init_linkedlist(void);
void push(int);
void pop(void);
void print_list(void);
int main()
{
int returnVal;
init_linkedlist();
push(3);
push(4);
push(7);
push(10);
print_list();
pop();
pop();
pop();
pop();
pop();
return 0;
}
void init_linkedlist(void)
{
head = (Data *) malloc(sizeof(Data));
tail = (Data *) malloc(sizeof(Data));
head -> next = tail;
tail -> next = tail;
}
void push(int inputValue)
{
Data *newData;
newData = (Data *) malloc(sizeof(Data));
newData -> value = inputValue;
newData -> next = head -> next;
head -> next = newData;
}
void print_list(void)
{
Data *printData;
int printValue;
printData = head -> next;
while (1)
{
printValue = printData -> value;
if (printData == tail)
{
printf("The Print is over.\n");
break;
}
else
{
printData = printData -> next;
printf("%d is print value.\n", printValue);
}
}
}
void pop(void)
{
Data *nextData;
int returnVal;
if (head -> next == tail)
{
printf("This Linked List is empty\n");
exit(0);
}
nextData = head -> next;
returnVal = nextData -> value;
printf("returnVal is %d\n", returnVal);
head -> next = nextData -> next;
free(nextData);
printf("%d is popup.\n", returnVal);
} |
위의 프로그램은 LIFO 방식인 stack의 역할을 Linked List를 사용하여 구현한 내용입니다.
위의 그림과 같이 4개의 숫자가 논리적으로 Stack에 저장되어 지며 실제로는 Linked List로 구현되어있음을 확인할 수 있습니다.
실행 결과는 다음과 같습니다.
위와 같이 10 7 4 3 순서대로 Stack에 Value가 들어 있음을 확인할 수 있습니다.
pop up은 stack의 LIFO 특성상 늦게 들어온 value가 가장 빨리 나가므로 10 -> 7 -> 4 -> 3의 순서로 출력 됨을 확인 할 수 있습니다.