[数据结构]栈的基本操作

顺序栈

1.1顺序栈的定义

/*
   顺序栈基本操作
*/
#include <stdio.h>
#include <stdlib.h>
//定义栈中最大元素的个数.
#define MAXNUM 20
typedef int DataType;
typedef struct SeqStack{
    int t; //栈顶位置指示
    DataType s[MAXNUM];
}SeqStack,*PSeqStack;

//创建一个空栈;为栈结构申请空间.并将栈顶元素变量赋值为－1
PSeqStack createEmptyStack(void);
//判断pastack所指的栈是否为空，当pastack所指的栈为空时返回1;否者为0.
int isEmptyStack(PSeqStack pastack);
//压栈操作
void push_seq(PSeqStack pastack,DataType e);
//出栈操作
void pop_seq(PSeqStack pastack);
//pastack不为空栈时，求栈顶元素
DataType getTop_seq(PSeqStack pastack);

1.2 初始化栈

PSeqStack createEmptyStack(){
    PSeqStack pastack=(PSeqStack)malloc(sizeof(struct SeqStack));
    if (pastack==NULL)
    {
        printf("Error:out of space\n");
    }else{
        pastack->t=-1;
    }

    return pastack;
}

1.3判断栈是否为空

int isEmptyStack(PSeqStack pastack){
    return pastack->t==-1;
}

1.4入栈操作

void push_seq(PSeqStack pastack,DataType e){
    if(pastack->t>=MAXNUM-1){
        printf("Stack Overflow!\n");
    }else{
        pastack->t++;
        pastack->s[pastack->t]=e;
    }
}

1.5出栈操作

void  pop_seq(PSeqStack pastack){
    if (pastack->t==-1)
    {
        printf("UnderFlow!\n");
    }else{
        printf("Pop:%d\n",pastack->s[pastack->t]); 
        pastack->t--;
    }
}

1.6返回栈顶元素

DataType getTop_seq(PSeqStack pastack){

     return pastack->s[pastack->t];
}

1.7测试

int main(){
    PSeqStack stack1=createEmptyStack();
    push_seq(stack1,1);
    push_seq(stack1,2);
    push_seq(stack1,3);
    printf("%d\n",getTop_seq(stack1));
    pop_seq(stack1);
    pop_seq(stack1);
    pop_seq(stack1);

    return 0;
}

链栈

2.1链栈定义

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

typedef int DataType;
struct Node;
typedef struct Node *PNode;

struct Node
{
     DataType info;
     PNode link;

};

struct LinkStack
{
    PNode top;
};
typedef struct LinkStack *PLinkStack;

// 申请链栈结构空间，创建一个空链栈,返回指向空链接的指针.
PLinkStack createEmptyStack_link(void);
// 链式栈是否为空栈
int isEmptyStack_link(PLinkStack plstack);
//入栈
void push(PLinkStack plstack, DataType e);
//出栈
void pop(PLinkStack plstack);
//对非空栈求栈顶元素

2.1初始化栈

PLinkStack createEmptyStack_link(){
    PLinkStack plstack=(PLinkStack)malloc(sizeof(struct LinkStack));
    if (plstack==NULL)
    {
        printf("Out of space\n");
    }else{
        plstack->top=NULL;
    }

    return plstack;
}

2.2判断栈是否为空

int isEmptyStack_link(PLinkStack plstack){
   return plstack->top==NULL;
}

2.3入栈操作

void push(PLinkStack plstack,DataType e){
    PNode newnode=(PNode)malloc(sizeof(struct Node));
    if(newnode==NULL){
      printf("Out of space.\n");
    }else{
      newnode->info=e;
      newnode->link=plstack->top;
      plstack->top=newnode;
    }
}

2.4出栈操作

void pop(PLinkStack plstack){
    if (isEmptyStack_link(plstack))
    {
        printf("Empty Stack pop.\n");
    }else{
        PNode p=plstack->top;
        printf("%d\n",p->info);
        plstack->top=plstack->top->link;
        free(p);
    }
}

2.5测试代码

int main(){
    PLinkStack plstack1=createEmptyStack_link();
    push(plstack1,1);
    push(plstack1,3);
    push(plstack1,5);
    pop(plstack1);
    pop(plstack1);
    pop(plstack1);
    pop(plstack1);

}