C:DataStructure- 스택(stack)

자료 구조 모형의 첫 단계, 스택에 대해

스택-> 창고에 쌓여 있는 상자로 비유됨 = 후입선출, LIFO 방식(last in first out) = 가장 최근에 들어온 게 제일 위에 쌓이고 제일 먼저 나감

ADT//

가장 위에 있는 애를 가리키는 변수 top, 크기 MAX_STACK_SIZE
주의)top = -1일 때 스택이 비어있다는 의미. 만약 top이 0이면 하나의 스택이 쌓여있다는 것(index 값에 연관 지어 생각)

is_empty = 스택 비어있는지(if top == -1, true)
is_full = 스택 꽉 차있는지(if top >= MAX_STACK_SIZE -1, true)
push = 넣기(top++)
pop = 빼기(top--, 무조건 가장 위에 있는 애가 빠짐)
peek = (제일 위에 있는 애를 엿보는 것)

push(a);
b = pop();//이때, b에 들어가게 되는 스택은 a임.

전역 변수로 구현-> 매개변수로 top, 배열값 등을 보내줄 필요 없음
(스택에 저장하는 데이터 타입-> typedef 이용해 정의)
전역 변수로 각각 선언 시, 여러 개의 스택을 사용하기 어려움-> top, 배열 등 스택 요소들을 구조체로 묶어서 선언하기도(StackType)

#malloc, realloc 동적 메모리 할당.
realloc의 경우, 동적 메모리 크기를 변경할 수 있음(현 내용은 유지하고 메모리를 다시 할당하는 방식. 배열 크기는 2배씩 늘어남)

스택 연산 시간 복잡도 O(1)->

(작성중)