Stack : 스택
이번에 배울 자료구조는 스택이다.
스택을 이해하기 위해서 기억해야 할 가장 큰 특징은 바로
LIFO (Last In First Out) 이다. (first in last out이라고도 하지만 글쎄.. 하나만 기억해두는게 더 깔끔하다.)
무슨말이냐 하면, 마지막으로 들어온 것이 먼저 나간다는 것이다.
다음 그림을 봐보자.
출처 [네이버 지식백과] 스택 [stack] (컴퓨터인터넷IT용어대사전, 2011. 1. 20., 일진사)
그림을 보면 아래쪽에 네모난 통이 있다.
이것이 Stack이다.
데이터를 저장하는 바구니라고 생각하면 된다.
보통 바구니에 무엇을 넣게 되면, 먼저 넣은것은 아래로, 나중에 넣은것은 위에 있게 된다.
그럼 바구니에서 어떤 것을 꺼내게 될 때에, 마지막에 넣은것이 위에 있기 때문에 마지막의 것을 가장 먼저 꺼내게 된다.
이것이 Stack의 개념이다.
Stack에서는 데이터를 집어 넣는 것을 Push, 꺼내는 것을 Pop이라고 한다.
다만 주의하여야 할 점은, pop은 stack에서 데이터를 꺼내는 일이기 때문에 꺼낸 후에는 stack에 존재하지 않게 된다.
따라서 스택에서 꺼내지 않고 내용만 보고 싶을 경우는 Peek 함수를 사용한다.
기본적으로 스택을 구현하기 위한 함수는 다음과 같다.
집어넣기 위한 Push
꺼내기 위한 Pop
사이즈를 확인하기 위한 Size (혹은 size를 stack 구조체에서 유지하여도 무관하다.)
꺼내지 않고 데이터를 확인하기 위한 Peek(가장 위의 노드를 복사해온다. 혹은 Top이라고도 한다.)
이정도만 구현한다면 스택에 대해 대부분 이해했다고 볼 수 있겠다 !
다음시간에 직접 구현해봅시다!