[자료구조] C - 스택, Stack, array stack, linkedlist stack

스택은 후입선출 방식으로 저장하는 방법 입니다.

(LIFO : Last In, First Out)

이 데이터를 Task라고 생각을 한다면,

좋은 예로 안드로이드 어플리케이션으로 들 수가 있습니다.

핸드폰에서 작업내용을 보면 가장 최신으로 실행한 어플이 앞에 나오죠?

액티비티를 실행시켜도 가장 마지막에 누른 버튼으로 부르는 액티비티를 볼 수 있습니다.  

이를보면 가장 마지막에 실행한 액티비티, 어플리케이션부터 실행을 하는 방법을 스택이라고 합니다.

프로그래밍을 하다보면 task 관리에서 가장 자주 마주치는 자료구조라고 생각하시면 됩니다.

아래의 그림을 보시면 좀 더 이해하기 쉬울 것 같습니다.

푸시는 데이터를 스택에 넣는 작업을 의미하고,

팝은 스택에서 데이터를 꺼내는 작업을 의미합니다.

스택에서는 위의 그림처럼 푸시로 아무리 많은 데이터를 쌓아두어도

팝을 할때는 제일 마지막에 들어온 데이터가 먼저 추출되게 됩니다.

왜 그러냐고 묻는건 마치 왜 글씨를 왼쪽부터 오른쪽 방향으로 쓰냐고 묻는 것이니 이런게 스택이다 라고 알아두시면 됩니다.

자 그럼 이걸 어떻게 구현하는가?

두가지 방법이 있어요  배열과 링크드리스트! 링크드 리스트는 C로 만드는 모든 자료구조에 적용이 가능하니 잘 이해해두시면 좋습니다.

1.배열 방법

배열 스택애서는 자연스러워요 누구나 이해하기 쉬운 구조 입니다.

위에 있었던 그림을 옆으로 뉘였다고 생각하면 쉽겠습니다.

푸시를 하게되면 가장 뒤쪽에 데이터를 추가하게 되고

팝을 하면 가장 마지막에 있던 데이터를 가져오면 되겠습니다.

위에 보시면 화살표가 있는데 이 화살표의 위치를 따로 저장해 두어야 참조하면서 쓸 수 있는 점 기억해두세요

배열 코드

https://github.com/geusan/datastructure/blob/master/c_language/02_1_array_stack.c

2. 링크드 리스트 방법

링크드 리스트 스택은 배열보다 더쉬워요

따로 화살표를 저장해둘 필요도 없구요

푸시를 하면 맨마지막 노드 찾아서 뒤에 새로 만들어주고

팝을 하면 가장 먼저 있던 노드를 삭제하고 뒤의 노드를 제일 먼저 참조할 수 있도록 하면 됩니다.

스택은 링크드 리스트가 더 쉬운 것 같습니다.

링크드 리스트 코드

https://github.com/geusan/datastructure/blob/master/c_language/02_2_linkedlist_stack.c

자료구조를 공부하는데에 있어서 배열 또는 링크드 리스트를 사용하는 기교를 더 익히기 보다는 이런식의 저장과 추출을 하는 형태가 스택이라는 개념적인 이해가 더 중요합니다. 물론 이걸 실현시켜주는 것에는 기교가 필요하겠지만, 자료구조를 이해한다면 확실히 이런 식의 프로그래밍은 이렇게 짜야겠다는 감이 좀 잡혀서 진짜 중요합니다. 기교는 나중에라도 익힐 수 있으니 이런 구조를 이해하는 것에 우선순위를 두면 좋겠습니다.