[자료구조] 3. 스택

KNOU/자료구조

[자료구조] 3. 스택

워터파슬리 2022. 11. 5. 23:45

728x90

01. 스택의 개념과 추상 자료형

✅ 스택

객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형
- 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계를 표현(First In Last Out, LIFO)
0개 이상의 원소를 갖는 유한 순서 리스트
push(add)와 pop(delete)연산이 한곳에서 발생되는 자료구조

🔸스택의 추상자료형

스택 추상 자료형: 세 개의 연산(create, push, pop)만 해당 객체에 접근 가능하도록 제한하는 것
추상 자료형은 운영체제/컴파일러 개발자들이 만드는 것으로 소프트웨어/애플리케이션 개발자들이 다른 연산으로는 객체(데이터)에 접근할 수 없도록 막고, 이를 이용해서 OS나 프로그래밍언어가 효율적으로 작동하게 만듬

▪️ CreateS 연산

Stack CreateS(maxStackSize) ::= 스택의 크키가 maxStackSize인 빈 스택을 생성하고 반환;

▪️ Push 연산

Element Push(stack, item) ::= if( isFull(stack) ) then{ 'stackFull' 출력; }else{ 스택의 가장 위에 item을 삽입하고 스택 반환; }

▪️ Pop 연산

Element Pop(stack) ::= if( IsEmpty(stack) ) then{ 'stackEmpty' 출력; }else{ 스택의 가장 위에 있는 원소를 삭제하고 반환; }

🔸Pop/Push 연산 실행

ⓡ CreateS(3);
② Push(stack, 'S');
③ Push(stack, 'T');
④ Pop('T');
⑤ Push(stack, 'R');
⑥ Push(stack, 'P');
⑦ Push(stack, 'Q');
⑧ Pop(stack);

top: 현재 스택에서 제일 위에 있는 값만을 가리키는 변수로 top을 이용해서만 스택에 접근할 수 있음

02. 스택의 응용과 구현

🔸스택의 다양한 응용

변수에 대한 메모리의 할당과 수집을 위한 시스템 스택
서브루틴 호출 관리를 위한 스택
- 예) main 함수에서 A 함수를 호출하고 A함수에서 B함수를 호출할 경우, B함수 실행 종료 후 돌아가야할 위치, A함수 실행 종료 후 돌아가야할 위치를 저장하는데 스택이 사용됨
연산자들 간의 우선순위에 의해 계산 순서가 결정되는 수식 계산
인터럽트의 처리와 이후 리턴할 명령 수행 지점을 저장하기 위한 스택
컴파일러, 순환 호출(재귀호출) 관리

🔸스택의 삭제 연산

int a = 5;
int b = a--; //b = 5, a = 4

int a = 5;
int b = --a; //b = 4, a = 4

top--에서 사용된 '--' 연산자의 위치에 따라 연산의 적용 순서가 달라질 수 있음

🔸스택의 구현

▪️ 스택의 생성

#define STACK_SIZE 10
typedef int element;
element stack[STACK_SIZE];
int top = -1;

▪️ 스택의 삭제 연산

element pop(){
	if(top == -1){
            printf("Stack is Empty!\n")
            return 0;
    }else{
    	return stack[top--]; //리턴 후, 삭제
    }
}

▪️ 스택의 삽입 연산

void push(element item){ //스택의 삽입 연산, item=400
	if(top >= STACK_SIZE-1){
            printf("Stack is Full!\n");
            return;
    }eles{
    	stack[++top] = item;
    }
}