간단한 Linked List를 사용한 Stack

오늘은 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의 순서로 출력 됨을 확인 할 수 있습니다.