[자료구조] Stack

스택이란?

스택은 선형구조를 가진 자료구조로 한 쪽 끝에서만 자료를 넣거나 빼는 후입 선출(Last-in First-out)의 형태로 동작합니다.

스택은 기본적으로 다음과 같은 연산을 합니다.

push

push 연산을 하면 스택에 지정한 데이터를 맨 끝에 넣습니다.

pop

pop 연산을 하면 스택에 맨 끝에 있는 데이터를 가져오고 스택에서 제거합니다.

peek

peek 연산을 하면 스택에 맨 끝에 있는 데이터를 가져옵니다.

스택의 활용

스택은 이전 상태로 되돌리는 경우에서 많이 사용됩니다.

예를 들어, 터미널에서 이전에 사용했던 명령들을 확인하고 사용할 수 있는 히스토리 기능이나 브라우저에서 이전 페이지로 되돌아가고 싶을 때 사용됩니다.

 

스택의 구현 (C)

스택은 배열 또는 링크드 리스트로 구현이 가능합니다.

 

- 배열리스트를 이용한 구현

https://github.com/zxcv9203/dataStructure/tree/master/chap03/arraystack

GitHub - zxcv9203/dataStructure

배열 리스트를 이용해서 스택을 구현은 다음과 같은 방식으로 구현하였습니다.

• 배열을 원하는 크기만큼 동적할당 한후 현재 인덱스 가르키는 변수를 0으로 초기화합니다.
• 값을 Push 할때는 데이터를 현재 인덱스 위치에 값을 넣고 인덱스를 1증가 시킵니다.
• 값을 Pop 할때는 현재 인덱스 위치의 데이터를 반환하고 인덱스를 1 감소 시킵니다.
• 값을 peek 할때는 현재 인덱스 위치에 데이터를 반환합니다.

- 링크드 리스트를 이용한 구현

https://github.com/zxcv9203/dataStructure/tree/master/chap03/linkedstack

GitHub - zxcv9203/dataStructure

• 값을 Push 할때는 넣고 싶은 데이터와 가장 최근에 추가했던 노드를 가르키는 포인터를 가진 노드를 동적할당하고 헤더노드가 해당 노드를 가르키도록 하게 합니다.
• 값을 pop할때는 가장 최근에 추가한 노드가 가르키고 있는 주소를 헤더노드가 가르키게하고 가장 최근에 추가했던 노드를 반환해줍니다.
• 값을 peek할때는 가장 최근에 추가한 노드를 반환해줍니다.

스택 문제 (미로 찾기)

스택을 활용하면 미로에서 빠져나오는 길을 찾을 수 있습니다. 

https://github.com/zxcv9203/dataStructure/tree/master/chap03/findmaze

GitHub - zxcv9203/dataStructure

스택에다 데이터를 넣고 4방향으로 탐색하면서 스택에 경로를 추가하고 인접한 경로가 막혀있을 경우 스택에 넣어두었던 데이터를 pop하여 제거하는 방식으로 구현하였습니다.