스 택 의 배열 구현

배열 과 스 택 의 위 치 를 전역 변수 로 설명 하지 않 는 것 이 좋 습 니 다. 스 택 이 잠재 적 으로 존재 할 수 있 기 때문에 모든 ADT 에 적 용 됩 니 다.하나의 배열 로 스 택 을 실현 하 는 것 은 매우 간단 합 니 다. 모든 스 택 에 하나의 스 택 위 치 를 가지 고 있 습 니 다.하나의 요 소 를 스 택 에 넣 으 려 면 TopOfStack + +, 그리고 S - > Arrar [TopOfStack] = X 만 있 으 면 됩 니 다.스 택 을 나 갈 때 TopOfStack 만 -
배열 이 실 현 된 스 택 에 있어 서 스 택 에 들 어가 거나 스 택 을 나 가 는 것 은 매우 빠 릅 니 다. 어떤 기계 에 서 는 자체 증가 와 자체 주소 지정 기능 을 가 진 레지스터 에서 작업 하면 (정수) push 와 pop 은 모두 기계 명령 으로 쓸 수 있 습 니 다.가장 현대 화 된 컴퓨터 는 스 택 작업 을 명령 시스템 의 일부분 으로 하고 스 택 은 컴퓨터 에서 매우 기본 적 인 데이터 구조 이다.
stack.h

#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

typedef int ElementType;

struct StackRecord;
typedef struct StackRecord *Stack;

int IsEmpty(Stack S);
int IsFull(Stack S);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S); //     
void MakeEmpty(Stack S);	//   
void Push(Stack S, ElementType X);
ElementType Top(Stack S);   //        
void Pop(Stack S);  //  
ElementType TopAndPop(Stack S); //           

#endif // STACK_H_INCLUDED

stack.c

#include"stack.h"
#include"..\fatal.h"
#include
#include

#define EmptyTOS (-1)
#define MinStackSize (5)

struct StackRecord{
     
    int Capacity; //  ,        
    int TopOfStack; //  
    ElementType *Array;	//         
};

int IsEmpty(Stack S){
     
    return S->TopOfStack == EmptyTOS;
};

int IsFull(Stack S){
     
    return S->TopOfStack == S->Capacity - 1;
}

Stack CreateStack(int MaxElements){
     
    Stack S;

    if(MaxElements < MinStackSize)
        Error("Stack Size is too small.");

    S = malloc(sizeof(struct StackRecord));
    if(S == NULL)
        FatalError("Out of Space!!");

    S->Array = malloc(sizeof(ElementType) * MaxElements);
    if(S->Array == NULL)
        FatalError("Out of space!!");

    S->Capacity = MaxElements;
    MakeEmpty(S);

    return S;
}

void MakeEmpty(Stack S){
     
    S->TopOfStack = EmptyTOS;
}

void DisposeStack(Stack S){
     
    if(S != NULL){
     
        free(S->Array);
        free(S);
    }
}

void Push(Stack S, ElementType X){
     
    if(IsFull(S))
        Error("Full Stack");
    else
        S->Array[++S->TopOfStack] = X;
}

void Pop(Stack S){
     
    if(IsEmpty(S))
        Error("Empty Stack");
    else
        S->TopOfStack--;
}

ElementType Top(Stack S){
     
    if(IsEmpty(S))
        Error("Empty Stack");
    else
        return S->Array[S->TopOfStack];
}
ElementType TopAndPop( Stack S )
{
     
    if( !IsEmpty( S ) )
        return S->Array[ S->TopOfStack-- ];
    Error( "Empty stack" );
    return 0;  /* Return value used to avoid warning */
}

int main(){
     
    Stack S = CreateStack(10);
    //  Push（）
    Push(S,1);
    Push(S,2);
    //  Top（）
    printf("%d
",Top(S));
    //  Pop（）
    Pop(S);
    printf("%d
",Top(S));

    DisposeStack(S);
    return 0;
}