기본자료 구조 (Linked List 와 Queue, Stack )

아래는 제가 Single Linked list 와  Array로 간단하게 Queue와 Stack을
Programming 하고, Test를 해봤습니다.
버그가 있다면 말씀해주시면 감사하겠습니다.

기본적으로, Queue 는 FIFO 구조 이며,  Stack는 LIFO 구조 입니다.
Queue와 Stack의 동일한 점은 Data를 넣는 지점은 TAIL 이지만,
다른 점은 데이타를 꺼내는 지점 HEAD or TAIL 따라 queue 와 stack으로 나누어지게 됩니다.

1.  Single Linked List  ( Queue 와 Stack )

	#include <stdio.h>
	#include <stdlib.h>
	typedef struct ListElmt_ {
	void * data;
	struct ListElmt_ *next;
	}ListElmt;
	typedef struct List_ {
	int size;
	ListElmt *head;
	ListElmt *tail;
	}List;
	int list_init(List *plist)
	{
	plist->size=0;
	plist->head = NULL;
	plist->tail = NULL;
	return 0;
	}
	int list_ins_last(List *plist, void *pdata)
	{
	int ret=0;
	ListElmt *pNewElemt,*pNext;
	if( plist->size >= 0 ){
	pNewElemt = (ListElmt *) malloc( sizeof(ListElmt) );
	pNewElemt->data = pdata; // last node address
	pNewElemt->next = NULL;
	if(plist->tail == NULL || plist->head == NULL){ // first insert elements
	plist->head = pNewElemt;
	plist->tail = pNewElemt;
	}else { // second insert elements
	if( plist->head != NULL){
	plist->tail->next = pNewElemt;
	plist->tail = pNewElemt;
	}else
	ret=-2; //error 1
	}
	plist->size++;
	if(ret < 0)
	free(pNewElemt);
	}else
	ret = -1; // error 1
	return ret;
	}
	int list_del_head(List *plist,void **pData) // for queue, dequeue
	{
	int ret=0;
	int *pTest;
	ListElmt *tmp;
	if( plist->size > 0 && plist->head != NULL ){
	if(plist->head->next == NULL || plist->size == 1){ // last one,
	*pData = plist->head->data;
	free(plist->head);
	// reset
	plist->head = NULL;
	plist->tail = NULL;
	plist->size = 0;
	pTest = (int *)*pData;
	}else { // more than 1
	*pData = plist->head->data; // head's data
	tmp = plist->head;
	plist->head = plist->head->next; // pop
	free(tmp);
	pTest = (int *)*pData;
	plist->size--;
	}
	}else
	ret=-1;
	return ret;
	}
	int list_del_tail(List *plist,void **pData) // for stack, pop
	{
	int ret=0;
	int *pTest,i;
	ListElmt *tmp;
	if( plist->size > 0 && plist->tail != NULL ){
	if(plist->size == 1) {
	tmp = plist->tail;
	*pData = tmp->data;
	free(tmp);
	//reset;
	plist->head = NULL;
	plist->tail = NULL;
	plist->size = 0;
	}else { //more than 2 elmts
	tmp = plist->head;
	for(i=0;i<(plist->size-2);i++)
	{
	if(tmp->next != NULL)
	tmp = tmp->next; // (tail-1)
	}
	*pData = plist->tail->data;
	free(plist->tail);
	plist->tail = tmp;
	plist->size--;
	}
	}else
	ret=-1;
	return ret;
	}
	List list;
	int main()
	{
	int data[]={1,2,3,4,5,6,7,8,9,10};
	int pri=0;
	int i=0,j;
	int chk=0;
	ListElmt *pElmt,*pNext;
	int *pTestData;
	int *pTestData2;
	list_init(&list);
	for(j=0;j<5;j++)
	{
	for(i=0;i<4+j;i++)
	{
	chk = list_ins_last(&list,(void *)&data[i]);
	if(chk < 0)
	printf("error ins!!!!!!!!! chk=%d",chk);
	printf("enqueue %d/%d data %d \n",i,list.size,data[i]);
	}
	printf("\n\n");
	for(i=0;i<3+j;i++)
	{
	// chk = list_del_head(&list,(void **)&pTestData2 );
	chk = list_del_tail(&list,(void **)&pTestData2 );
	if(chk < 0)
	printf("error del !!!!!!!!! chk=%d",chk);
	printf("dequeue %d/%d data %d \n",i,list.size, *pTestData2);
	}
	printf("\n\n");
	}
	return 0;
	}

view raw langc_algo_single_list.c hosted with ❤ by GitHub

2.  Array Queue and Stack 

	#include <stdio.h>
	#define MAX 10
	int size=0;
	int head=0; // not used in stack
	int tail=0;
	int queue[MAX];
	int stack[MAX];
	//QUEUE
	int enqueue(int *pqueue, int *pdata)
	{
	if(size >= MAX) return -1; // check max value , error , not working
	pqueue[tail] = *pdata; //next item,
	if(tail == (MAX-1)) tail = 0;
	else tail++;
	size++;
	return 0;
	}
	int dequeue(int *pqueue, int *pdata)
	{
	if(size <= 0) return -1; // check minum value , error
	*pdata = pqueue[head];
	if(head == (MAX-1)) head = 0;
	else head++;
	size--;
	return 0;
	}
	// STACK
	int push(int *pstack, int *pdata)
	{
	if(size >= MAX) return -1; // check max value , error , not working
	pstack[size] = *pdata;
	size++;
	return 0;
	}
	int pop(int *pstack, int *pdata)
	{
	if(size <= 0) return -1; // check minum value , error
	size--;
	*pdata = pstack[size];
	return 0;
	}
	int main()
	{
	int i=0;
	int data=0;
	int off=10;
	int ret=0;
	for(i=0;i<MAX+10;i++)
	{
	data = off + i;
	ret = enqueue(queue,&data);
	printf("enqueue %d err=%d\n",data,ret);
	}
	printf("\n\n");
	for(i=0;i<MAX;i++)
	{
	ret = dequeue(queue,&data);
	printf("dequeue %d err=%d\n",data,ret);
	}
	printf("\n\n");
	off=5;
	for(i=0;i<5;i++)
	{
	data = off + i;
	ret = enqueue(queue,&data);
	printf("enqueue %d err=%d\n",data,ret);
	}
	printf("\n\n");
	for(i=0;i<4;i++)
	{
	ret = dequeue(queue,&data);
	printf("dequeue %d err=%d\n",data,ret);
	}
	return 0;
	}

view raw langc_algo_array_queue_stack.c hosted with ❤ by GitHub