선형 표 로 표 시 된 순서 스 택

LinearListstack (선형 테이블 스 택)
github 소스 코드 특징: 1. 데이터 구조의 측면 에서 볼 때 스 택 도 선형 표 이 고 그 특수성 은 스 택 의 기본 적 인 조작 은 선형 표 작업 의 부분 집합 이 며 조작 이 제 한 된 선형 표 이다.그러나 데이터 유형의 측면 에서 볼 때 스 택 은 선형 표 와 크게 다른 두 가지 추상 적 인 데이터 유형 이다.2. 스 택 (stack) 은 표 끝 에 만 삽입 하거나 삭제 하 는 선형 표 로 한정 되 어 있 기 때문에 스 택 의 경우 표 끝 에 특별한 의 미 를 가지 고 스 택 지붕 (top) 이 라 고 부 르 고 표 끝 을 스 택 바닥 (bottom) 이 라 고 부른다.3. 스 택 의 수정 은 후진 선 출 의 원칙 에 따라 이 루어 지기 때문에 스 택 은 후진 선 출 (Last in First out) 의 선형 표 (LIFO 구조 로 약칭) 라 고도 부른다.4. 선형 표 와 유사 하고 스 택 에 도 두 가지 저장 표시 방법 이 있 으 며 순서 스 택 과 체인 스 택 이 있다.순서 스 택, 즉 스 택 의 순서 저장 구 조 는 한 그룹의 주소 연속 저장 부 를 이용 하여 스 택 밑 에서 스 택 꼭대기 까지 의 데이터 요 소 를 순서대로 저장 하 는 동시에 포인터 top 을 설치 하여 스 택 꼭대기 요소 가 순서 스 택 에 있 는 위 치 를 표시 합 니 다.5. 스 택 을 사용 하 는 과정 에서 필요 한 최대 공간의 크기 를 예측 하기 어렵 기 때문에 일반적인 상황 에서 빈 스 택 을 초기 화 할 때 스 택 의 최대 용량 을 제한 해 서 는 안 됩 니 다.순서 창고 에 대해 비교적 합 리 적 인 방법 은 먼저 순서 창고 에 기본 용량 을 분배 한 다음 에 응용 과정 에서 창고 의 공간 이 충분 하지 않 을 때 점차적으로 확대 하 는 것 이다.이 를 위해, 상수 두 개 를 설정 할 수 있 습 니 다: STACKINIT_SIZE (저장 공간 초기 분 배 량) 와 STACKINCREMENT (저장 공간 분 배 량 증가).
LinearListStack. c 파일

#include 
#include 
#include "LinearListStack.h"
//    

static void clear(LinearListStack *This);
static int isEmpty(LinearListStack *This);
static int length(LinearListStack *This);
static void risePrint(LinearListStack *This);
static void downPrint(LinearListStack *This);
static int getTop(LinearListStack *This,ElemType* e);
static int push(LinearListStack *This,ElemType* e);
static int pop(LinearListStack *This, ElemType* e);

LinearListStack *InitLinearListStack(){
    LinearListStack *L = (LinearListStack *)malloc(sizeof(LinearListStack));
    LinearListStack_P *p = (LinearListStack_P *)malloc(sizeof(LinearListStack_P));
    p->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    p->top = p->base;
    p->length = 0; //    
    p->size = STACK_INIT_SIZE; //     
    L->This = p;
    L->clear = clear;
    L->isEmpty = isEmpty;
    L->length = length;
    L->risePrint = risePrint;
    L->downPrint = downPrint;
    L->getTop = getTop;
    L->push = push;
    L->pop = pop;
    return L;
}

void DestroyLinearListStack(LinearListStack *L){
    free(L->This);
    free(L);
    L = NULL;
}

static void clear(LinearListStack *This){
    LinearListStack_P *p = This->This;
    p->top = p->base;
    p->length = 0; //    
}

static int isEmpty(LinearListStack *This){
    LinearListStack_P *p = This->This;
    return (p->length == 0);
}

static int length(LinearListStack *This){
    LinearListStack_P *p = This->This;
    return p->length;
}

static void risePrint(LinearListStack *This){
    LinearListStack_P *p = This->This;
    int i;
    for (i=0; i < p->length; i++){
        printf("%c", *(p->base + i));
    }
    printf("
");
}

static void downPrint(LinearListStack *This){
    LinearListStack_P *p = This->This;
    int i;
    for (i=0; i < p->length; i++){
        printf("%c", *(p->top - 1 - i));
    }
    printf("
");
}

static int getTop(LinearListStack *This,ElemType* e){
    LinearListStack_P *p = This->This;
    if (p->top == p->base) return -1;
    *e = *(p->top-1);
    return 0;
}

static int push(LinearListStack *This,ElemType* e){
    LinearListStack_P *p = This->This;
    if (p->top - p->base >= p->size){ //          
        ElemType *newbase = (ElemType *)realloc(p->base, (p->size + STACKINCREMENT)*sizeof(ElemType));
        if (!newbase) return -1;//        
        p->base = newbase;//   
        p->top = p->base + p->size;
        p->size += STACKINCREMENT;//      
    }
    *((p->top)++) = *e;
    ++p->length;
    return 0;
}

static int pop(LinearListStack *This, ElemType* e){
    LinearListStack_P *p = This->This;
    if (p->top == p->base) return -1;
    *e = *(p->top-1);
    p->top--;
    p->length--;
    return 0;
}

LinearListstack. h 파일

/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef __LINEARLISTSTACK_H
#define __LINEARLISTSTACK_H
/* Includes ------------------------------------------------------------------*/
/* Exported types ------------------------------------------------------------*/
typedef char ElemType;

typedef struct LinearListStack_P{
    ElemType *base;  
    ElemType *top;   //    
    int length;      //         
    int size;    //         
}LinearListStack_P;

typedef struct LinearListStack{
    LinearListStack_P *This;  
    void (*clear)(struct LinearListStack *This);
    int (*isEmpty)(struct LinearListStack *This);
    int (*length)(struct LinearListStack *This);
    void (*risePrint)(struct LinearListStack *This);
    void (*downPrint)(struct LinearListStack *This);
    int (*getTop)(struct LinearListStack *This,ElemType* e);
    int (*push)(struct LinearListStack *This,ElemType* e);
    int (*pop)(struct LinearListStack *This, ElemType* e);
}LinearListStack;

/* Exported define -----------------------------------------------------------*/
#define STACK_INIT_SIZE 100 //              
#define STACKINCREMENT 10   //             (           )
/* Exported macro ------------------------------------------------------------*/
LinearListStack *InitLinearListStack();
void DestroyLinearListStack(LinearListStack *L);

#endif

testLinear ListStack. c 파일

#include 
#include 
#include "LinearListStack.h"

int strlen(char *str){
    int i = 0;
    while(*(str+i) != '\0'){
        i++;
    }
    return i;
}

int main(void)
{
    int i;
    char string[] = "abcdefgh";
    int strlength = strlen(string);
    ElemType elem;
    LinearListStack *stack = InitLinearListStack();
    printf("string length = %d
",strlength);
    printf("stack is empty:%d
",stack->isEmpty(stack));
    for (i = 0; i < strlength; i++){
        stack->push(stack,string+i);
    }
    printf("base to top: 
");
    stack->risePrint(stack);
    printf("top to base: 
");
    stack->downPrint(stack);
    printf("stack is empty:%d
",stack->isEmpty(stack));
    printf("stack length:%d
",stack->length(stack));
    for(i=0;i < strlength; i++){
        stack->getTop(stack,&elem);
        printf("get top elem:%c
",elem);
        stack->pop(stack,&elem);
        printf("pop elem:%c
",elem);
    }
    printf("stack is empty:%d
",stack->isEmpty(stack));
    printf("stack length:%d
",stack->length(stack));
    stack->clear(stack);
    DestroyLinearListStack(stack);
    return 0;
}

컴 파일:

gcc LinearListStack.c LinearListStack.h testLinearListStack.c -o testLinearListStack

testLinear Liststack 출력 실행:

string length = 8
stack is empty:1
base to top:
abcdefgh
top to base:
hgfedcba
stack is empty:0
stack length:8
get top elem:h
pop elem:h
get top elem:g
pop elem:g
get top elem:f
pop elem:f
get top elem:e
pop elem:e
get top elem:d
pop elem:d
get top elem:c
pop elem:c
get top elem:b
pop elem:b
get top elem:a
pop elem:a
stack is empty:1
stack length:0