---------------------------------------------------
이제부터는
연결리스트를 사용하여
배열의 한계를 극복한
연결리스트 스택을 살펴보겠습니다.
우선 처음엔 전역변수 형태로 만듭니다.
---------------------------------------------------
연결리스트 스택은
일단 노드 포인터가 주를 이루는데
처음에는 쉽게
이것의 형태가 전역변수입니다.
---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
이전에 썼던 노드 구조체와 동일합니다.
---------------------------------------------------
그다음 전역변수 형태의
노드 포인터가 존재합니다.
int top 대신에
노드의 주소를 담는
노드 포인터 스택탑을 만들고 null 포인터를 저장했습니다.
그 다음 del 포인터는 삭제할때
그 다음 p_node 포인터는 출력할때
그 다음 s_node 포인터는 탐색할때
사용합니다.
---------------------------------------------------
두번째는
마찬가지로
기능을 선택하는 선택지를 만들어 줍니다.
---------------------------------------------------
푸쉬
팝
프린트 노드
서치 노드
4가지 기능을 만들어 줍니다.
---------------------------------------------------
그래서 일단 이런식으로
선택문을 만들어 줍니다.
---------------------------------------------------
선택이 1일때
push 하고 데이터 입력
선택이 2일때
pop
선택이 3일때
전체 노드 출력
선택이 4일때
서치노드하고
데이터 입력
---------------------------------------------------
다음으로 푸시함수 구현에 대해서 살펴보면
---------------------------------------------------
일단 푸쉬함수의 함수 프로토타입인데
전역변수를 사용하기 때문에 간단합니다.
반환형 보이드 이고
입력은 정수 데이터 하나만 해도 됩니다.
---------------------------------------------------
push 동영상
---------------------------------------------------
첫번째 추가는
생성된 노드의 주소를 전달해주기만 하면 끝이지만
두번째 추가부터는
단순히 새로 생성된 노드를 가리키기만 하면 이전 노드와의 연결이 끊어지게 됩니다.
그러므로
새로 생성된 노드의 링크가
이전 노드를 가리키고
top은 새로생성된 노드를 가리키게 하는
두가지 과정이 필요합니다.
그러면 비로소
노드끼리도 연결이 되고
노드 포인터 탑은 제일 최근에 생성된 노드를 가리키게 됩니다.
---------------------------------------------------
그래서 최종 완성된 소스는 다음과 같습니다.
---------------------------------------------------
그래서 최종 완성된 소스는 다음과 같습니다.
push함수는
우선 메모리 동적할당을 사용하여
힙영역에 메모리 할당하고
노드 포인터에 주소를 전달합니다.
---------------------------------------------------
그 다음 데이터에 값을 넣고
다음 노드의 주소가 들어갈 넥스트엔 널 포인터를 넣습니다.
---------------------------------------------------
푸쉬 함수는 첫번째 추가와 두번째 추가가 다르기 때문에
If~else로 두 가지 경우를 구분해줍니다.
---------------------------------------------------
stack_top 포인터가 널일땐
가리키는 노드가 없다는 뜻이고
첫번째 노드 추가인 상황을 말합니다.
그때는
최상위 노드를 가리키는 스택탑 포인터에 노드의 주소만 전달해주면 됩니다.
---------------------------------------------------
stack_top 포인터가 널이 아닐땐
이미 추가된 노드가 있다는 뜻이고
두번째 이후부터 노드 추가 상황이 됩니다.
두번째 이후부터는
새로 생성된 노드가 이전 노드를 가리키고
스택탑 포인터는 최상위 노드를 가리키도록 하는
두가지 과정이 필요합니다.
---------------------------------------------------
즉,
생성한 노드의 넥스트에 이전 노드의 주소를 가진 스택탑을 주고
스택탑은 새로 생성된 노드를 가리키도록 합니다.
이 두가지 과정을 그림으로 표현하면 다음과 같습니다.
---------------------------------------------------
첫번째 노드의 주소를
탑 포인터에 넘겨주어 가리키도록 합니다.
이렇게 첫번째 추가는 매우 쉽습니다.
탑 포인터에 주소만 넘겨주면 끝입니다.
---------------------------------------------------
그 다음 두번째 추가부터 조금 복잡한데
두번째
노드를 생성하고
---------------------------------------------------
이전 노드에 연결시켜줍니다.
---------------------------------------------------
그 다음 탑 포인터를
새로운 노드를 가리키도록 합니다.
즉, 탑 포인터에 새로운 노드의 주소를 줍니다.
---------------------------------------------------
---------------------------------------------------
팝함수도
반환형은 보이드이고
입력은 없어도 됩니다.
전역변수를 쓰기 때문에 형태가 간단합니다.
---------------------------------------------------
pop 동영상
---------------------------------------------------
팝함수의 완성된 소스는 다음과 같습니다.
---------------------------------------------------
우선 스택탑이 널일땐
제거할 노드가 없는 것이므로
캔트팝을 출력하여
팝할수 없다는 것을 말해줍니다.
---------------------------------------------------
그 다음
스택 탑이 널이 아니라면
제거할 노드가 있는 것입니다.
---------------------------------------------------
그러므로
Del포인터가 스택탑 값을 넣어
최상위 노드를 가리키도록 합니다.
---------------------------------------------------
그 다음
제거할 노드의 데이터를 출력해줍니다.
---------------------------------------------------
그 다음
스택 탑에
스택탑 넥스트를 저장하여
다음 노드로 옮겨갑니다.
---------------------------------------------------
---------------------------------------------------
이것도
마찬가지로
보이드 이고 입력은 없습니다.
---------------------------------------------------
print_node 동영상
---------------------------------------------------
프린트 노드의 완성된 소스는 다음과 같습니다.
---------------------------------------------------
피노드에 스택탑값을 넣어
최상위 노드를 가리키게 한다음
---------------------------------------------------
피노드가 널이 아닌동안
진행합니다.
---------------------------------------------------
피노드가 가리키는 데이터를 출력해주고
---------------------------------------------------
피노드를 아래로 이동시킵니다.
---------------------------------------------------
---------------------------------------------------
반환형은 보이드 이고
입력은 탐색할 데이터만 주면 됩니다.
---------------------------------------------------
search_node 동영상
---------------------------------------------------
노드를 탐색하는
서치 노드 함수는 다음과 같습니다.
---------------------------------------------------
에스 노드는
최상위 노드를 가리키고
---------------------------------------------------
에스 노드가
널이 아닌 동안 탐색합니다.
---------------------------------------------------
일치하는 데이터가 발견되면
출력하고 return 하여 종료합니다.
---------------------------------------------------
만약 끝까지 찾지 못했을땐
while 반복문을 탈출하여
자연스럽게
찾지 못했다는 캔트 파인드가 출력 될 것입니다.
---------------------------------------------------
---------------------------------------------------
푸쉬 세번 했을때
이런식으로
밑에서부터
10,20,30이 쌓이게 될것입니다.
---------------------------------------------------
그 다음 서치노드를 해서
30을 찾으면
파인드 30이 출력되어
잘 검색이 되고
없는 데이터인 50을 찾으라고 했을 경우엔
찾지 못하고 캔트 파인트가 출력이 되는것을 알 수 있습니다.
---------------------------------------------------
그 다음 팝을 하게 되면
최상위 노드 부터 하나씩 제거가 됩니다.
그래서
팝 30
팝 20
팝 10
이렇게 정상적으로 출력이 되는것을 알 수 있습니다.