stack에 대하여 알아보기
참조: 참조 블로그
스택이란
스택은 컴퓨터에서 아주 많이 사용되는 자료구조입니다. 예를 들어, 스마트폰 “뒤로 가기” 키를 눌렀을 때 현재 수행되는 앱이 종료되고 바로 직전에 수행되던 앱이 다시 나타나곤 하는데요, 이때 사용되는 것이 스택입니다. 스택(stack)은 말 그대로 ‘쌓아놓은 더미’를 뜻합니다. 식당에 쌓여있는 접시 더미, 책상에 쌓인 책, 겹겹이 쌓인 상자 모두 스택의 예에 해당합니다. 이 중에서도 가장 대표적인 예시로 ‘프링글스(Pringles)’를 들 수 있겠습니다.
후입선출(LIFO)
스택의 가장 큰 특징은 후입선출(‘LIFO’) 입니다. 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미인데요, 이는 과자 프링글스를 생각하면 쉽습니다. 젤 나중에 넣은 칩 조각을 가장 먼저 먹게 되는 것과 같은 이치죠. 이는 먼저 들어온 데이터가 먼저 나가는 ‘큐(Queue)’ 와의 가장 큰 차이점 이라고도 할 수 있습니다.
스택의 구조&사용
스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 아주 요긴하게 사용되는 자료구조입니다. 문서 편집기에서 ‘되돌리기(undo)’ 기능을 구현하면 바로 직전(최근)에 실행했던 작업이 취소되곤 하지 않나요? 그때 바로 이 스택 자료구조를 사용합니다.
- 상단(stack top) : 스택에서 입출력이 이루어지는 부분
- 하단(stack bottom): 반대쪽 바닥 부분
- 요소(element): 스택에 저장되는 것
- 공백 스택(empty stack): 공백 상태의 스택
- 포화 스택(full stack): 포화 상태의 스택 (풀스택!)
시스템 스택(Stack) 함수호출
- 복귀주소 기억
함수의 실행이 끝나면 자신을 호출한 함수로 되돌아갑니다. 이 때 스택은 복귀할 주소를 기억하는 데 사용됩니다. 함수는 호출된 역순으로 되돌아가야 하기 때문입니다.</br> 출처: https://roi-data.com/entry/자료구조-4-스택Stack이란-연산-구현방법 [데이터 드리븐 마케팅 Blog:티스토리]
- 활성 레코드
: 시스템 스택에는 함수가 호출될 때마다 활성 레코드(activation record)가 만들어지며, 이곳에 복귀 주소가 저장됩니다. 활성 레코드에 생성되는 정보는 아래와 같습니다. - 복귀 주소 - 프로그램 카운터 - 매개변수 - 함수 안에서 선언된 지역변수 시스템 스택에는 아래 그림과 같은 순서로 활성 레코드가 만들어졌다가 없어지게 됩니다.
스택의 정적/동적 구현
- 스택생성
- top : 가장 최근에 입력되었던 자료를 가리키는 변수
- stack[0] … stack[top] : 먼저 들어온 순으로 저장
- 공백 상태: top = -1 </br>출처: https://roi-data.com/entry/자료구조-4-스택Stack이란-연산-구현방법 [데이터 드리븐 마케팅 Blog:티스토리]
// 1차원 배열의 사용
# define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
/* top의 초기 값은 스택이 비어있을 때 -1 이다. */
int top = -1;
- 스택의 삽입
void push(int item)
{
if (top >= MAX_STACK_SIZE - 1) {
stack_full();
return;
}
stack[++top] = item;
// top ++; stack[top] = item;
}
// push(x)
if is_full(S)
then error "overflow"
else top <- top + 1
data[top] <- x
3. 스택의 삭제
int pop() {
if (top == -1)
return stack_empty();
// int x; x = stack[top]; top--; return x;
return stack[top--];
}
// pop()
if is_empty()
then error "underflow"
else e <- data[top]
top <- top-1
return e
- 스택의 검사
// 스택이 비어있는지 검사하는 함수
int isempty()
{ if (top < 0)
return(1);
else
return(0);
}
// 스택이 가득 차 있는지 검사하는 함수
int isfull()
{ if (top >= MAX_STACK_SIZE -1 )
return(1);
else
return(0);
}