새싹교실/2017/따라와반/과제방/자료구조/4회차

오늘의 실습 내용

• • 스택 - 배열, Linked List
  • 큐 - 배열, Linked List
  • 과제방에는 Linked List만 올리면 됨.

신원준

스택

(코드는 여기에)

큐

(코드는 여기에)

이민욱

스택

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct __Node{
    int Data;
    struct __Node* Next;
    struct __Node* Prev;

}Node;

Node* NewNode(int data);
void AddendNode(Node* head, Node* end);
void RemoveNode(Node* head, Node* node);
void DeleteNode(Node* node);
void DestroyNode(Node* head);


void push(Node** head, int data);
int pop(Node** head);
int size(Node* head);
int empty(Node* head);
int top(Node* head);

int main() {
    Node* head=NULL;
    int N, X;
    char str[100];
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%s", str);
        if (!strcmp(str,"push")) {
            scanf("%d", &X);
            push(&head, X);
        }
        else if (!strcmp(str,"pop")) {
            printf("%d\n", pop(&head));
        }
        else if (!strcmp(str,"size")) {
            printf("%d\n", size(head));

        }
        else if (!strcmp(str,"empty")) {
            printf("%d\n", empty(head));
        }
        else if (!strcmp(str,"top")) {
            printf("%d\n", top(head));
        }
    }

    return 0;
}


Node* NewNode(int data){
    Node* tmp=(Node*)malloc(sizeof(Node));
    tmp->Data = data;
    tmp->Next = NULL;
    tmp->Prev = NULL;
    return tmp;
}

void AddendNode(Node* head, Node* end){
    while(head->Next!=NULL){
        head=head->Next;
    }
    head->Next = end;
    if(end!=NULL) end->Prev = head;
}
void RemoveNode(Node* head, Node* node){
    while(head->Next == node){
        head= head->Next;
    }
    head->Next = node->Next;
    node->Next->Prev = head;
    DeleteNode(node);
}
void DeleteNode(Node* node){
    free(node);
}
void DestroyNode(Node* head){
    Node* tmp;
    while(head->Next!=NULL){
        tmp = head;
        head=head->Next;
        DeleteNode(tmp);
    }
}

void push(Node** head, int data) {
    Node* tmp = *head;
    (*head)= NewNode(data);
    AddendNode(*head, tmp);
}
int pop(Node** head){
    if(*head==NULL) return -1;
    int data = (*head)->Data;
    Node* tmp = *head;
    *head=(*head)->Next;
    if(*head!=NULL) (*head)->Prev = NULL;
    DeleteNode(tmp);
    return data;
}
int size(Node* head){
    int count =0;
    while(head!=NULL){
        count++;
        head=head->Next;
    }
    return count;
}
int empty(Node* head){
    if(head==NULL) return 1;
    return 0;
}
int top(Node* head) {
    if(head==NULL) return -1;
    return head->Data;
}

큐

(코드는 여기에)

정석우

스택

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

typedef struct Node
{
	int data;
	struct Node* ptr;
}Node;

Node* stack = NULL;
Node* head = NULL;

void push(int input)
{
	Node* newNode;
	newNode = (Node*)malloc(sizeof(Node));
	newNode->data = input;
	newNode->ptr = head;
	head = newNode;
}

void pop()
{
	Node* topNode = head;
	if (head == NULL)
	{
		printf("-1\n");
	}
	else
	{
		int returnvalue = head->data;
		head = head->ptr;
		free(topNode);
		printf("%d\n", returnvalue);
	}
}

void print_stack()
{
	Node* temp = head;
	if (temp != NULL)
	{
		printf("Stack: ");
		do
		{
			printf("%d ", temp->data);
			temp = temp->ptr;
		} while (temp != NULL);
		printf("\n");
	}
	else
	{
		printf("The Stack is empty\n");
	}
}

void stack_size()
{
	Node* temp = head;
	int cnt = 0;
	while (temp != NULL)
	{
		cnt++;
		temp = temp->ptr;
	}
	printf("%d\n",cnt);
}

void stack_isempty()
{
	if (head == NULL)
	{
		printf("1\n");
	}
	else
	{
		printf("0\n");
	}
}

void stack_top()
{
	if (head != NULL)
	{
		printf("%d\n", head->data);
	}
	else
	{
		printf("-1\n");
	}
}

int main()
{
	int N, i, target;
	char str[12];
	char npush[] = "push";
	char ntop[] = "top";
	char nsize[] = "size";
	char nempty[] = "empty";
	char npop[] = "pop";
	scanf(" %d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%s", str);
		if (!strcmp(str,npush))
		{
			scanf(" %d", &target);
			push(target);
		}
		else if (!strcmp(str,ntop))
		{
			stack_top();
		}
		else if (!strcmp(str,nsize))
		{
			stack_size();
		}
		else if (!strcmp(str,npop))
		{
			pop();
		}
		else if (!strcmp(str,nempty))
		{
			stack_isempty();
		}
	}
	return 0;
}

큐

(코드는 여기에)