4장 - 연결리스트를 이용한 스택과 큐

배열과 연결 리스트의 비교

 

저장 방식의 차이

배열: 메모리의 인접한 곳에 저장

연결 리스트: 각 노드들은 메모리의 여러 곳에 나누어 저장되고, link포인터를 이용하여 다음 노드의 주소를 기억함

 

메모리 사용 측면

저장될 데이터의 수를 안다면 배열이 효과적.(연결 리스트는 data 뿐 아니라 link포인터가 필요)

데이터 수를 모를 경우, 새로 데이터가 입력될 때마다 malloc 실행 후 연결하면 되는 연결 리스트가 유리함.

 

정렬된 데이터의 유지

배열: 데이터가 추가될 때 기존 데이터의 위치를 변경해야 할 수 있음, 이진 검색 가능

연결 리스트: 데이터가 추가되더라도 기존 데이터의 위치 변경은 발생하지 않음. 이진 검색 불가능

 

 

배열을 이용한 스택과 큐의 구현 방법의 문제점으로

메모리 낭비, stack full의 발생 가능성이 있다.

연결 리스트를 이용하면 이 문제점들을 파훼할 수 있다

 

---

연결 리스트 - stack

 

맨 앞쪽 노드가 top이고, top에서만 push,pop이 발생한다.

push시 새로운 노드의 링크=top, top=새 노드가 됨

pop시 return top.data , top = top.link임 

 

stack 선언

typedef struct {
	int key;
}element;

struct stack{
	element data;
	struct stack* link;

};

struct stack* top;

초기조건: top = NULL;

경계 조건: top = NULL 일 때 stack empty, 

memory full일 때 stack full

 

 

push

void push(element item) {
	struct stack* temp = (struct stack*)malloc(sizeof(struct stack)); //새 노드 생성
	if (temp == NULL)//memory full
		exit(1);

	temp->data = item;
	temp->link = top;
	top = temp;
}

새 노드를 생성, 새 노드의 링크에 기존의 top 연결, top = 새 노드로 갱신

 

pop

element pop() {
	struct stack* temp = top;
	element item;
	if (temp == NULL) {//top==null, stack empty
		exit(1);
	}

	item = temp->data;
	top = temp->link;
	free(temp);//pop 한 노드 삭제
	return item;
}

top == null 이면 빈 스택임.

temp가 stack top을 가리키도록 하고

pop() 반환할 item = temp.data

새로 갱신될 top = temp.link가 됨

다 쓴 temp는 free(temp)해줌

---

리스트를 이용한 큐의 선언

 

typedef struct {
	int key;
}element;

struct Que {
	element data;
	struct Que* link;
};

struct Que* front, * rear;

front, rear가 필요하다.

초기설정으로는 front = NULL;

경계조건으로는 front ==NULL 일 때 queue empty, memory full일 때 queue full이다.

(rear까지 확인 안해도 됨)

 

addq()

void addq(element item) {
	struct Que* temp = (struct Que*)malloc(sizeof(struct Que));
	if (temp == NULL)//memory full
		exit(1);

	temp->data = item;
	if (front)//빈 큐일 경우
		rear->link = temp;
	else
		front = temp;
	rear = temp;
}

temp 노드를 만든다.

temp.data = item이다.

빈 큐일 경우 temp 노드가 rear가 되어야 하고, front 또한 temp노드가 되어야 한다.

빈 큐가 아닌 경우는 기존 rear노드의 link를 temp로 설정해서 새 노드를 이어주고, rear = temp로 설정해준다.

 

deleteq()

lement deleteq() {
	struct Que* temp = front;
	element item;
	if (temp == NULL) //빈 큐인 경우
		exit(1);

	item = temp->data;
	front = temp->link;
	free(temp);
	return item;
}

기존 front.data를 반환하고

기존 front.link를 새로운 front로 설정하고

기존의 front는 free 한다.

---

다항식을 단일 연결 리스트로 표현하기

 

struct poly {
	int coef;
	int expon;
	struct poly* link;
};

struct poly* a, * b, * d;

coef = 계수

expon = 지수

다항식 a, 다항식 b, a+b를 저장할 d.

 

동작원리

a다항식과 b다항식을 앞에서부터 비교한다.

지수가 같은경우, 해당하는 항의 계수를 더한 뒤 d에 삽입

어느 한 쪽의 지수가 더 큰 경우, 더 큰 항을 d에 삽입

 

다항식 d의 항 추가는 리스트의 끝에서 일어나게 되는데, Queue방식이라고 볼 수 있음

 

struct poly* padd(struct poly* a, struct poly* b) {
	//다항식 d = a+b 를 return 하는 함수
	struct poly* front, * rear, * temp;
	int sum;

	rear = (struct poly*)malloc(sizeof(struct poly)); //사용하지 않는 초기 노드를 생성함
	if (rear == NULL)//memory full인 경우임
		exit(1);

	front = rear;
	
	while (a && b) {//a,b 둘다 null이 아닐 때까지
		switch (COMPARE(a->expon, b->expon)) {
		case -1: //a.expon < b.expon
			attach(b->coef, b->expon, &rear);
			b = b->link;
			break;
		case 0://a.expon == b.expon
			attach(a->coef + b->coef, a->expon,&rear);
			a = a->link;
			b = b->link;
			break;
		case 1: //a.expon>b.expon
			attach(a->coef, a->expon,&rear);
			a = a->link;
			break;
		}
	}
	for (; a; a = a->link) attach(a->coef, a->expon, &rear);
	for (; b; b = b->link) attach(b->coef, b->expon, &rear);

	temp = front;
	front = front->link;
	free(temp);
	return front;
}
void attach(float coefficient, int exponent, struct poly** rear) {
	//rear노드 뒤에 새 노드를 추가하는 함수
	struct poly* temp;
	temp = (struct poly*)malloc(sizeof(struct poly));
	if (temp == NULL)
		exit(1);//memoryfull

	temp->coef = coefficient;
	temp->expon = exponent;
	(*rear)->link = temp;
	*rear = temp;
}

중간에 사용하지 않는 temp노드를 만들었는데,

새 노드를 생성해서 link로 이어주는 과정에서

(기존의)rear.link = 새 노드;

rear = 새 노드; 를 해야한다.

이 때, temp노드조차 존재하지 않는 완전히 빈 큐라면

rear = null인 상태이기 때문에 rear.link = 새 노드를 할 필요가 없으며, 해줄 수도 없다.

이런 상황을 배제하기 위해 사용하지않는 temp노드를 만든 것이다.