자료구조 03 스택 04 큐 05 연결 리스트

03 스택

 

001 스택의 개념과 추상자료형

- 스택을 가지고 운영체제 만들고, 프로그래밍 언어가 실행될 수 있는 환경도 만들자

 

① 어떤 값/ 데이터에 접근할 수 있는 순서가 정해져 있다

② 어떤 아이템이 먼저 스택안에 들어왔는지, 먼저 쌓여진 순서를 알아낼 수 있다

 

스택의 정의

- 객체와 그 객체가 저장되는 순서를 기억하는 방법에 관한 추상 자료형 (객체를 저장도 함)

- 가장 먼저 입력된 자료가 가장 나중에 출력되는 관계

 

- 0 개 이상의 원소를 갖는 유한순서 리스트

- push (add) 와 pop (delete) 연산이 한 곳에서 발생하는 자료구조

- create, push, pop 3개 연산만 스택에 접근할 수 있다, 다른 건 접근 금지

Stack CreateS(maxStackSize) :: = 
 스택 크기가 maxStackSize 인 빈 스택을 생성하고 반환한다

Element Push(stack, item) :: =
    if (IsFull(stack))
    	then { 'stackFull' 을 출력한다 }
    else { 스택의 가장 위에 item 을 삽입하고, 스택을 반환한다; }

Element Pop(stack) :: =
    if (IsEmpty(stack))
    	then { 'stackEmpty' 을 출력한다 }
    else { 스택의 가장 위에 있는 원소(element)를 삭제하고 반환한다; }

- 이런 규칙이 OS / 컴파일러 개발자가 만들어서 OS 가 제대로 작동 or 프로그래밍 언어가 효율적으로 작동하게 만든다

 

- top 변수는 Stack 의 제일 위의 값을 가리키는 변수, top 을 이용해서만 Stack 에 접근할 수 있다

- top 은 OS / 컴파일러 개발자들만 결정하고 변경할 수 있다

- S[0] 인덱스로 접근 불가

 

002 스택의 응용과 구현

 

- 변수에 대한 메모리 할당과 수집을 위한 시스템 스택

- 서브루틴 호출관리를 위한 스택 

- 연산자들 간의 우선순위에 의해 계산순서가 결정되는 수식 계산

- 인터럽트(시스템 프로그래밍) 처리와, 이후 리턴할 명령 수행지점을 저장하기 위한 스택

- 컴파일러, 순환 호출(recursive call, 재귀 호출) 관리

 

스택의 삭제연산 > '--' '++' 연산자의 위치에 따라 연산의 적용순서가 달라질 수 있음

 

#define STACK_SIZE 10
typedef int element;
element stack[STACK_SIZE];
int top = -1; // 아무것도 가리키지 않음

element pop() {
    if (top == -1) {
        printf("Stack is Empty!!\n";
        return 0;
        }
    else 
    	return stack[top--]; // 순서 중요
}

void push(element item) { // 스택의 삽입연산, item = 400
    if (top >= STACK_SIZE-1) { // 스택이 이미 FULL 인 경우
        printf("Stack is Full!!\n");
        return;
    }
    else 
    	stack[++top] = item;
}

 

003 사칙 연산식의 표현

 

수식의 계산

- 연산자의 계산 순서를 생각해야 한다 ( × ÷ 먼저, + - 는 앞에 나온 것 먼저 등 )

 

수식의 표기방법

- 중위 표기법 ( infix notation ) A+B 연산자를 피연산자 사이에 표기하는 방법

- 후위 표기법 ( postfix notation ) AB+ 연산자를 피연산자 뒤에 표기하는 방법

- 중위 표기법을 후위 표기법으로 변형하는데 스택을 사용할 수 있고, 스택을 이용해 계산한다

 

- 괄호에 맞춰서 먼저 계산할 것들을 고려해서 후위 표기법으로 표기하므로, 후위 표기법에는 괄호가 없다

- 스택에 든 후위표기식과 계산법 > PPT 참고

 

 

04 큐

 

001 큐의 개념 및 추상자료형

 

- 스택은 위에서 넣고 위에서 빼고, 큐는 위에서 넣고 아래에서 빼고

- queue 줄서다. 누가 먼저왔는지 알 수 있다 (= 스택과 같다)

- 컴퓨터는 직관적으로 알 수 없으므로 큐 / 스택과 같은 자료구조와 그에 맞는 연산을 정의해 사용한다. 변수값을 아무나 접근 / 변경 못한다

 

- 택시타기 위한 행렬, 병원 접수대, 은행의 예금인출기, 백화점 계산대 위에 놓인 상품들 

- 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄 ( First-in-First-out )

 

- 한 쪽에서는 삽입연산만 발생하고, 다른 쪽에서는 삭제연산만 발생하는 양쪽이 모두 트여있는 자료구조

> 데이터 삽입 / 삭제가 서로 다른 곳에서 일어난다 > 데이터에 접근하는 변수를 달리 쓴다 > 첨자 / 인덱스 값에 서로 다른 변수를 이용한다

 

- 삽입연산: 서비스받기 위한 기다림, 대기열

- 삭제연산: 서비스를 받는 중, 완료

 

- 삽입 / 삭제 같은 곳에서 일어나는 스택은 1개의 변수 ( top 변수 ) 로 처리하고, 이를 pop / push 연산자가 공유한다

- 삽입 / 삭제 다른 곳에서 일어나는 큐는 2개의 변수를 운영한다 ( front 는 삭제에, rear 는 삽입에 사용하는 변수 )

 

- queue 에서 data 접근법은 1개이다: front, rear 변수를 이용해서 값 접근하기: push, pop, delete, add 든 시스템만 운영하는 front, rear 변수를 통해 값을 접근할 수 있다, 프로그래머가 직접 조작 못한다

 

- 큐의 삽입(Add_q) / 삭제(Delete_q) 연산

Queue Add_q (queue, item) ::=
	if (IsFull_q(queue))
    	then { 'queueFull' 을 출력한다; }
        else { 큐의 rear 에서 item 을 삽입하고, 큐를 반환한다; }
// 어디서도 rear 변수에 직접 접근하지는 않았다

Element Delete_q(queue) ::=
	if (IsEmpty_q(queue))
    	then { 'queueEmpty' 를 출력한다; }
        else { 큐의 front 에 있는 원소를 반환한다; }

- 빈 큐 검사(IsEmpty_q) / 큐의 만원 검사(IsFull_q) 연산 

: 프로그램이 더 안전하게 작동하기 위해 삽입 / 삭제 연산에 사용하고, 그 외에는 ...

Boolean IsEmpty_q(queue) ::=
	if (rear == front)
    	then { 'TRUE' 값을 반환한다; }
        else { 'FALSE' 값을 반환한다; }

Boolean IsFull_q(queue, maxQueueSize) ::=
	if ((queue 의 elements 의 갯수) == maxQueueSize)
    	then { 'TRUE' 값을 반환한다; }
        else { 'FALSE' 값을 반환한다; }

- 초기 상태에는 rear, front 가 같은 위치이다가, 삽입이 일어나면 rear 가 증가. 삭제가 일어나면 front 증가. 다시 rear, front 가 같은 위치이면 Queue empty 상태이다

 

002 큐의 응용

 

- CPU 관리방법인 FCFS( First-Come First-Served ), RR( Round Robin ) 등의 스케줄링 기법에 사용한다?

 

003 배열을 이용한 큐의 구현

 

- 큐의 생성 (변수 rear 의 초기값은 큐의 공백상태를 나타내는 '-1' 로 시작함)

#define QUEUE_SIZE 5
typedef int element;
element queue[QUEUE_SIZE];
    int float = -1;
    int rear = -1;

- 큐의 삽입연산 (삽입연산 발생 시 rear 변수만 오른쪽으로 이동, 삭제연산 발생 시 front 변수만 오른쪽으로 이동)

void Add_q(int *rear, element item) {
    if (*rear == QUEUE_SIZE-1) {
    	printf("Queue is full!!");
        return;
    }
    queue[++(*rear)] = item;
    return;
}

- 큐의 삭제연산 (삭제연산의 결과로 삭제된 원소를 Delete_q 연산자의 호출 프로그램에게 반환함)

element Delete_q (int *front, int rear) {
    if (*front == rear) {
    	printf("Queue is empty\n");
        return;
    }
    return (queue[++(*front)]);
}

 

004 원형 큐

 

- 배열로 구현한 큐의 경우, 큐의 원소의 갯수가 n-1 이 아니더라도 큐가 full 이 될 수 있음

 

- 배열의 문제점을 해결하기 위해 원형 큐가 제안됨

- 원형 큐는 파이프의 입구와 출구 부분을 연결시킨 형태임

- 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 나머지 연산을 활용함

 

05 연결 리스트

 

001 리스트의 개념

 

- '일정한 순서'의 나열, '논리적인 순서'의 나열

- 리스트의 '순서'는 물리적인 위치와 상관없이 '논리적인 순서' 혹은 원소들 간의 '의미적인 순서'를 말함

- 메인 메모리 상 순서는 뒤죽박죽이어도, 접근 시 순서가 보장됨. 실제 메모리 적재 ≠ 데이터 접근

 

- 배열은 인덱스로 표현되는 '순서' 가 배열 원소의 메모리공간 (주기억장치) 에서의 물리적 위치를 의미함

- 리스트의 '순서' 개념은 '논리적인 순서' 이며, 원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들 간의 논리적인 순서만 유지함

 

리스트의 구현방법

- 포인터를 이용한 리스트 구현: 연결리스트

- 배열을 이용한 리스트 구현

 

002 배열을 이용한 리스트의 구현

 

- 중간에 원소 삽입 시, 1개 삽입하자고 데이터 10만개 이동 .... 데이터 이동시간이 발생

- 배열의 확장: 초기배열 선언에서 충분히 크게 하면 배열의 추가확장을 피할 수 있겠지만 메모리 낭비가 될 수도 있음

: 원소를 리스트 중간에 삽입하기 위해서는 원소값을 하나씩 뒤로 밀어야 함, 이동은 필연적

 

- 중간에 원소 삭제 시, 빈 공간을 그냥 둘 수 없고 또 이동이 필요함

- 데이터 이동에 대한 오버헤드, 성능에 비효율성이 발생함

 

- 배열로 구현된 리스트는 원소의 순서가 연속적인 물리적 주소에 저장됨, 원소를 삽입 / 삭제하기 위해 모든 원소를 뒤로 혹은 앞으로 이동시켜야 함

- 리스트 원소값의 이동은 원소수가 많을 수록 프로그램 수행시간을 증가시킴

 

- 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴, 자료의 삽입 / 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하면 빈번한 자료이동으로 인한 비효율적인 컴퓨팅 성능을 유발함

 

003 포인터를 이용한 리스트의 구현

 

- 노드(node) : 리스트의 원소(값) + 다음 원소를 가리키는 정보

- 노드는 데이터 요소 (원소, 값) 와 리스트의 다음 원소를 지시하는 포인터 (주소, 링크link) 로 구성됨

 

*다음 노드는 없다, 이 다음에 오는 데이터는 없다 = 끝

*리스트가 메모리에 적재됐을 때 메인 메모리의 주소값 1000, 1004 등등등

 

004 포인터 변수 및 리스트의 삭제 / 삽입

 

리스트의 생성

- 정수값 data 와 링크 link 로 구성된 노드( node ) 의 생성

struct linked_list_node {
    int data;
    struct linked_list_node *link;
}

- 포인터의 할당과 반환 예

int a, *p_a;
float b, *p_b;
p_a = (int *)malloc(sizeof(int)); // malloc 은 그때그때 필요하면 실행중에 메모리를 할당받는 것
p_b = (float *)malloc(sizeof(float));
*p_a = 10;
*p_b = 3.14;
printf("a is %d, b is %f\n", *p_a, *p_b);
free(p_a);
free(p_b);

 

005 연결 리스트에서 노드의 삽입과 삭제

 

- 연결리스트에서 노드의 삭제 (그림 확인)

1. 삭제할 노드의 선행노드의 링크 필드를 삭제할 노드의 후행노드를 가리키게 한다
2. 삭제할 노드를 메모리에 반환한다 (= OS 에 준다, 가비지컬렉션)

 

- 연결리스트에서 노드의 삽입 (그림 확인)

1. 메모리 공간을 할당받고, 삽입할 내용을 저장해 삽입할 x 노드를 생성한다
2. x 노드의 링크 부분이 후행노드가 될 j 노드를 가리키게 한다
3. 삽입될 x 노드의 선행노드가 될 i 노드의 링크필드가 x 노드를 가리키게 한다

 

void addNode(linkedList_h* H, int x) {
// 리스트 마지막 노드에 삽입연산하며, x 값은 100 이라고 가정함
    listNode* NewNode;
    listNode* LastNode;
    NewNode = (listNode*)malloc(sizeof(listNode));
    NewNode -> data = x;
    NewNode -> link = NULL;
}