[자료구조] 스택과 큐(Stack and Queue)

 

스택(stack)

스택과 큐는 순서 리스트(ordered list)의 특별한 경우

 

스택

• 탑(top)이라고 하는 한쪽 끝에서 삽입(push)와 삭제(pop)가 일어남
• 스택 S = (a0,...,an-1)
• a0을 bottom, an-1을 top의 원소
• ai는 원소 ai-1의 위에 있다. (이때 0<i<n)
• 후입선출(LIFO, Last In First Out)

 

시스템 스택(System Stack)

• 프로그램 실행 시 함수 호출을 처리
• 함수 호출 시 활성 레코드(activation record) 또는 스택프레임(stack frame)이라는 구조를 생성하여 시스템 스택의 탑에 둔다.
  • 이전의 스택프레임(호출한 함수의 스택프레임)에 대한 포인터-64bit=8byte
  • 복귀 주소(함수가 종료된 후 실행되어야 할 명령문 위치)-주소는 8byte
  • 지역 변수(static 제외)
  • 호출한 함수의 매개 변수
  • 아래 2개 부분이 스택프레임의 크기에 큰 영향을 준다.
• 함수가 자기자신을 호출하는 순환 호출도 마찬가지로 처리
  • 순환 호출시마다 새로운 스택 프레임 생성
  • 최악의 경우 가용 메모리 전부 소모

 

*스택의 ADT를 정의하기 전에 top을 제대로 정의해야한다.(구현이 달라진다.)

1) 초기 top을 -1로 둔다: 이때 top은 마지막 원소의 위치를 의미하게 된다.

2) 초기 top을 0으로 둔다: 이때 top은 원소를 삽입할 위치를 의미하게 된다.

 

 

 

동적 배열을 사용하는 스택(Stacks using Dynamic Arrays)

동적 배열 이용

-스택의 범위(MAX_SIZE)를 컴파일 시간에 알아야하는 단점 극복

-원소를 위해 동적 할당된 배열 이용

-필요시 배열의 크기를 증대시킴

 

stack full에 대한 새로운 검사

-MAX_STACK_SIZE를 capacity로 대체

-push 변경

-stackFull 변경

• 배열 stack의 크기를 확장
• array doubling: 배열의 크기를 늘릴 필요가 있으면 항상 배열의 크기를 2배로

//REALLOC MACRO
void stackFull()
{
	REALLOC(stack, 2*capacity*sizeof(*stack))
    capacity *=2;
}

시간 복잡도(time complexity): O(n)

-realloc() -> 메모리 할당 O(1)

-capcity*sizeof(*stack) 바이트를 새로운 배열에 복사 O(capacity)

- array doubling의 복잡도 => O(capacity)

- capacity는 2^k이 되므로, O(2^k)

- n>2^k이므로 O(n)

 

 

큐(Queue)

개념

- 한쪽에선 삽입, 한쪽에선 삭제가 일어나는 순서 리스트

-삽입이 일어나는 쪽 rear, 삭제가 일어나는 쪽- front

- 선입선출(FIFO, First In First Out)

 

큐를 순차 기억장소로 표현: 1차원 배열과 두 변수 front, rear

addq와 deleteq: push/pop과 유사하나 사용하는 변수가 구분됨(addq-rear, deleteq-front)

 

작업 스케줄링(job scheduling)

-운영체제에 의한 작업 큐(job queue) 생성

-시스템에 들어간 순서대로 처리

-큐를 순차 표현으로 구현할 때의 문제점: 큐가 점차 오른쪽으로 이동하게 됨.->MAX_QUEUE_SIZE로 rear가 가버림.

 

queueFull일 때 전체큐를 왼쪽으로 이동시켜야함

이동시 첫번째 원소를 q[0]으로, front=-1, rear는 재조정.

이동 시간이 많이 들어, 최악의 경우 O(MAX_QUEUE_SIZE)를 보아야함.

 

원형 큐(Circular Queue)

- 큐가 배열의 끝을 둘러싸도록 함

- 변수 front는 큐에서 첫 원소의 위치로부터 시계반대 방향으로 하나 앞 위치를 가리킴.

- MAX_QUEUE_SIZE-1과 0이 붙은 것 처럼.

//Queue의 이동
if(rear == MAX_QUEUE_SIZE-1) rear = 0;
else rear++; // (rear+1) / MAX_QUEUE_SIZE와 동등--Moduler 연산

- 큐의 공백 조건: front == rear

- full과 empty를 구분하기 위해 그 전에 큐의 크기를 증가시킨다.

• front == rear가 full or empty임을 알기 위해 최대 원소 수를 MAX_QUEUE_SIZE - 1로 한다. (공간 하나를 비움)

void addq(element item)
{ /* queue에 item을 삽입 */
    rear = (rear+1)%MAX_QUEUE_SIZE;
    if (front == rear) queueFull();
    queue[rear] = item;
}

element deleteq()
{ /* queue의 앞 원소를 삭제 */
    element item;
    if (front == rear) return queueEmpty();
    front = (front+1) % MAX_QUEUE_SIZE;
    return queue[front];
}

 

 

동적 할당 배열을 이용하는 원형 큐(Circular Queues using Dynamically Allocated Arrays)

capacity: 배열 queue의 위치 번호

원소 삽입시 배열 크기 확장 필요

• 함수 realloc
• array doubling

원형 큐에 맞게 재구성이 필요

 

최대 복사 원소 수 capacity -1

1) 크기가 두배되는 새로운 배열 생성

2) 두번째 부분(queue[front+1]~queue[capacity-1] 사이의 원소들)을 0에서부터 복사해 넣음

3) 첫번째 부분(queue[0]~queue[rear]사이의 원소들)을  capacity-front-1에서부터 복사해 넣음

 

 

미로문제(A Mazing Problem)

• 미로는 1<=i<=m, 1<=j<=p인 이차원 배열 maze[m][p]로 표현.
• 값이 1이면 막힌 길. 값이 0이면 통과할 수 있는 길.
• 현재의 위치 x: maze[i][j]
• 현재 위치를 중심으로 8개의 후보 인접위치가 존재.
• 이동할 수 있는 방향을 move 배열에 미리 정의. 0~7의 숫자로 표시.

길을 찾아가는 법

-미로 이동 시, 현 위치 저장 후 방향 선택

-잘못된 길을 가면 되돌아와서 다른 방향 시도(rollback)

-시도했던 길을 2차원 배열 mark에 기록해서 유지.

이동 때마다 현 위치를 push, 잘못된 길을 만나면 pop

 

초기 알고리즘에 추가적으로 필요한 것

- 스택에 들어갈 원소(item)은 현 위치+방향정보

- 스택이 full일 때 확장(array doubling)

• 미로의 각 위치는 최대 1번 방문 -> 스택 크기는 미로 배열 내의 0의 갯수만큼
• m*p 크기의 미로면 스택의 최대 크기도 m*p

 

수식의 계산(Evaluation of Expressions)

수식은 피연산자와 연산자 및 괄호로 구성된다.

수식이나 명령문의 의미를 이해하기 위해 연산 수행 순서를 파악.(괄호가 다수긴 함)

연산자는 우선순위 계층(precedence hierarchy)를 가지고 있다.

 

사람은 중위 표기(index notation)을 사용하지만, 컴퓨터는 아님.

후위 표기법(postfix notation): 연산자가 피연산자 이후에 위치+괄호 없음

+전위 표기법(prefix notation): 연산자가 피연산자 앞에 위치 +괄호 없음

 

후위 표기식의 연산

- 수식을 왼쪽->오른쪽으로 스캔

- 연산자를 만날 때까지 피연산자 stack push

- 연산자를 만나면 연산에 필요한 만큼 피연산자 stack pop

- 연산하고 결과를 stack push

이상 반복 후

- stack pop으로 top에서 결과를 가져온다.

 

중위에서 후위로의 변환

-식을 모두 괄호로 묶는다.

-이항 연산자들을 모두 그 오른쪽 괄호와 대체시킨 후, 괄호를 삭제.

 

'(' 연산자가 복잡.

- 스택 속에서는 낮은 우선순위, 그 외엔 높은 우선순위.

- 해결방법: isp(in-stack precedence)와 icp(incoming precedence) 사용, 스택에서 연산자 삭제: isp >= icp

 

다중 스택과 큐(Multiple Stacks and Queues)

같은 배열에 두 개 이상의 스택 구현- 각 스택에 대한 영역이 명시되어야 함.

 

n개의 스택

- 기억 장소를 n개의 segment로 나눔.

- 예상 크기를 알면 그 크기에 따라, 모르면 동일하게 나눔

 

stackFull함수(배열이 full이 될 경우 실행)

- 메모리 내의 빈 공간이 있는 가를 결정

- 사용할 수 있는 자유 공간이 있다면 만원인 스택에 그 자유공간을 할당하도록 다른 스택 이동

 

1) 공간 찾기(stack i 기준)

• 스택 j와 j+1 사이에 빈공간, => top[j]<boundary[j+1]을 만족하는 최소의 j 탐색.(i<j<n)
• 찾으면 i+1부터 j까지의 스택을 오른쪽으로 이동시켜 i와 i+1 사이 공간을 확보.

2) 1번에서 j를 찾지 못하면 스택 i의 왼쪽을 조사

• 스택 j와 j+1 사이에 빈공간, => top[j]<boundary[j+1]을 만족하는 최소의 j 탐색.(1<i<j)
• 찾으면 i+1부터 j까지의 스택을 오른쪽으로 이동시켜 i와 i+1 사이 공간을 확보.

3) 1,2번에서 찾지 못할 시 빈공간 없음.