스택(Stack)
가장 최근에 보관한 자료를 먼저 꺼내는 LIFO(Last In First Out)방식의 자료 구조이다.
리스트의 한쪽으로 삽입과 삭제 연산을 수행한다.
스택의 특징
가장 최근에 자료를 보관한 위치를 기억하며 Top이라 부른다.
자료를 보관하는 연산을 Push라고 부른다.
자료를 꺼내는 연산을 Pop이라 부른다.
Push 연산
IF Top>= MAX Then //꽉 차면
Overflow //버퍼 오버플로우
Else //꽉 차지 않을 때
Top = Top +1 //Top 위치를 1 증가
Buffer[Top] = data //버퍼의 Top 위치에 data 보관
Pop 연산
IF Top=0 Then //비었으면
Underflow //버퍼 언더플로우
Else
data = Buffer[Top] //버퍼의 Top 위치의 값을 데이터에 설정
Top = Top -1 //Top 위치를 1 감소
스택을 사용하는 분야
함수 호출 순서의 제어
인터럽트 처리
수식 계산
재귀적인 문제를 동적 프로그래밍 방식으로 해결
큐(Queue)
가장 먼저 보관한 자료를 먼저 꺼내는 FIFO(First In First Out) 방식의 자료구조
한쪽으로 보관하고 다른 쪽에서 꺼냄
큐의 특징
가장 먼저 보관한 자료의 위치를 기억하며 Front라 부른다.
자료를 보관할 위치를 기억하며 Rear라고 부른다.
큐에 자료를 보관하는 연산을 Put 혹은 Enqueue라 부른다.
큐에 자료를 꺼내는 연산을 Get 혹은 Dequeue라 부른다.
큐를 사용하는 분야
스케쥴러
대기 순서에 따라 처리하는 연산
데크(Deque)
맨 앞이나 뒤로 자료를 저장하거나 꺼낼 수 있는 자료구조
입력을 한쪽에서만 가능하게 제한한 데크를 Scroll이라 부른다.
출력을 한쪽에서만 가능하게 제한한 데크를 Shelf라고 부른다.