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

스택, 배열|링크드리스트 구현과 문제점

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

스택, 배열로 구현

#include <stack>
#define MAX_CAPACITY 100

void push(char);
char pop();
char peek();
int is_empty();
int is_full();


char stack[MAX_CAPACITY];
int top=-1;

void push(char ch)
{
    if(is_full())   //스택이 가득차면 push 불가, 이때의 경우를 알수있게 해야함
    {
        return;
    }
    top++;
    stack[top]=ch;
}
char pop()          //스택이 비어있는지 검사할것
{
    if(top==-1)
    {
        return NULL;
    }
    char tmp=stack[top];
    top--;
    return tmp;
}
char peek()     //pop과는 다르다. 비우지않고 반환만 함
{
    return stack[top];
}
int is_empty()
{
    return top==-1;
}
int is_full()
{
    return top==MAX_CAPACITY-1;
}



# 스택, 링크드리스트로 구현
#include <stdio.h>
#include <malloc.h>

typedef struct node {
    char* data;
    struct node* next;
}Node;

Node* top = NULL;
//가장 왼쪽 노드를 탑으로 둠
void push(char* item)
{
    Node* p =(Node*)malloc(sizeof(Node));
    p->data=item;
    p->next=top;
    top=p;
}
char* pop()
{
    if(is_empty())
    {
        return NULL;
    }
    char* data = top->data;

    free(top);
    top=top->next;

    return data;
}
char* peek()
{
    if(is_empty())
    {
        return NULL;
    }
    return top->data;
}
int is_empty()
{
    return top==NULL;
}

위와 같은 코드에서 나오는 문제점

스택이 2개일때 코드를 중복으로 적어야함.

노드의 data 타입이 다를때 template과 같은 기능을 사용하지 못함.

댓글0