연결 리스트 기반 스택(List Base Stack) 개념

[ 이 게시물은 개념 설명 게시물이고 소스코드는 다음 게시물에 있습니다. ]

연결 리스트를 이용한 스택을 만드는 과정인데 아래의 그림을 참조하면 조금 더 쉽게 이해할 수 있다.

 

void SPush(Stack *pstack, Data data) // 스택 노드에 값을 추가
{
    Node *newNode = (Node*)malloc(sizeof(Node)); // 노드에 공간을 형성해준다.
 
    newNode->data = data; // 새로 생긴 노드의 data부분에 data값을 넣어주고
    newNode->next = pstack->head; // 새로 생긴 노드의 next부분은 head가 가리키고 있던 노드를 가리킴
 
    pstack->head = newNode; // head는 새로 생긴 노드를 가리키게 한다.
}
 
 

이 SPush의 과정이 위의 그림과 같은데

새로생긴 노드는 뒤로 붙는것이 연결 리스트 기반 스택이다. (즉 h -> 1이었는데 2가 추가되고 2 -> 1 에서 h -> 2 -> 1 이런식으로 진행된다.)

그림에서 빠진것이 있다면 처음 생성된 노드의 next는 NULL을 가리킨다.

리스트 기반 스택 소스코드를 보면 처음 head는 NULL을 가리키고, SPush에서 newnode의 next가 pstack->head

 즉 NULL을 가리키니 첫 노드의 next는 NULL을 가리킨다.

코드를 보면 SPop과정은 SPush과정의 역순으로 진행된다고 볼 수 있다.