●Stack
▷제한적으로 접근 가능한 나열구조, Last-in-first-out.
▶ADT
▷임의의 Object를 저장
▷삽입/삭제는 Last-in-first-out 규칙을 따름
▶주요 명령
▷void push(object): 데이터를 삽입.
▷object pop(): 마지막에 넣은(최상위) 데이터를 삭제함. 삭제한 데이터를 반환함.
▶보조 명령
▷object top(): 마지막에 넣은 데이터를 반환함. (pop()과 다르게 삭제하지 않음)
▷int size(): 저장된 원소의 개수를 반환함.
▷bool empty(): 저장된 원소가 없으면 true 반환.
▶Exception
▷StackEmpty: 빈 Stack의 요소에 접근하려 할 때. (top, pop)
▷Stackfull: Array기반의 Stack에서 Array에 더이상 데이터를 넣을 수 없을 때.
▶활용
▷직접: 웹 브라우저, 텍스트 에디터의 뒤로가기/취소, C++의 Chain method call
▷간접: algorithm의 보조 데이터 구조, 다른 데이터 구조의 일부.
▷C++ Stack Interface (c++ STL class의 Stack과 다름)
○Array-based Stack
▷배열을 이용해 Stack 구현 (왼쪽(0)부터 오른쪽(n)으로 데이터를 채워나간다.)
▷왼쪽(0)부터 오른쪽(n)으로 데이터를 채워나간다.
▷최대 크기가 정해져있고, 가장 오른쪽의 데이터를 지정하는 index를 저장하는 변수가 필요.
▶성능 (n-Stack의 요소 개수)
▷공간복잡도 : O(n)
▷각 연산의 시간복잡도 : O(1)
▶한계
▷Maximum Size가 존재하며, 이를 바꿀 수 없음.
▷가득찬 Stack에 데이터를 넣으면 StackFull Exception이 발생함.
▶코드
○Linked List-based Stack
▷(Singly) Linked List를 이용해 Stack을 구현.
▷Linked List의 특성에 따라 최대 크기의 제한이 없음.
▶코드(노드)
▶코드(Linked-List)
▶코드(Stack)
