数据结构C-栈（五）

//
//  main.c
//  Stack
//
//  Created by 季晓东 on 2019/1/18.
//  Copyright © 2019 季晓东. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

//定bool类型的值true|false
#define true 1
#define false 0

#define EXIT -1
#define ZERO 0

//自定义bool数据类型
typedef int bool;

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Stack {
    Node *node;
    Node *top;
    int size;
} Stack;


//----------------------------------------------函数声明----------------------------------------------------------------
//自定义错误提示
void error(char* msg);

//自定义警告提示
void warning(char* msg);

//初始化
void init(Stack *stack);

//获得栈的长度
int getSize(Stack *stack);

//判断stack是否为空
bool isEmpty(Stack *stack);

//入栈
void push(Stack *stack, int e);

//出栈
int pop(Stack *stack);

//查看栈顶元素
int peek(Stack *stack);

//是否包含某元素
bool contains(Stack *stack, int e);

//显示信息
void show(Stack *stack);

//----------------------------------------------函数实现----------------------------------------------------------------

void error(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("ERROR: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

void warning(char* msg) {
    printf("\n---------------------------------------------------------------------------\n");
    printf("WARNING: %s", msg);
    printf("\n---------------------------------------------------------------------------\n\n");
}

void init(Stack *stack) {
    Node *dummyHead = (Node *)malloc(sizeof(Node));
    stack->top = (Node *)malloc(sizeof(Node));
    if (stack == NULL && stack->top != NULL) {
        error("Stack memory allocation failed.");
        exit(EXIT);
    }
    
    dummyHead->next= NULL;
    stack->top = dummyHead;
    stack->node = dummyHead;
}

int getSize(Stack *stack) {
    return stack->size;
}

bool isEmpty(Stack *stack) {
    return stack->size == ZERO;
}

void push(Stack *stack, int e) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = e;
    node->next = NULL;
    
//    Node *cur = stack->top;
    //  时间复杂度O(n)
//    for (int i=0; i<stack->size; i++) {
//        cur = cur->next;
//    }
    
//    时间复杂度O(1)
    stack->top->next = node;
    stack->top = node;
    stack->size++;
}

int pop(Stack *stack) {
    //  时间复杂度O(n)，若采用双向链表时间复杂度为O(1)
    Node *prev = stack->node;
    for (int i=0; i<stack->size-1; i++) {
        prev = prev->next;
    }
    Node *delNode = prev->next;
    prev->next = delNode->next;
    stack->top = prev;
    stack->size--;
    return delNode->data;
}

int peek(Stack *stack) {
//  时间复杂度O(n)
//    Node *top = stack->node;
//    for (int i=0; i<stack->size; i++) {
//        top = top->next;
//    }
//    return top->data;
    
//    时间复杂度O(1)
    return stack->top->data;
}

bool contains(Stack *stack, int e) {
    Node *cur = stack->node->next;
    while (cur != NULL) {
        if (e == cur->data) {
            return true;
        }
        cur = cur->next;
    }
    return false;
}

void show(Stack *stack) {
    printf("Stack: size=%d, ",stack->size);
    Node *node = stack->node->next;
    while (node != NULL) {
        printf("%d->",node->data);
        node = node->next;
    }
    printf("null\n");
}

//----------------------------------------------main函数----------------------------------------------------------------

int main(int argc, const char * argv[]) {
    
    Stack stack;
    
    init(&stack);
    
    push(&stack, 1);
    show(&stack);
    
    push(&stack, 2);
    show(&stack);
    
    pop(&stack);
    show(&stack);
    
    push(&stack, 6);
    show(&stack);
    
    push(&stack, 60);
    show(&stack);
    
    
    printf("peek = %d\n",peek(&stack));
    
    pop(&stack);
    show(&stack);
    
    printf("peek = %d\n",peek(&stack));

    pop(&stack);
    show(&stack);
    
    return 0;
}