스택(Stack)

문제6) 스택(Stack)의 개념을 설명하고, 아래의 조건을 만족하는 스택의 작동 알고리즘을 작성하시오.

K : 스택의 크기

Top : 스택 포인터

S : 스택의 이름

 

가. 스택(S)의 스택 포인터(Top)를 1 증가시킨다. 스택 포인터가 스택의 크기(K)보다 크면 Overflow 처리

한다. 그렇지 않으면 Item이 가지고 있는 값을 스택의 Top 위치에 삽입한다.

 

나. 스택 포인터가 0이면 스택의 바닥이며 더 이상 삭제할 자료가 없으므로 Underflow 처리한다.

그렇지 않으면 Top 위치에 있는 값을 Item으로 옮기고 스택 포인터를 1 감소시킨다.

 

답)

 

 

1. 후입선출(LIFO)형 자료구조, 스택(Stack)의 개념

가. 스택(Stack)의 정의 설명

개념도
정의	Top이라고하는 스택의 한쪽 끝에서만 자료의 삽입(Push)과 삭제(Pop)가 이루어지는 LIFO형 자료구조
스택의 자료 처리는 주요 연산을 통해 수행되며, 수식 계산등에 활용

 

나. 스택(Stack)의 주요 연산과 활용

연산과 활용	세부항목	상세설명
주요연산	Push()	Stack의 Top 증가 후 데이터 삽입
	Pop()	Stack의 Top 데이터 삭제 및 반환
	Overflow()	Stack이 Full 상태로, Push() 불가한 경우
	Underflow()	Stack이 Empty 상태로 , Pop() 불가한 경우
	Top	스택 최상위 포인터
활용	인터럽트 처리	문맥교환시 활용
	수익의 계산	산술식 계산
스택은 서브루틴의 복귀 번지 저장에도 활용하며, Push/Pop 연산을 통해 삽입/삭제 작동

 

2. 스택의 삽입을 주어진 조건으로 작동 알고리짐 작성

가. 삽입 연산을 위한 주어진 문제 설명

구분	설명
삽입(Push)연산
문제 설명	① 스택(S)의 스택 포인터(Top)를 1 증가시킨다 ② 스택포인터가 스택의 크기(K)보다 크면 Overflow 처리한다 ③ 그렇지 않으면 Item이 가지고 있는 값을 스택의 Top 위치에 삽입한다.
스택포인터 값에 따라 Overflow 와 삽입 연산이 발생함

 

나. 스택(Stack)의 삽입(Push) 작동 알고리즘 작성

작동 알고리즘 작성	알고리즘 설명
Push(Item) { Top = Top + 1; if(Top > K) { Overflow(); } else { S(Top) <- Item; } }	// 스택 포인터 (Top) 1 증가 // Top이 스택의 크기(K)보다 크면, // Overflow 처리 // 그렇지 않으면 , // Item값을 Top 위치에 삽입
스택의 삭제는 Pop 연산을 통해 동작함

 

 

3. 스택 삭제를 주어진 조건으로 작동 알고리즘 작성

가. 삭제 연산을 위한 주어진 문제 설명

구분	설명
삭제(Pop) 연산
문제설명	① 스택 포인터가 0이면 스택의 바닥이므로 , Underflow 처리 ② 그렇지 않으면 Top 위치에 있는 값을 Item 옮기고 , ③ 스택 포인터 1 감소시킴
스택포인터 값에 따라 Underflow와 삭제 연산이 발생함

 

나. 스택(Stack)의 삭제(Pop) 작동 알고리즘

작동 알고리즘 작성	알고리즘 설명
Pop() { if(Top == 0) { Underflow(); } else { Item <- S(Top); Top = Top - 1; } return Item; }	// 스택 포인터(Top)가 0 이면, // Underflow 처리 // 그렇지 않으면, // Top위치에 있는 값을 Item으로 옮기고 // Top을 1 감소 // Item 값을 리턴
스택의 삽입과 삭제 연산을 통해, 후위 표기식으로 계산을 수행

 

4. 스택(Stack)을 이용한 후위표기식 계산과정 사례 설명 (147x+)

피연산자는 Push, 연산자는 Pop 2회 수행한후 연산결과 Push하여 후위표기식 계산

 

---

 

공감과 댓글은 아이티신비에게 큰 힘이 됩니다.

블로그 글이 유용하다면 블로그를 구독해주세요.♥