Stack - 배열,연결리스트,원형연결리스트

 

- 스택은 데이터를 한 쪽 끝에서만 넣거나 뺄 수 있는 자료구조이다.

 

출처: https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

-장/단점

장점: 구현이 쉽다, 데이터 저장 및 읽기 속도가 빠르다.

단점: 저장 공간 낭비, 데이터의 최대 갯수를 미리 지정해야함 

*이는 스택의 장점을 최대한 활용하기 위해 배열기반으로 스택이 구현 되므로 발생하는 단점이다.

 

-활용

컴퓨터 프로그램에서 함수를 부를 때 스택을 사용한다 > 순차적으로 읽으며, 가장 먼저 호출됨 함수가 가장 먼저 실행

                                                                                      > 위와 같이 함수 정보를 저장하는 스택을 콜스택이라고 함

재귀함수 또한 가장 마지막에 호출된 함수를 가장 먼저 실행하므로 스택의 구조로 구현된다고 볼 수 있다.

 

 

-구현 

 

>배열 기반 스택

헤더

#ifndef _St_Array

#define _St_Array

#define MAX_DATA 100

typedef int Sdata;

typedef struct _Stack{

    Sdata arr[MAX_DATA];

    int index;

}StackArray;

typedef StackArray Stack;

void StackInit(Stack* st);

int isEmpty(Stack* st);

void push(Stack* st, Sdata data);

Sdata pop(Stack* st);

Sdata peek(Stack* st);

int size(Stack* st);

#endif

소스

#include<stdio.h>

#include"St.h"

void StackInit(Stack* st){

    st->index = -1;

}

int isEmpty(Stack* st){

    if(st->index == -1) return 1;

    return 0;

}

void push(Stack* st, Sdata data){

    (st->index)++;

    st->arr[st->index] =data;

}

Sdata pop(Stack* st){

    if(isEmpty(st)){

        printf("스택 메모리 에라\n");

        exit(-1);

        }

    int rpos = st->index;

    (st->index)--;

    return st->arr[rpos];

}

Sdata peek(Stack* st){

    if(isEmpty(st)){

        printf("스택 메모리 에라\n");

        exit(-1);

    }

    return st->arr[st->index];

}

int size(Stack* st){

    return len(st->arr);

}

 

>단방향 연결리스트 기반

 

헤더 

#ifndef _Stack_linked

#define _Stack_linked

typedef int Data;

typedef struct _node{

    Data data;

    struct _node* next;

}node;

typedef struct _stLinked{

    node* head;

    int len;

}stLinked;

typedef stLinked Stack;

void stinit(Stack* st);

int isEmpth(Stack* st);

void push(Stack* st,Data data);

Data pop(Stack* st);

Data peek(Stack* st);

#endif

소스

#include <stdio.h>

#include <stdlib.h>

#include"StLinked.h"

void stinit(Stack* st){

    st->head =NULL;

}

int isEmpth(Stack* st){

    if(st->head == NULL) return 1;

    return 0;

}

void push(Stack* st,Data data){

    node* newnode = (node*)malloc(sizeof(node));

    newnode->data =data;

    newnode -> next = st->head;

    st->head = newnode;

}

Data pop(Stack* st){

    if(isEmpty(st)){

        printf("스택 메모리 오류");

        exit(-1);

    }

    node* rnode = st->head;

    Data rdata = st->head->data;

    st->head = st->head->next;

    free(rnode);

    return rdata;

}

Data peek(Stack* st){

    if(isEmpth(st)){

        printf("스택 메모리 오류");

        exit(-1);

    }

    return st->head->data;

}

* 단방향 연결리스트의 경우 head만 필요하다. (어차피 head 혹은 tail 방향으로만 데이터를 넣고 뺀다)

 

>원형 연결리스트 

 

헤더

#include"Circular_LinkedList.h"

typedef int Data;

typedef struct _CStakc{

    List* plist; //LinkedList로 구현하기 전 일단 각 스택별 List를 가지고 있어야함

}CStack;

typedef CStack Stack;

void StackInit(Stack* st);

int itEmpty(Stack* st);

void pust(Stack* st, Data data);

Data pop(Stack* st);

Data peek(Stack* st);

소스

#include<stdio.h>

#include "CStack.h"

#include<stdlib.h>

void StackInit(Stack* st){

    Linit(st->plist);

}

int isEmpty(Stack* st){

    if(st->plist->tail == NULL) return 1;

    return 0;

}

void pust(Stack* st, Data data){

    LinsertFirst(st->plist,data);

}

Data pop(Stack* st){

    Data data;

    if(isEmpty){

        exit(-1);

    }

    LFirst(st->plist,&data);

    LRemove(st->plist);

    return data;

}

Data peek(Stack* st){

    Data data;

    LFirst(st->plist,&data);

    return data;

}

 * 기존에 구현해둔 원형 연결리스트를 가져다가 썼다.

 * 헤더 파일에서 stack를 정의할 때 구조체에 원형연결리스트를 포함시켜둔다 

     - 이는 각 스택마다 하나의 리스트를 가지고 있어야하기 때문

 

 

참고자료:  윤성우 - 열혈자료구조

 

https://laboputer.github.io/ps/2017/09/09/stack/

[자료구조 1] 스택(Stack) 활용하기

https://www.fun-coding.org/Chapter06-stack-live.html#gsc.tab=0

잔재미코딩 온라인 강의 사이트입니다