#27 [C 자료구조] 연결 리스트: 스택/큐/덱 구현하기

이전 포스팅에서 살펴봤던당했던 스택/큐/덱은 연결 리스트로 구현하면 훨씬 더 효율적으로 표현할 수 있다. 그래서 실제로 연결리스트로 구현되는 것들이 대부분이다. 오늘 세 가지 부분에 대해서 DEEEEEEEEEEEP하게 들어가 보도록 하자. 반드시 스택/큐 에 대한 일반적인 구현 방식에 대해 선행지식이 있어야 한다.

파이팅하자 파이리썬!!

 

 

 

스택 with 연결 리스트

연결 리스트로 구현한 스택은 다음과 같은 장점을 가지고 있다.

- 다 음 -

1) 노드 추가에만 메모리를 할당, 이전보다 효율적

2) top 노드를 포인터 변수가 가리키고 포인터 변수로 직접 접근

3) 그러나 포인터 연산 필요

연결 리스트로 오면서 값 별 포인터가 추가된 모습이다.

 

바로 연결리스트로 구현한 스택을 코드로 봐보자.

 

1) 스택형 연결 리스트 스트럭쳐 만들기

typedef struct { //스택 안에서 노드 temp 을 삽입/삭제 하기 위함
	int key;
} element;

typedef struct stack SP;
typedef struct stack {
	element item;
    SP *link; // 아래 node 참조
};

 

2) push 함수 만들기

void push(element item, SP *temp) {
	temp -> item = item; // 위에 정의된 item을 temp노드에 넣음
    temp -> link = top; // 이전 top을 temp가 가리킴
    top -> tmep; // top포인터가 temp를 가리킴
}

위와 같은 과정을 띄게 된다. 이전 단순 연결 리스트의 삽입과 크게 다르지 않다.

 

3) pop 함수 만들기

element pop() {
	SP *temp = top; // 최상단의 노드를 temp도 가리킴
    element item; // 꺼낼 item을 일단 정의
    item = temp ->  item; // 현 최상단의 노드를 item에 넣음
    top = temp -> link; // top 포인터를 이전 노드에 박아줌
    free(temp);
return item;
}

 

스택 최댓값을 주고 구현하기

스택의 최대값을 설정하고 구현하는 스택 표현방식도 어렵지는 않다.

 

1) 스택형 연결 리스트 스트럭쳐 만들기

위와 비슷하지만 define을 해준다.

#define MAX_STACKS 10

typedef struct {
	int key;
} element;

typedef struct stackPointer;
typedef struct stack {
	element item;
    stackPointer *link;
};

stackPointer *top[MAX_STACKS]; //10개짜리를 만듦

 

2) push 함수 만들기

void push(int i, element item) { //이전 노드가 아닌 순서인 int i를 넣는다.
	stackPointer *temp = (stackPointer*) malloc (sizeof (stackPointer)); //새로 메모리 할당해준 노드

	temp -> item = item; // 위에 정의된 item을 temp노드에 넣음
    temp -> link = top[i]; // 이전 top[i]가 가리키던 것을 temp가 가리킴
    top[i] -> tmep; // top[i]포인터가 temp를 가리킴
}

노드를 새로 추가해줄 때 malloc()으로 새로운 노드를 생성해준다는 점이 다르다.

 

3) pop 함수 만들기

element pop(int i) { //i번째 스택의 top에서 값 삭제할 것
	stackPointer *temp = top[i]; // 최상단의 노드를 temp도 가리킴
    element item; // 꺼낼 item을 일단 정의
    
    if (!temp) //empty stack이면
    	return stackEmpty();
    
    item = temp ->  item; // 현 최상단의 노드를 item에 넣음
    top[i] = temp -> link; // top[[i] 포인터를 이전 노드에 박아줌
    free(temp);
return item;
}

이 것 또한 위와 크게 다르진 않다.

---

 

 

 

 

큐 with 연결 리스트

큐 또한 스택과 비슷한 특성을 지니고 있다. 선형 큐와 비슷하지만 원형 큐처럼 문제점을 해결했다고 보면 된다.

연산처리 시간과 간단한 방법을 통해 표현이 가능해졌다.

마찬가지로 포인터로 컨트롤한다.

 

1) 큐 스트럭트 짜기

typedef struct { //한 큐에 노드 temp 삽입/삭제 용
	int key;
} element;

typedef struct queue QP;
typedef struct queue {
	element item;
    QP *link;
};

QP *front;
QP *rear;

스택과 비슷하지만 여기선 front와 rear가 같이 생성된다는 점을 유의하자.

2) add 함수 만들기

void addq(element item, QP *temp){
	temp -> item = item; // 넣고자 하는 값을 노드에 삽입
    temp -> link = NULL; // 템프는 맨 뒤이므로 아무것도 가리키지 않음
    if (front)
    	rear -> link = temp; // 맨 뒷 노드가 템프 참조
    else
    	front = temp; //temp가 첫 타 일떄
    rear = temp;  //이제 맨 뒤는 temp
}

 

3) delete 함수 만들기

element deleteq() {
	QP *temp = front;
    element item;
    item = temp -> item; //첫 값을 item에 넣음
    front = temp -> link; //프론트는 이제 두 번째 값을 가리킴
    free(temp);
    return item;
}

 

큐 최대 값을 주고 구현하기

스택과 마찬가지로 MAX_QUEUES를 줘보자

 

1) 큐 스트럭트 짜기

#define MAX_QUEUES 10 //최대 큐값

typedef struct { 
	int key;
} element;

typedef struct queue queuePointer;
typedef struct queue {
	element item;
    queuePointer *link;
};

queuePointer *front[MAX_QUEUES];
queuePointer *rear[MAX_QUEUES];

 

2) add 함수 만들기

void addq(int i, element item){
	queuePointer *temp = (queuePointer*) malloc(sizeof(queuePointer));
    
    temp -> item = item; // 넣고자 하는 값을 노드에 삽입
    temp -> link = NULL; // 템프는 맨 뒤이므로 아무것도 가리키지 않음
    if (front[i])
    	rear[i] -> link = temp; // 맨 뒷 노드가 템프 참조
    else
    	front[i] = temp; //temp가 첫 타 일때
    rear[i] = temp;  //이제 맨 뒤는 temp
}

3) delete 함수 만들기

element deleteq(int i) {
	queuePointer *temp = front[i];
    element item;
    
    if(!temp)
    	return queueEmpty(); 
    
    item = temp -> item; //첫 값을 item에 넣음
    front[i] = temp -> link; //프론트는 이제 두 번째 값을 가리킴
    free(temp);
    return item;
}

---

 

 

 

 

덱(Deque) with 연결 리스트

덱은 양쪽 끝에서 삽입과 삭제를 허용하는 스택+큐 구조다.

예시를 들어보자면 다음과 같을 때 사용된다.

• 웹브라우저 히스토리 (큐로도 가능), 앞 삽입, 뒤 삭제 구조
• undo 과정, 오래된 것들은 지우고 앞에 것을 저장함
• scroll

덱의 수행 시간은 이중 연결 리스트를 구현한다면 스택과 큐의 수행 시간과 동일하다.

프로그래밍이 다소 복잡하다.

오늘은 여기까지!!

다음 시간엔 원형, 이중 연결 리스트를 배워보자!!

 

덱의 프로그래밍은 생각보다 다소 안 쓰이므로 생략하겠다. 양아치