顺序栈

定义：栈是限定仅在表尾进行插入和删除操作的线性表。特点：先进后出(First in Last out)，或者叫后进先出表。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

数据结构

typedef int ElemType;
#define MaxSize 50//定义栈中元素的最大个数
typedef struct SqStack {
    ElemType data[MaxSize];//存放战中元素
    int top;//栈顶元素
}SqStack, *stack;

方案一：
栈空间范围为S[0, MaxSize-1];
栈顶指针指向顶元素所在的位置

stack.png

(a) 非空栈top>=0，顶元素=s[top]；
(b) 进栈，先对top+1，指向下一空位置，将新数据输入top指向的位置，完成进栈操作，结束时top指向新栈顶元素的位置；
(c) 出栈，先根据top指向取出栈顶数据元素，再对top-1完成出栈操作，结束时top指向去掉原栈顶的元素后的新栈顶元素所在位置；
(d) 栈满条件，top= MaxSize-1，若插入元素，将发生溢出，overflow；
(e) 栈空条件，top=-1，若删除元素，将发生“下溢”。

//初始化
void InitStack(stack s) {
    s->top = -1;//初始化栈顶指针
}

//判断栈空
int StackEmpty(SqStack s) {
    if (s.top == -1) {
        printf("空栈...\n");
        return 0;
    }
    else
        return 1;
}

//进栈
int Push(stack s, ElemType data) {
    if (s->top == MaxSize-1) {
        printf("栈满...\n");
        return 1;
    }
    s->data[++s->top] = data;
    return 0;
}

//出栈
int PopStack(stack s) {
    if (s->top == -1) {
        printf("空栈...\n");
        return 1;
    }
    int data = s->data[s->top--];
    return data;
}

//读取栈顶元素
int GetTop(stack s) {
    if (s->top == -1) {
        printf("空栈...\n");
        return 1;
    }
    int data = s->data[s->top];
    return data;
}

//销毁栈
void destory(stack s) {
    s->top = -1;
    memset(s->data, 0, sizeof(s->data));
}

//十进制转换为二进制
void ten_to_two(stack s, int ten) {
    int tmp = ten;
    if (ten < 0) { //将负数变成正数，同时前面加负号
        ten = ~ten + 1;
        printf("-");
    }
    if (ten == 0) {
        Push(s, ten);
    }
    else {
        while (ten) {
            tmp = ten % 2;
            Push(s, tmp);
            ten = ten / 2;
        }
    }
}

//测试
void testStack() {
    SqStack S;
    stack s = &S;
    InitStack(s);
//    Push(s, 23);
//    printf("%d\n", GetTop(s));
    int ret;;
    ten_to_two(s, 4);
    printf("4=");
    while((ret = PopStack(s)) >= 0){
        printf("%d", ret);
    }
    printf("\n");
}

方案二：
栈空间范围为S[0, MaxSize-1];
栈顶指针指向顶元素上一个空的位置

stack.png

(a) 非空栈top>=1，顶元素=s[top-1]；
(b) 进栈，先将新数据输入top指向的位置，再对top+1，指向下一空位置，完成进栈操作，结束时top正好指向新栈顶位置的上一空位置；
(c) 出栈，先对top-1，再根据top指向取出栈顶数据元素，完成出栈操作，结束时top指向去掉原栈顶的元素后的新栈顶元素所在位置的上一空位置；
(d) 栈满条件，top= MaxSize，若插入元素，将发生溢出，overflow；
(e) 栈空条件，top=0，若删除元素，将发生“下溢”。

//初始化，这里吧top=0设置为空栈，栈满的条件为top=maxsize
void init_stack(stack s) {
    s->top = 0;
}

//判断栈空
int empty_stack(SqStack s) {
    if (s.top == 0) {
        printf("空栈...\n");
        return 0;
    }
    else {
        printf("非空栈...\n");
        return -1;
    }
}

//入栈
int push_stack(stack s, ElemType data) {
    if (s->top == MaxSize) {
        printf("栈满...\n");
        return -1;
    }
    s->data[s->top++] = data;
    return 0;
}

//出栈
int pop_stack(stack s) {
    if (s->top == 0) {
        printf("空栈...\n");
        return -1;
    }
    int data = s->data[--s->top];
    return data;
}

//获取栈顶元素
int get_stack(stack s) {
    if (s->top == 0) {
        printf("空栈...\n");
        return -1;
    }
    int top = s->top-1;
    int data = s->data[top];
    return data;
}

//销毁栈
void destory_stack(stack s) {
    s->top = 0;
    memset(s->data, 0, sizeof(s->data));
}
//十进制转换为八进制
void ten_to_eight(stack s, ElemType ten) {
    int tmp;
    while (ten) {
        tmp = ten % 8;
        push_stack(s, tmp);
        ten = ten / 8;
    }
}
//测试
void test_stack() {
    SqStack S;
    stack s = &S;
    init_stack(s);
    int ret;
//    empty_stack(S);
//    push_stack(s, 23);
//    push_stack(s, 45);
//    push_stack(s, 90);
//    printf("%d\n", get_stack(s));
//    printf("%d\n", pop_stack(s));
//    printf("%d\n", get_stack(s));
//    empty_stack(S);
    ten_to_eight(s, 16);
    printf("4=");
    while ((ret=pop_stack(s)) >= 0) {
        printf("%d", ret);
    }
    printf("\n");
}

数据结构

推荐阅读更多精彩内容