동적인 단일 연결 리스트 (Singly Linked List) - 스택

안녕하십니까~ 테슬라입니다
동적 단일 연결리스트의 응용이라 생각 할 수 있는 스택과 큐를 알아보도록 하겠습니다~
음 오늘은 우선 스택을 알아보도록 할게요.
그렇다면 우선 스택이란 무엇일까요?

스택이란 여러 개의 물건들이 쌓여있는 것을 말합니다.
예를 들어 어릴 때 가지고 놀던 블록을 위로 차곡차곡 쌓듯이 쌓는 것 말이지요.
제가 여기서 말하고자 하는 스택은 비슷한 개념이라 할 수 있지요.
컴퓨터의 자료구조에서 나오는 개념으로
스택에 저장된 데이터 항목 중에서 나중에 삽입된 것이 먼저 삭제(출력)되지요.
우리들이 식당의 배식판을 생각해보면 맨 위에 쌓인 것이 가장 마지막에 쌓였겠죠?
하지만 일반적으로 배식판들은 맨 위에서부터 사용되어가지요.
이처럼 나중에 삽입되고 먼저 삭제(출력)되므로 후입선출이라고도 불리우지요.

음 다시 돌아와서 그렇다면 어떻게 연결 리스트로 구현할까요?
아래의 그림을 봐주세요~

왼쪽이 단일 연결리스트로 표현한 Push입니다. 회색은 입력 되어있던 값이고,
흰색 노드와 검은 화살표가 새로 Push된 값의 노드와 연결입니다
오른쪽은 왼쪽의 연결을 개념적으로 나타낸 스택입니다.
원래 top이 가리키던 주소를 새로 생성한 노드 뒤에 연결하고 새로 생긴 노드의 주소를 top에게 줍니다.


Pop은

이번에도 역시 회색은 입력 되어있던 값이고,
흰색 노드와 검은 화살표가 Pop에 의해 변경된 노드와 연결입니다.
top를 다음 노드에 넘겨주고 맨 앞의 노드와의 연결을 free()와 같은 방식으로 제거합니다.

코드로 나타내본다면,
NODE *push(NODE *p,int num) { NODE *temp; temp=(NODE *)malloc(sizeof(NODE)); if(temp==NULL) exit(0); temp->data=num; temp->next=p; return (temp); } NODE *pop(NODE *p) { NODE *temp; if(p != NULL){ printf("Pop된 값 : %d\n",p->data); temp=p; p = p->next; free(temp); } else printf("Pop 할 데이터가 없습니다.\n"); return p; }
이런식으로 생각해볼 수 있겠지요?

그럼 단일 연결 리스트로 구현한 스택의 장점은 무엇일까요?
우선 배열을 생각해보지요.
Push할 경우 배열의 위치를 가리키는 값을 하나 증가시켜 다음 위치에 값을 저장하고,
Pop할 경우 위치를 가리키는 값을 하나 낮추어 그 전의 입력된 값의 위치를 가리키지요.
이러한 배열은 선언한 범위 내에서만 사용할 수 있기 때문에,
배열의 크기에 따라 적게 선언한다면 사용 할 시 부족하거나
 크게 선언 한다면 메모리가 낭비 되겠지요?

링크드 리스트로 구현한다면 어떨까요?
Push할 때 동적 메모리 할당을 하여 필요한 만큼만 사용하고,
Pop할 때에도 메모리를 free해주므로  메모리를 효율적으로 사용할 수 있지요.

음 오늘의 포스팅은 여기까지 입니다.
자 그럼 다음 시간엔 단일 연결 리스트를 이용한 큐에 대해 써보도록 하겠습니다.