사실 자료구조를 수강한지는 한 학기, 스터디를 시작한지는 2개월이 지났지만 여태까지 배운 것들에 대한 정리를 하나도 안 하고 있었기 때문에 ... 지금부터라도 내가 했던 걸 조금씩 기록하려고 한다.
아무튼 자료구조 시간에 배웠던 Stack을 사용하는 문제들을 실제로 풀어보기 위해 Stack에 대한 것을 다시 복습해봤다.
Stack이란 제한적으로 접근할 수 있는 나열 구조이며, Last In, First Out 방식을 사용하기 때문에 '가장 끝 원소'에 대해서만 접근할 수 있다.
예를 들어 A라는 데이터가 있는 Stack이 존재했다고 가정해보자. B, C가 차례로 Stack에 들어온다면, 그 뒤 내가 직접적으로 접근할 수 있는 데이터(예를 들어 데이터를 삭제한다든가)는 C다. 나중에 들어온 데이터가 무조건 먼저 나가야 되는 Stack의 특성 때문이다.
Stack에서 사용되는 기본적인 ADT(추상 자료형)은
- push(a): a를 스택의 맨 위에 삽입한다.
- pop(): 스택의 맨 위에 있는 객체를 제거하고 반환한다.
- top(): 스택의 맨 위 객체를 제거하지 않고 반환한다.
- size(): 스택에 저장된 요소 개수를 정수로 반환한다.
- empty(): 스택이 비어 있는지 여부를 bool로 반환한다.
정도로 추릴 수 있겠다.
Stack이나 다음에 올릴 Queue 같은 경우에는 내용이야 워낙 간단하고 이걸 활용하는 문제가 어려우니, 문제 풀이 내용을 위주로 추가로 업로드할 예정이다.