C언어 스택(Stacks in C) - 연결리스트로 구현(The implementation with the linked lists)

C언어 스택(Stacks in C) - 연결리스트로 구현(The implementation with the linked lists)

- 스택에 관한 내용은 이전 글 참고

1. 동작 원리

(1-1) push 명령 시 새로운 노드를 생성한 후 Top 포인터가 이를 가르키게 한다.

( Top 포인터는 항상 가장 최근 노드(가장 위)를 가르킨다. )

(1-2) 각 노드들은 자신의 이전 노드를 가르킨다.

( pop 명령 시 삭제되는 노드의 이전 노드를 가르키기 위함 )

(2-1) pop 명령 시 Top 포인터가 가르키고 있는 노드의 값을 반환하고, Top 포인터는 이전 노드를 가르킨다.

(2-2) 값을 반환한 노드는 삭제한다. ( 메모리를 반환한다. )

2. 함수 설명

int stack_empty( STACK *) : 스택이 비어있는지( 생성된 노드가 없는지) 확인한다.

void push( STACK **, int) : 스택에 새로운 노드를 추가하는 함수로 동작원리 (1)에 해당한다.

int pop( STACK **) : 스택에 있는 노드를 제거하는 함수로 동작원리 (2)에 해당한다.

3. 전체 소스 코드

 

 

#include <stdio.h> #include <malloc.h> #define MAX     10 typedef struct stack{     int data;     struct stack *pre; }STACK; int stack_empty( STACK *); void push( STACK **, int); int pop( STACK **); int main( void) {     STACK *TOP;     // initialize the top of the stack.     TOP = NULL;         push( &TOP, 10);     push( &TOP, 30);     push( &TOP, 20);     pop( &TOP);     pop( &TOP);     pop( &TOP);     pop( &TOP);     push( &TOP, 50);     push( &TOP, 40);     pop( &TOP);     pop( &TOP);     pop( &TOP); } /*     stack_empty( STACK)     this function examine whether the stack is empty. */ int stack_empty( STACK *s) {     if( s == NULL)     {         return 1;     }     return 0; } /*     push( STACK *, int)     insert a data into the stack and     the variable 'top' point the top of the stack. */ void push( STACK **s, int data) {     STACK *new_node = (STACK *)malloc(sizeof(STACK));         // initialize the new node     new_node->pre   = NULL;     new_node->data  = data;     printf("PUSH : %d\n", data);     if( *s == NULL)     {         *s  = new_node;         return;     }     // new node point the previous node that pointed the top pointer.     new_node->pre   = *s;     // update the top pointer.     *s              = new_node; } /*     pop( STACK *)     get a data from the stack and     remove the data in the stack. */ int pop( STACK **s) {     STACK *temp = *s;     int data;     if( stack_empty( temp))     {         printf("The stack is empty!\n");         return -1;     }     // back up the data that holding the node.     data    = temp->data;     // update the top pointer.     *s      = temp->pre;     free(temp);     printf("POP : %d\n", data);     return data; }

 

 

4. 실행 결과