본문 바로가기
IT/[Everyday]Coding

알고리즘을 공부하기 위한 기초 [ linear structure - Stack ]

by Jang HyunWoong 2014. 12. 19.

Linear Structure 

1. List

2. Stack

3. Queue

4. Deque

 

2. Stack

- An ordered list in which insertions and deletions are made at one end called the top

 (top 이라고 불리우는 한쪽 끝에서만 삽입과 삭제가 만들어지는 정리된 리스트)

- LIFO( Last In First Out ) 라고 불리운다. 마지막에 들어간 것이 첫번째로 나온다.

 



 

자료의 삽입 : TOP = TOP +1

자료의 삭제 : TOP = TOP -1

Overflow 발생 : 스택의 크기가 m 일때, TOP > m 이면 Overflow 발생한다.

 

스택의 사용분야

1. 인터럽트 처리

2. 수식의 계산 (산술식)

3. 서브루틴의 복귀번지 저장 

4. 서브 프로그램의 호출 (함수 호출의 순서 제어)

 

삽입 알고리즘


 

 

삭제 알고리즘

 

 

 

스택은 생각보다 많은 곳에 사용이 된다고 생각한다.

 

응용하여 이렇게 생각할 수 있다.

 

 

문제) [{()}] 대괄호, 중괄호, 소괄호가 랜덤으로 하나씩 들어오는데 그 순서가 맞는지 확인하기 위한 알고리즘은? 예를 들어 [[]{([])}] (O) [{}([}])] (X) 

 

스택을 사용하여 확인할 수 있다. 

 



반응형

'IT > [Everyday]Coding' 카테고리의 다른 글

트리 in C#  (0) 2014.12.19
큐 in C#  (0) 2014.12.19
스택 in C#  (0) 2014.12.19
알고리즘을 공부하기 위한 기초 [ 자료 구조 ]  (0) 2014.12.19
[C++] 클래스로 LIFO(스택) 구현하기  (0) 2014.12.19