스택, 큐 구현

스택.

배열로 구현.

#include <stdio.h>

int stack[100];
void push(int *top, int data)
{
	if(*top>99)
	{
		printf("stack full\n");
		return;
	}
	*top += 1;
	stack[*top] = data;
}
void pop(int *top)
{
	if(*top==-1)
	{
		printf("stack empty\n");
		return;
	}
	stack[*top] = -1;
	*top -= 1;
}
void print_stack()
{
	int i;
	for(i=0;i<sizeof(stack)/sizeof(int);i++)
		if(stack[i]!=-1)
			printf("%d->",stack[i]);
	printf("\n");
}
 
int main()
{
	int i;
	int top = -1;
	for(i=0;i<100;i++)
		stack[i] = -1;
	for(i=0;i<10;i++)
		push(&top,i);
	print_stack();

	for(i=0;i<15;i++)
		pop(&top);
	print_stack();
    return 0;
}

링크드 리스트로 구현. 모범구현인지는 모르겠다.

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

struct stack {
    int data;
    struct stack *next;
};
void push(stack *s, int data)
{	
	stack *newitem = (stack *)malloc(sizeof(stack));
	stack *head = s;
	while(s->next!=NULL)
		s = s->next;
	s->next = newitem;
	newitem->data = data;
	newitem->next = NULL;
	s = head;
}
int pop(stack *s)
{
	stack *temp = s;
	stack *last;
	int ret;
	while(temp->next!=NULL)
	{
		if(temp->next->next==NULL)
			last = temp;
		temp = temp->next;
	}
	ret = temp->data;
	last->next = NULL;
	free(temp);
	return ret;
}
void print_stack(stack *s)
{
	stack *temp = s;
	printf("stack = ");
	while(temp->next!=NULL)
	{
		temp = temp->next;
		printf("%d ",temp->data);
	}
	printf("\n");
}
void deletestack(stack *s)
{
	stack *temp;
	while(s->next!=NULL)
	{
		temp = s;
		s = s->next;
		free(temp);
	}
}

int main()
{
	stack *s = (stack *)malloc(sizeof(stack));
	int i;
	s->next = NULL;
	for(i=0;i<10;i++)
		push(s,i);
	print_stack(s); //10개 넣고 출력해봄.
	for(i=0;i<5;i++) //5개 pop
		printf("pop = %d\n",pop(s));
	print_stack(s); //5개 pop하고 출력해봄.

	deletestack(s); //메모리 해제
    return 0;
}

큐.

배열을 이용한 큐 구현.

#include <stdio.h>

int queue[100];
void enqueue(int data, int *rear)
{
	//printf("*rear = %d, sizeof = %d\n",*rear,sizeof(queue)/sizeof(int));
	if(*rear == (sizeof(queue)/sizeof(int)))
	{
		printf("queue full\n");
		return;
	}
	*rear += 1;
	queue[*rear] = data;
}
void dequeue(int *front, int *rear)
{
	if(*front == *rear)
	{
		printf("queue empty\n");
		return;
	}
	*front += 1;
	queue[*front] = -1;
}
void print_queue()
{
	int i;
	for(i=0;i<sizeof(queue)/sizeof(int);i++)
		if(queue[i]!=-1)
			printf("%d->",queue[i]);
	printf("\n");
}
 
int main()
{
	int i, front = -1, rear = -1;
	for(i=0;i<sizeof(queue)/sizeof(int);i++)
		queue[i] = -1;

	for(i=0;i<10;i++)
		enqueue(i,&rear);
	print_queue();

	for(i=0;i<5;i++)
		dequeue(&front,&rear);
	print_queue();

	for(i=0;i<10;i++)
		enqueue(i,&rear);
	print_queue();
    return 0;
}

링크드 리스트를 이용한 큐 구현.

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

struct queue {
	queue* link;
    int data;
};
struct head {
	queue* front;
	queue* rear;
};

void enqueue(head* q, int data)
{
	queue *newitem = (queue *)malloc(sizeof(queue));
	queue *temp = q->front;
	if(q->front==NULL)
		q->front = newitem;
	else
	{
		while(temp->link!=NULL)
			temp = temp->link;
		temp->link = newitem;
	}
	newitem->data = data;
	newitem->link = NULL;
	q->rear = newitem;
}
void dequeue(head* q)
{
	queue *temp = q->front->link;
	free(q->front);
	q->front = temp;
}
void print_queue(head *q)
{
	queue *temp = q->front;
	while(temp->link!=NULL)
	{
		printf("%d->",temp->data);
		temp = temp->link;
	}
	printf("%d\n",temp->data);
}
void deletequeue(head *h)
{
	queue *temp = h->front;
	queue *remove;
	while(temp->link!=NULL)
	{
		remove = temp;
		temp = temp->link;
		free(remove);
	}
	free(h);
	free(temp);
}

int main()
{
	head *h = (head *)malloc(sizeof(head));
	h->front = h->rear = NULL;
	int i;
	for(i=0;i<10;i++) //큐에 0~9까지 10개 집어넣음
		enqueue(h,i);
	print_queue(h); //출력

	for(i=0;i<5;i++) //5개 dequeue함.
		dequeue(h);
	print_queue(h); //출력

	for(i=0;i<5;i++) //5개 다시 넣음.
		enqueue(h,i);
	print_queue(h); //출력

	deletequeue(h);
    return 0;
}