[C][강의요약] 스택의 구현 (3)

https://youtu.be/PQHnuPnfqgU

 

// stackADT.h
#ifndef STACKADT_H
#define STACKADT_H

#include <stdbool.h> /* C99 only */

typedef int Item;

typedef struct stack_type *Stack;

Stack create();
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
void push(Stack s, Item i);
Item pop(Stack s);
Item peek(Stack s);

#endif

 

// stackADT.c
#include <stdio.h>
#include <stdlib.h>
#include "stackADT.h"

#define INIT_CAPACITY 100

struct stack_type {
	Item *contents;
    int top;
    int size;
}

static void terminate(const char *message)
{
	printf("%s\n", message);
    exit(1);
}

void push(Stack s, Item i)
{
	if (is_full(s))
    	reallocate(s);
    s->top++;
    s->contents[s->top] = i;
}

Item pop(Stack s)
{
	if (is_empty(s))
    	terminate("Error in pop: stack is empty.");
    s->top--;
    return s->contents[s->top+1];
}

Stack create()
{
	Stack s = (Stack)malloc(sizeof(struct stack_type));
    if (s == NULL)
    	terminate("Error in create: stack could not be created.");
    s->contetns = (Item *)malloc(INIT_CAPACITY * sizeof(Itme));
    if (s->contents == NULL)
    {
    	free(s);
        terminate("Error in create: stack could not be created.");
    }
    s->top = -1;
    s->size = INIT_CAPACITY;
    return s;
}

void destroy(Stack s)
{
	free(s->contents);
    free(s);
}

void make_empty(Stack s)
{
	s->top = -1;
}

bool is_empty(Stack s)
{
	return s->top == -1;
}

void reallocate(Stack s)
{
	Item *tmp = (Item *)malloc(2 * s->size * sizeof(Itme));
    if (tmp == NULL)
    {
    	terminate("Error in create: stack could not be created.");
    }
    for (int i = 0; i < s->size; i++)
    {
    	tmp[i] = s->contents[i];
    }
    free(s->contents);
    s->contents = tmp;
    s->size *= 2;
}

 

// 사용 예
#include "stackADT.h"

int main()
{
	Stack s1 = create();
    Stack s2 = create();
    
    push(s1, 12);
    push(s2, 9);
}

 

 

 

연결 리스트로 구현

 

동일한 헤더 파일 사용

//stackADT.c

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

struct node {
	Item data;
    struct node *next;
};

struct stack_type {
	struct node *top;
};

static void terminate (const char *message)
{
	printf("%s\n", message);
    exit(EXIT_FAILURE);
}

Stack create()
{
	Stack s = (Stack)malloc(sizeof(struct stack_type));
    if (s == NULL)
    	terminate("Error in create: stack could not be created.");
    s->top = NULL;
    return s;
}

void destroy(Stack s)
{
	make_empty(s);
    free(s);
}

void make_empty(Stack s)
{
	while (!is_empty(s))
    	pop(s);
}

bool is_empty(Stack s)
{
	return s->top == NULL;
}

void push(Stack s, Item i)
{
	struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL)
    	terminate("Error in push: stack is full.");
        
    new_node->data = i;
    new_node->next = s->top;
    s->top = new_node;
}