スタックC言語実装

スタック(stack)スタックとも呼ばれ、演算が制限された線形テーブルである.その制限は、テーブルの一端でのみ挿入および削除演算を許可することである.この一端はスタックトップと呼ばれ、反対に、他端をスタックボトムと呼ぶ.新しい要素をスタックに挿入することは、スタックトップ要素の上に新しい要素を配置し、新しいスタックトップ要素にすることである.個のスタック削除要素は、スタックまたはバックスタックとも呼ばれ、隣接する要素を新しいスタックトップ要素にするためにスタックトップ要素を削除します.
一、スタックの配列実現
スタックのシーケンスストレージ構造は、通常、1次元配列と、スタックトップ要素の位置を記録する変数から構成される.

//       
#include 
#include 

#define ElementType int //         
#define MAXSIZE 1024 //           
#define ERROR -99 //ElementType    ，    

//                                  
typedef struct {
    ElementType data[MAXSIZE];
    int top;
}Stack;

//    
Stack* InitStack() {
    Stack* stack;
    stack = (Stack*)malloc(sizeof(Stack));
    if (!stack) {
        printf("    
");
        return NULL;
    }
    stack->top = -1;
    return stack;
}

int IsFull(Stack* stack) {
    if (stack->top == MAXSIZE - 1) {
        printf("    
");
        return 1;
    }
    return 0;
}

int IsEmpty(Stack* stack) {
    if (stack->top == -1) {
        printf("   
");
        return 1;
    }
    return 0;
}

//  
void Push(Stack* stack, ElementType item) {
    if (IsFull(stack)) {
        return;
    }
    stack->data[++stack->top] = item;
}

//  
ElementType Pop(Stack* stack) {
    if (IsEmpty(stack)) {
        return ERROR;
    }
    return stack->data[stack->top--];
}

void PrintStack(Stack* stack) {
    printf("       :
");
    int i;
    for (i = stack->top; i >= 0; i--) {
        printf("%d
", stack->data[i]);
    }
}


int main(int argc, const char * argv[]) {
    Stack* stack;
    stack = InitStack();
 
    Push(stack, 1);
    Push(stack, 2);
    Push(stack, 3);
    Push(stack, 4);
    Push(stack, 5);
    
    PrintStack(stack);
    
    Pop(stack);
    Pop(stack);
    
    PrintStack(stack);
    
    return 0;
}

二、スタックのチェーンテーブル実現
スタックのチェーンストレージ構造は、実際にはチェーンスタックと呼ばれる単一のチェーンテーブルであり、挿入および削除操作はチェーンスタックのスタックの上部でのみ行われます.あのスタックトップポインタTopはチェーンテーブルのどちらにあるべきですか?私たちは挿入削除操作をしなければなりません.チェーンヘッドで操作しやすいのは明らかです.

#include 
#include 

#define ElementType int
#define ERROR -99

typedef struct Node {
    ElementType data;
    struct Node* next;
}LinkStack;

//     
LinkStack* InitLinkStack() {
    LinkStack* s;
    s = (LinkStack*)malloc(sizeof(LinkStack));
    if (!s) {
        printf("    
");
    }
    s->next = NULL;
    return s;
}

int IsEmpty(LinkStack* s) {
    return (s->next == NULL);
}

void Push(LinkStack* s, ElementType data) {
    LinkStack* cell;
    cell = (LinkStack*)malloc(sizeof(LinkStack));
    if (!cell) {
        printf("    
");
    }
    cell->data = data;
    cell->next = s->next;
    s->next = cell;
}

ElementType Pop(LinkStack* s) {
    LinkStack* firstCell;
    ElementType topData;
    if (IsEmpty(s)) {
        printf("  
");
        return ERROR;
    }
    firstCell = s->next;
    s->next = firstCell->next;
    topData = firstCell->data;
    free(firstCell);
    return topData;
}

void PrintLinkStack(LinkStack* s) {
    printf("       :
");
    LinkStack* p;
    p = s;
    while (p->next != NULL) {
        p = p->next;
        printf("%d
",p->data);
    }
}

int main(int argc, const char * argv[]) {
    LinkStack* s;
    s = InitLinkStack();
    Pop(s);
    
    Push(s, 1);
    Push(s, 2);
    Push(s, 3);
    Push(s, 4);
    Push(s, 5);
    
    PrintLinkStack(s);
    
    Pop(s);
    Pop(s);
    
    PrintLinkStack(s);
    
    return 0;
}