数据结构与算法

2020-04-13  本文已影响0人  只写Bug程序猿

栈是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,允许操作的一端称为栈顶,不允许操作的一端称为栈底, 后进先出,就像一摞盘子,每次将一个个盘子摞在最上边或者从最上面取一只盘子,不能从中间插入或抽出

顺序栈

采用顺序存储结构的栈称为顺序栈

顺序栈的定义
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int */
typedef struct {
    SElemType data[MAXSIZE];
    int top
}Stack;
初始化空顺序栈
Status initStack(Stack *S){
    S->top = -1;
    return OK;
}
清空顺序栈
Status clearStack(Stack *S){
    S->top = -1;
    return OK;
}
顺序栈是否为空
Status stackEmpty(Stack S){
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}
返回顺序栈长度
int stackLength(Stack S){
    return S.top + 1;
}
获取顺序栈顶元素
Status getTop(Stack S,SElemType *e){
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
   
    return OK;
    
}
顺序栈插入元素

插入元素e为新栈顶元素
Status pushData(Stack *S, SElemType e){

//栈已满
if (S->top == MAXSIZE -1) {
    return ERROR;
}

//栈顶指针+1;
S->top ++;
//将新插入的元素赋值给栈顶空间
S->data[S->top] = e;

return OK;

}

删除顺序栈顶元素

删除S栈顶元素,并且用e带回
Status pop(Stack *S,SElemType *e){

//空栈,则返回error;
if (S->top == -1) {
    return ERROR;
}

//将要删除的栈顶元素赋值给e
*e = S->data[S->top];
//栈顶指针--;
S->top--;

return OK;

}

顺序栈的遍历
Status stackTraverse(Stack S){
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

链式栈

采用链式存储结构的栈称为链式栈,采用单链表实现

定义
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定,这里假设为int */
typedef struct{
    SElemType data;
    struct StackNode *next;
}StackNode;
typedef StackNode* ListStackPtr;

typedef struct {
    ListStackPtr top;
    int count;
}ListStack;
链式栈初始化
Status initStack(ListStack *S){
    S->top = NULL;
    S->count = 0;
    return OK;
}
链式栈清空
Status clearStack(ListStack *S){
    ListStackPtr p = S->top;
    ListStackPtr temp;
    while (p) {
        temp = p;
        p = temp->next;
        free(temp);
        
    }
    S->count = 0;
    return OK;
}
链式栈是否为空
Status isEmpty(ListStack S){
    return S.count == 0 ? TRUE : FALSE;
}
链式栈长度
int stackLength(ListStack S){
    return S.count;
}
获取栈顶元素
Status getTop(ListStack *S,SElemType *e){
    if (S.top == NULL) {
        return ERROR;
    }else{
        *e = S.top->data;
    }
    return OK;
}
插入元素
Status push(ListStack *S,SElemType e){
    ListStackPtr temp = malloc(sizeof(StackNode));
    temp->data = e;
    temp->next = S->top;
    S->top = temp;
    S->count++;
    return OK;
}
删除元素
Status pop(ListStack *S, SElemType e){
    ListStackPtr temp;
    if (S->count == 0) {
        return ERROR;
    }
    *e = S->top->data;
    temp = S->top;
    S->top = temp->next;
    free(temp);
    S->count--;
    return OK;
}
遍历链式栈
Status travelStack(ListStack S){
    ListStackPtr temp;
    temp = S.top;
    while (temp) {
        printf(temp->data);.
        printf("\n");
        temp = temp->next;
    }
    return OK;
}
上一篇 下一篇

猜你喜欢

热点阅读