본문 바로가기
PS/자료구조

여러개의 스택 구현

by 노아론 2018. 1. 15.
스택 구현

스택, 배열로 구현

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
#define INIT_CAPACITY 100

typedef int Item;
typedef struct stack_type *Stack;

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


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

static void terminate(const char* message)
{
    printf("%s\n",message);
    exit(1);
}
Stack create()
{
    Stack s = (Stack)malloc(sizeof(sizeof(struct stack_type)));
    if(s==NULL)
    {
        terminate("Error in create: stack could not be created");

    }
    s->contents=(Item*)malloc(INIT_CAPACITY*sizeof(Item));
    if(s->contents==NULL)
    {
        free(s);
        terminate("Error in create: stack coud 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;
}
bool is_full(Stack s)
{
    return s->top==s->size-1;
}
void push(Stack s,Item item)
{
    if(is_full(s))
    {
        reallocate(s);
    }
    s->contents[s->top]=item;
}
Item pop(Stack s)
{
    if(is_empty(s))
        terminate("Error in popL stack is empty");
    s->top--;
    return s->contents[s->top+1];
}
Item peek(Stack s)
{
    if(is_empty(s))
        terminate("Error in peek: stack is empty");
    return s->contents[s->top];
}
void reallocate(Stack s)
{
    Item *tmp=(Item*)malloc(2*s->size*sizeof(Item));
    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;
}
int main()
{
    Stack s1=create();
    Stack s2=create();

    push(s1,2);
    push(s2,3);
}

스택, 연결리스트 구현

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
#define INIT_CAPACITY 100

typedef int Item;
typedef struct stack_type *Stack;

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

//top은 노드 좌측
struct node{
    Item data;
    struct node* next;
};
struct stack_type
{
    struct node* top;
};

static void terminate(const char* message)
{
    printf("%s\n",message);
    exit(1);
}
Stack create()
{
    Stack s = (Stack)malloc(sizeof(sizeof(struct stack_type)));
    if(s==NULL)
    {
        terminate("Error in create: stack could not be created");

    }
    s->top=NULL;
    //s->top이 NULL이기에 s->top->next는 건들지X
    return s;
}
void destroy(Stack s) //필요없어서 없애는것.
{
    free(s);
}
void make_empty(Stack s)//비우는것
{
    while(!is_empty(s))
        pop(s);
}
bool is_empty(Stack s)
{
    return s->top ==NULL;
}
//is_full 이 없다.
void push(Stack s,Item item)
{
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    if(new_node==NULL)
        terminate("Error in push: stack is full");
    new_node->data=item;
    new_node->next=s->top;
    s->top=new_node;
}
Item pop(Stack s)
{
    if(is_empty(s))
        terminate("Error in popL stack is empty");
    Item old_node = s->top->data;
    s->top=s->top->next;

    return old_node;
}
Item peek(Stack s)
{
    if(is_empty(s))
        terminate("Error in peek: stack is empty");
    return s->top->data;
}
// reallocate 는 필요x
int main()
{
    Stack s1=create();
    Stack s2=create();

    push(s1,2);
    push(s2,3);
}

댓글0