[C 언어 / 자료구조] 리스트 / 스택 / 큐

리스트를 그림으로 표현

배열 : 길이가 정해져 있음 (정적)
연결 리스트 : 길이가 정해져 있지 않음 (동적)

스택 : 후입선출 (Last-in, First-out)
큐 : 선입선출 (First-in, First-out)

---

메모리 영역 정리

---

 

- 순차 리스트

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

// 논리값 매크로 
#define	TRUE	1
#define FALSE	0

// 배열 길이 지정 
#define LIST_LEN	100

// 자료형 별칭 
typedef int Data;

typedef struct _ArrayList {
	Data arr[LIST_LEN];
	int cur;
	int numOfData;
} ArrayList;

// 리스트 변경을 손쉽게 하기 위해 별칭 통합 
typedef ArrayList List;

// 초기화 , 삽입 , 처음 , 다음이후 , 삭제 , 총합 
void ListInit(List * plist);
void LInsert(List * plist, Data data);

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);

Data LRemove(List * plist);
int LCount(List * plist);

#endif

#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h" 

/*
typedef struct _ArrayList {
	Data arr[LIST_LEN];
	int cur;
	int numOfData;
} ArrayList;
*/

// 초기화 , 삽입 , 처음 , 다음이후 , 삭제 , 총합 
void ListInit(List * plist) {
	plist->numOfData = 0;
}

void LInsert(List * plist, Data data) {
	if(plist->numOfData > LIST_LEN) {
		printf("저장이 불가능합니다. \n");
		return;
	}
	
	plist->arr[plist->numOfData] = data;
	plist->numOfData++;
}


int LFirst(List * plist, Data * pdata) {
	if(plist->numOfData == 0) {
		return FALSE;
	}
	
	plist->cur = 0;
	*pdata = plist->arr[0];
	
	return TRUE;
}

int LNext(List * plist, Data * pdata) {
	if(plist->cur >= plist->numOfData - 1) {
		return FALSE;
	}
	
	plist->cur++;
	*pdata = plist->arr[plist->cur];
	
	return TRUE;
}


Data LRemove(List * plist) {
	int rpos = plist->cur;
	int size = plist->numOfData - 1;
	int i;
	Data rdata = plist->arr[rpos];
	
	for(i=rpos; i < size; i++) {
		plist->arr[i] = plist->arr[i+1];
	}
	
	plist->numOfData--;
	plist->cur--;
	
	return rdata;
}

int LCount(List * plist) {
	return plist->numOfData;
}

말그대로 초기화, 리스트를 만들고 초기화 작업으로 초기값을 잡아준다.

 

삽입 과정, arr[0] -> arr[1] -> arr[2] 에 하나씩 데이터를 삽입

 

cur 를 0으로 초기화 후 pdata에 arr의 첫번째를 넣어줌

 

cur 가 하나씩 증가하면서 pdata에 arr[cur] 를 넣어줌

 

삭제는 그냥 삭제할거 다음에 있는걸 땡겨오면 된다.

 

LCount 는 그냥 배열에 있는 총 갯수이다.

 

- 더미 연결 리스트

 

- 원형 연결 리스트

 

- 양방향 연결 리스트

 

- 배열 기반 스택

 

- 리스트 기반 스택

 

- 배열 기반 큐

 

- 리스트 기반 큐