독학사2단계_자료구조_3장 스택과 큐

3장. 스택과 큐

가) 스택(Stack)

1. 스택의 정의

·선형 리스트의 종류로써 리스트의 한 쪽 끝에서만 데이터의 삽입(PUSH)과 삭제(POP)가 이루어진다.

·LIFO(Last In First Out) ; 후입 선출

·스택에서 데이터를 삽입하고 삭제하는 위치를 top라고한다. 반대편을 bottom이라고 한다.

2. 시스템 스택(System Stack)

·OS(Kernel)이 사용하는 스택을 시스템 스택이라고한다.

3. 스택의 추상화 자료 구조

·스택의 기본 행동

(필수)Push

(필수)Pop

(필수)Empty        스택이 비어있는지 확인

(유용)Size          스택에 들어있는 원소의 갯수

(유용)Capacity    스택의 크기

4. 스택의 삽입, 삭제

·삽입(PUSH)

스택이 가득 차있지 않으면 (top+1)위치에 item를 삽입한다.

가득 차잇으면 overflow상태이다.

procedure push()

if top >= n then overflow    //n은 아마 스택의 크기 인듯

else

top = top +1

stack[top] = item

·삭제(POP)

스택이 비어있지 않으면 top위치의 item를 삭제한다.

비어있다면 underflow상태이다.

procedure pop()

if bottom >= n then underflow    //n은 아마 스택의 크기 인듯

else

item = stack[top]

delete stack[top]    //걍 이렇게 내가 이렇게 표현함

top = top -1

5. 스택의 적용 분야들

나) 큐(Queue)

1. 큐의 정의

·선형 리스트의 한 종류로써 한쪽 노드로는 삽입만을 또 다른 한쪽 노드로는 삭제만이 이루어진다.

·FIFO(Fist In Fist Out) ; 선입선출

·가장 먼저 서비스(데이터 처리)를 받을 항목을 큐의 선두(Front, Head)라고하며 큐의 마지막 항목을 후미(Rear, Tail)이라고 한다.

2. 큐의 추상화 자료 구조

·큐의 기본 행동

push_back    후미에 데이터 삽입

pop              선두의 데이터 불러오고 해당 데이터를 큐에서 삭제

size             큐에 들어있는 항목의 수

capacity       큐의 크기

clear            큐의 모든 원소 삭제

3. 큐의 삽입, 삭제

·삽입

delete the top item

·삭제

stack의 top에 item 삽입

4. 원형 큐(Circular Queue)

·선형 큐의 비효율적인 기억 자소의 이용을 보완하여 배열을 직선이 아닌 원형으로 구성함

·항목의 큐에 대한 삽입이나 삭제가 선두와 후미부분에 계속 연결되어 일어나서 기억공간의 소모를 줄일 수 있다.

5. 스택의 적용 분야들

다) 데크(Dequeue(Double-ended queue)[발음을 deck로함])

·양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조이다.

라) 스택의 응용 : 수식 계산

1. 연산의 우선 순위

2. 수식의 표기법

	Operating Order	A = B * (C + E ) - F / G
전위 표기법(Prefix)	Root – Left – Right	= A - * B + C E / F G
중위 표기법(Infix)	Left – Root – Right	A = B * (C + E ) - F / G
후위 표기법(Postfix)	Left – Right - Root	A B C E + * F G / - =

3. 후의 표기식의 연산

4. 중위 표기를 후위 표기로 변환

마) 다중 스택과 큐

1. 다중 스택의 정의

·하나의 스택안에 여러 개의 스택이 들어가 있는 형태이다. 

예를들어 배열로 구현을 한다고 가정하면 하나의 배열안에 여러개의 스택이 있는 것이다.

·top과 bottom(boundary)가 유동적이다.

·아래 그림은 m크기의 스택 안에 n개의 스택이 들어있는 것이다. n-1개의 top과 n개의 bottom이 있다.(마지막 bottom은 전체 스택의 끝을 의미)

[구현] [https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&ved=0CEEQFjAE&url=http%3A%2F%2Fdasan.sejong.ac.kr%2F~jano%2F2013%2Fds%2Fds_chapter3.ppt&ei=Cu1bU7LEH8XkiAfAs4CIDw&usg=AFQjCNHLfyFi-8e_etT2t8uNoOruOcu4dw&sig2=aUDLYr0xDgU2wTfPlvpM7Q&bvm=bv.65397613,d.aGc&cad=rja]

#define MEMORY_SIZE 100      // memory의 크기

#define MAX_STACKS 10         //가능한 스택의 최대 수+1

//전역 변수 선언

element memory[MEMORY_SIZE];

int top[MAX_STACKS];

int boundary[MAX_STACKS];

int n;                                    //사용자가 입력한 스택의 크기

//배열을 거의 같은 크기의 세그먼트로 나누는 코드

top[0] = boundary[0] = -1;

for (i=1; i<n; i++)

top[i] = boundary[i] = (MEMORY_SIZE/n)*i;

boundary[n] = MEMORY_SIZE-1;

2. 다중 스택의 삽입

//다중 스택의 삽입

void push(int i, element item)

{

if (top[i] == boundary[i+1])

stackFull(i);               //스택이 가득 찼을때 에러를 처리해주는 함수이다. 해당 스택의 왼쪽 오른쪽의 빈 공간이 있는지 검사하고 다른 스택들을 이동시켜 공간을 만든다.

memory[++top[i]] = item;

}

3. 다중 스택 삭제

//다중 스택의 삭제

element pop(int i)

{

if (top[i] == boundary[i])

return stackEmpty(i);     //해당 스택을 Clear시키는 함수

return memory[top[i]--];

}