스택(Stack)이란
한 끝에서 삭제와 삽입이 이루어지는 순서 리스트를 뜻하며 삭제와 삽입이 이루어지는 부분을 TOP이라고 한다.
수식으로는 S = (a0, a1, ... an)으로 표현하며 오른쪽에 있을수록 윗쪽에 있는 원소로 표현되며 TOP이된다.
제일 나중에 들어온 원소가 제일 먼저 삭제되기 때문에 후입선출(Last In First Out)구조하고도 부른다.
Top Pointer에서 삭제는 POP 연산이라 하고, 삽입은 PUSH 연산이라고 표현한다.
삽입과 삭제 구조가 간단함으로 어떤 내용을 기억시켰다가 다시 신속히 사용할때 많이 사용되어 컴퓨터 알고리즘에 중요한 자료구조이다.
시스템 스택
운영체제에 기본적으로 구현된 스택을 시스템 스택이라고 부른다.
시스템 스택은 프로그램의 레지스터 크기와 일치하며 (32bit 컴터면 4byte 길이) 내부는 함수나 서브프로그램이 호출되어 호출된 지역변수와 매개변수, 함수 수행 후 복귀할 주소들이 담겨져 있다.
함수 호출 시 프로그램은 함수에 대한 스택을 생성하고 함수를 실행한 뒤 복귀한 주소를 만들어 시스템 스택 Top에 PUSH를 한다.
만약에 해당 함수가 다른 함수를 호출하는 경우에는 필요한 지역 변수와 함께 새롭게 호출한 함수의 스택과 실행 후 복귀할 주소를 함께 생성하여 시스템 스택에 PUSH를 한다.
예)
함수가 실행될 때 : 함수 실행 - 함수스택 + 복귀 주소 생성 - 시스탬 스택에 저장.
내부에서 다른 함수를 실행 할 때 : 함수 스택 + 복귀 주소와 호출한 함수의 스택 + 복귀주소 + 지역변수 몽땅 시스탬 스택에 저장.
자기자신을 호출하는 순환 호출이라도 각 호출에 대한 스택을 따로 만들어 계속 쌓기 때문에 무한 반복되는 경우엔 메모리를 초과할 가능성이 있다.
스택 추상화
스택의 추상화 자료구조 표현은 일자원 배열 표현법을 사용하여 stack[N]으로 표현한다.
여기서 N은 스택이 허용할 수 있는 최대 엔트리 수이며 0부터 시작한다.
스택의 초기 상태는 빈 공간임으로 top pointer는 -1로 표현하며 공백 스택이라고 부른다.
POP, PUSH
스택의 삽입과 삭제는 스택의 크기가 제일 큰 고려사항이다 이를 위해선 가장 마지막 윈소의 위치를 나타내는 top pointer를 기준으로 여분 공간 크기를 파악한 후 연산 유무를 결정한다.
할당 공간이 가득차서 더이상의 원소 삽입이 불가능한 경우를 오버플로우라고 부른다.
삽입이 가능할 경우엔 top pointer를 증가 시킨 후 해당 위치에 원소를 저장한다.
삭제의 경우엔 top pointer의 원소를 삭제한 후 top pointer를 감소 시킨다.
스택의 원소가 하나도 없어서 삭제 연산이 불가능한 경우를 언더플로우라고 부른다.
삽입시엔 오버플로우검사, 삭제시엔 언더플로우 검사를 먼저 진행 후 해당 연산을 진행함.
적용 분야
순서대로 적재됨과 후위 선출의 특성을 살린 분야로
위에서 언급한 시스템 스택과 같은 복귀 주소를 저장하는 경우나
함수 순서 제어
중위 표기식을 후위 표기식으로 변환할때
후위 표기법의 산술식 연산
0-주소지정방식 명령어의 자료 저장소
재귀 프로그램 순서 제어
컴파일러 언어 번역 등에 사용된다.
큐(Queue)란?
출구와 입구가 하나인 스택과 달리 전용 출구와 전용 입구 모두를 보유한 순서 리스트를 의미한다.
가장 먼저 삽입된 원소가 가장 먼저 삭제됨으로 선입선출 (First In First Out)이라고 한다.
가장 최근에 삽입된 위치를 가르키는 포인트를 rear라고 부르며, 윈소중 가장 오래된 원소의 위치를 가르키는 포인트는 front라고 한다.
큐가 처음 생성되고 원소가 없는 초기 상태일땐 rear와 front 모두 -1로 표현하며, rear와 front가 동일한 경우는 공백, rear = n-1일 경우엔 가득찬 상태로 표현된다.
스택이 연산시 오버,언더 플로우를 검사했듯 큐또한 연산시 rear와 front의 값으로 오버,언더플로우 검사를 진행한다.
큐 삽입 과정은 rear가 n-1인지 확인하고 동일하면 가득찬 상태, 아니면 rear + 1를 하고 원소 저장을 하고, 큐 삭제는 front가 rear와 비교해 동일하면 공백 상태, 아니면 front + 1를 하고 원소를 삭제한다.
원형 큐
큐의 가장 보편적인 이용 방법으로 운영체제에 의한 작업 큐 관리 방식에 대표적으로 사용된다.
일반 선형 리스트일 경우엔 큐 삽입과 삭제를 반복하다보면 rear와 front값은 계속 증가하여 나중에는 큐의 내부는 공백이지만 주소값이 포화 상태가 되어 사용이 불가능한 경우가 발생한다.
이럴 경우에 전체 큐를 감소 시켜 공백만큼 rear와 front값을 줄여야 하는데 선형일 경우 시간이 많이 걸리지만 원형일 경우엔 공백을 초기화 하는데 큰 부담이 없어진다.
원형 큐에선 rear와 front값은 0이 초기값이며 front는 첫번째 원소보다 시계 반대 방향으로 하나 앞의 위치를 지정한다.
rear = front일 경우 공백이며 삽입 위치는 rear = (rear+1) mod n으로 결정되며 삭제 위치는 front = (front+1) mod n으로 한다.
mod 연산은 나누기를 한 뒤 나머지 값을 의미한다.
(선형과 원형 큐 상태 비교)
공백일 경우 둘다 rear == front
선형의 포화는 rear = n-1 (최근 삽입 위치가 한계 위치)
원형의 포화는 front = (rear+1) mod n (새로 삽입할 위치가 삭제 위치와 같음)
선형의 삽입 위치는 rear = rear + 1 (최근 삽입 위치 다음 위치)
원형의 삽입 위치는 rear = (rear+1) mod n (최근 삽입 위치 다음 위치)
선형의 삭제 위치는 front = front + 1 (최근 삭제 위치 다음 위치)
원형의 삭제 위치는 front = (front+1) mod n (최근 삭제 위치 다음 위치)
적용 분야
원형 큐를 활용한 끊이지 않는 구조의 장점과 선입 선출의 장점으로 반드시 순서대로 실행과 종료를 관리해야할 분야에서 많이 사용된다.
대표적인게 순서가 핵심인 작업 버퍼나 프로세스 스케줄링이다.
프로그램들이 프린터보단 작업 속도가 빠르니 프린터 작업을 프로그램들이 큐에 던져두면 프린터가 큐의 순서대로 작업하도록 하는 방식으로 사용되는 예.
데크(Deque)란?
원소의 삽입과 삭제가 양방향 모두 일어나는 리스트로 스택과 큐가 결합된 구조이다.
이름부터 Double Ended Queue로 스택과 큐의 장점을 취해 구성되었다고 한다.
데크는 양쪽에서 삽입 삭제 모두 이루어짐으로 큐와 같이 두개의 포인터를 가지는데 둘 다 삽입 삭제를 하다보니 관리에 어려움이 있어서 어느 한쪽에는 삽입이나 삭제 하나만 되도록 제한을 두는 제한 데크로 운영된다.
한쪽에 삽입 제한을 두어 삽입은 한 곳에서만 되도록 한 데크는 입력 제한 데크, 또는 스크롤이라고 부르며, 삭제 제한을 두어 한 곳에서만 삭제가 되는 데크는 출력 제한 데크, 또는 셀프라고 부른다.
스택을 통한 수식 계산법
연산자 우선순위를 기준으로 수식 표기법인 전위, 중위, 후위에 따른 계산법.
연산자의 우선순위는 연산의 순서를 결정하는 기준이며 일반적으로 C언어 기준을 따른다.
우선 순위는
1. 괄호 (), []
2. 단항식 ++,--
3. 승제 *, /
4. 가감 +,-
5. 시프트 <<,>>
6. 비교식 <,>
7. 등가 ==, !=
8. 비트 &,^,|
9. 논리 &&, ||
10. 조건 ?
11. 대입 +=, -=
12. 콤마 ,
로 나열되며 같은 우선 순위일 경우 왼쪽이 우선 순위를 가진다.
표기법은 연산자를 기준으로 표기 순서를 정하는 것으로 (A+B 를 기준으로)
전위 표기 : 연산자가 피연산자 앞. (+AB)
중위 표기 : 연산자가 피연산자 사이. (A+B)
후위 표기 : 연산자가 피연산자 위. (AB+)
로 표기하는 방식을 의미한다.
따라서 기존에 수식을 표기하던 표준 방식은 중위 표기를 따른것이다.
사람은 중위 표기법이 익숙하지만 컴파일러의 경우 효율이 떨어지기 때문에 컴파일러 기준으론 후위 표기법에 괄호를 사용하지 않는다.
후위 표기법으로 스택에 저장하면 피연산자를 차례로 저장하고 연산이 나오면 모두 합쳐 연산 하여 한 자리에 저장하는 과정을 반복하기 때문에 항상 top pointer를 유지하여 연산이 가능하다.
이를 위해 후위 연산법으로 변환 과정을 알아둬야 한다.
중위 -> 후위 표기법 변환 과정
0. 각 연산자별 우선순위에 따라 괄호 표시
1. 왼쪽 괄호 무시
2. 피연산자이면 바로 출력
3. 연산자면 스택에 삽입
4. 오른쪽 괄호가 나오면 스택에서 연산자 출력
5. 출력된 값이 없을 경우 스택이 공백이 될때까지 출력
6. 괄호 모두 읽으면 완료
중위 -> 후위 표기법 변환 예)
중위 : A / B * C - D * (E + F)
1. 연산자 우선순위에 따라 괄호 표시 : (((A / B) * C) - (D * (E + F)))
2. 연산자 우선순위 하나씩 변환
(A / B) -> AB/
AB/ * C -> AB/C*
(E + F) -> EF+
D * EF+ -> DEF+*
AB/C* - DEF+* -> AB/C*DEF+*-
3 결과 : AB/C*DEF+*-
다중 스택 & 큐
다중 스택이란
둘 이상의 스택을 하나의 스택 공간으로 표현한걸 말한다.
예를 들어 두개의 스택을 표현할땐 스택의 최하단 최상단을 각각 하위 스택들의 top pointer로 지정하여 중간 지점에서 만나도록 지정을 한다.
이럴 경우 스택의 포화 지점은 top1 = top2가 된다.
이런식으로 하면 다중의 스택을 하나의 스택 공간에 사용하여 공간 효율을 증가 시키는 장점이 있음.
N개의 다중 스택을 하나의 스택에서 구현할 경우 당연히 공간 분할도 N개로 나누어 각 스택을 배당한다.
다중 스택의 가장 첫 공간을 B[i]로 표현하며 Top은 T[i]으로 표현한다. (Bottom, Top)
따라서 B[i] == T[i+1]일 경우에는 i번째 스택은 포화 상태를 의미 하고, B[i] == T[i]일 경우에는 공백 상태를 의미함.
이 수식은 n개의 스택이 구현된 다중 스택에서 i번째 스택에 원소를 삽입할때 오버플로우 검사와 i번째 스택에 원소 삭제시 언어플로우 검사에 사용된다.
그 외 (진도와는 상관없는 용어나 설명)
서브루틴은 주로 조건문이나 반복문에서 조건에 맞을 경우 실행할 로직 부분을 부르는거 같음..
예)
if (조건) then
서브루틴
else
또다른 서브루틴
이런식
