栈

数据结构

栈基础实现

定义

#include<iostream>
#include<cstdlib>
#define ElemType int 
using namespace std ;
int i ;

typedef struct{
    ElemType *arr ;
    int size ;
    int top ;
}Stack ;

栈初始化

void init_Stack(Stack* s,int num){
    s->arr = (int*)malloc(sizeof(int)*num) ;
    s->size = num ;
    s->top = -1 ;// 0 ~ num-1 计数
    for(int i=0; i<s->size; i++){
        scanf("%d",&(s->arr[i])) ;
        s->top ++ ;
    }
    printf(" top => %d\n",s->arr[s->top]) ;
}

入栈出栈

void push_Stack(Stack* s,int elem){
    if(s->top == s->size){
        s->arr = (ElemType *)realloc(s->arr,(s->size+1)*sizeof(ElemType));
        if(!s->arr) return ;
        s->size++;
    }
    s->top++ ;
    s->arr[s->top] = elem ;
}

int pop_Stack(Stack* s){
    if(s->top == -1){
        printf("Stack Empty !\n") ;
        return -1 ;
    }
    
    int elem = s->arr[s->top] ;
    s->top -- ;
    return elem ;
}

获取栈顶元素

int peek_Stack(Stack* s){
    if(s->top == -1){
        printf("Stack Empty !\n") ;
        return -1 ;
    }
    return  s->arr[s->top] ;
}

打印栈

void Print_Stack(Stack* s){
    if(s->top == -1) {
        printf("Stack is empty!\n");
        return;
    }
    for(int i=s->top; i>=0 ;i--)
        printf("%d ",s->arr[s->top-i]) ;
    printf("\n") ;
}

获取栈元素个数

int get_Stack_Length(Stack* s){
    return s->size ;
}

判断栈空

bool is_Stack_Empty(Stack* s){
    if(s->top == -1) return true ;
    return false ;
}

测试

#include "stack.h"

int main(){
    Stack* s = (Stack*)malloc(sizeof(Stack));
    /*
    	一定要为栈申请空间，否则就是空指针
    */ 
    init_Stack(s,6) ;
    push_Stack(s,7) ;
    int elem = pop_Stack(s) ;
    Print_Stack(s) ;
    printf("%d \n",elem) ;
    printf("Stack_Length = %d\n", get_Stack_Length(s)) ;
    int p = peek_Stack(s) ;
    printf("peek = %d \n",p) ;
    Print_Stack(s) ;
    
    return 0 ;
}

链栈

定义

#include<iostream>
#include<cstdlib>
#define ElemType int
using namespace std ;

typedef struct node{
    ElemType val ;
    struct node* next ;

}Link_Stack;

初始化链栈

void init_Link_Stack(Link_Stack* s, int num){
    Link_Stack* cur = s ;
    s->val = 65535 ;
    s->next= nullptr ;
    for(int i=0; i<num; i++){
        Link_Stack* newElem = (Link_Stack*)malloc(sizeof(Link_Stack)) ;
        cur->next = newElem ;
        cur = cur->next ;
        printf("please input val : \n") ;
        int v ;
        scanf("%d",&v) ;
        newElem->val = v ;
        newElem->next = nullptr ;
        printf("cur->val = %d\n",cur->val) ;
    }
}

入栈出栈

void push_Link_Stack(Link_Stack* s, ElemType v){
    Link_Stack* cur = s ;
    while(cur->next){    
        cur = cur->next ;
    }
    Link_Stack* newNode = (Link_Stack*)malloc(sizeof(Link_Stack)) ;
    newNode->val = v ;
    newNode->next = nullptr ;
    cur->next = newNode ;
}

ElemType pop_Link_Stack(Link_Stack* s){
    Link_Stack* cur = s->next ;
    while(cur->next->next){
        cur = cur->next ;
    }
    Link_Stack* elem = cur->next ;// 尾端就是elem
    int m = elem->val ;
    cur->next = nullptr ;
    free(elem) ;
    return m ;
}

打印链栈

void Print_Link_Stack(Link_Stack* s, int num){
    Link_Stack* cur = s->next ;
    while(cur){
        if(cur->next == nullptr) printf(" %d \n",cur->val) ;
        else printf(" %d -> ",cur->val) ;
        cur = cur->next ;
    }
}