栈的顺序存储及实现（一）-蒲公英云

栈的顺序存储及实现（一）

继续学习数据结构，今天我们来学习栈的相关知识。其实学习没有捷径，如果抱着一种吃快餐的态度进行学习，那是学不到东西，各种技术都是浅尝辄止，那注定学习是不会有太大的效果。不知道你们讨不讨厌某某语言从入门到精通的这类书籍？我在想，有这么牛逼么，一本书直接都从入门到精通了，只不是吸引那些初学者的鳌头吧了。算法都是老前辈们留下来解决某一类问题非常行之有效的方法，不管什么时候都不会过时。虽然很多算法，在很多书上或者网上都有，但是我们得自己去敲一遍，才能有所收获。

不扯了，首先我们来看一下栈的相关定义。

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又被称为后进先出（LastIn First Out）的线性表，简称LIOF结构。

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。

它的特殊之出在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这使得：栈底是固定的，最先进栈的只能在栈底。

栈的插入叫进栈也称压栈、入栈。

栈的删除叫出栈，也称弹栈。

当然压栈和出栈是栈最重要的算法。

实际上栈在程序中用的是特别多的，比如浏览器的前进后退，文档的撤销操作等都是用的栈的方式。

接下来我们用数组也就是顺序存储结构来实现栈的相关算法。

下面是我们栈的数据结构

typedef struct SeqStack {
EleType data[MAXSIZE];//存储栈数据
int top;//栈顶位置
}SeqStack;

进栈操作：

栈未满的情况下，插入元素为新的栈顶，栈顶指针相应加1。

Center

出栈操作：

若栈不为空，则删除stack的栈顶元素，栈顶减一，返回删除元素值。

当为栈空时 top=-1。

下面通过代码来实现栈的相关算法实现。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <math.h>
#include <stdlib.h>
#define MAXSIZE 100
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int EleType;
//顺序存储结构的栈的数据结构
typedef struct SeqStack {
    EleType data[MAXSIZE];//存储栈数据
    int top;//栈顶位置
}SeqStack;
/*
初始化链表，直接将栈顶置为-1，就代表，栈内所有位置可用。
*/
int initStack(SeqStack* stack) {
    if (NULL == stack) {
        return ERROR;
    }
    stack->top = -1;
    return OK ;
}
/*
压栈，很简单，在空间允许情况下往栈顶上面一个位置进行压入元素
*/
int push(SeqStack * stack, EleType e) {
    if (NULL == stack || MAXSIZE == stack->top + 1) {
        return ERROR;
    }
    stack->data[stack->top + 1] = e;
    stack->top++;
    return OK;
}
/*
弹栈，一样的道理，在非空栈中弹出元素，通过指针将元素值进行返回。
*/
void pop(SeqStack* stack, EleType* e)
{
    if (NULL == stack || NULL == e || stack->top == -1) {
        return ERROR;
    }
    *e = stack->data[stack->top];
    stack->top--;
    return OK;
}
/*
从栈顶向下展示元素值
*/
void showStack(SeqStack* stack) {
    if (NULL == stack||stack->top==-1) {
        return;
    }
    int i = stack->top;
    for (; i >=0; i--)
    {
        printf("%d\n", stack->data[i]);
    }
    return;
}
/*
清空栈
*/
int clearStack(SeqStack* stack) {
    if (NULL == stack) {
        return ERROR;
    }
    stack->top = -1;
    return OK;
}
/*
判断栈是否为空
*/
int stackEmpty(SeqStack* stack) {
    if (NULL == stack) {
        return ERROR;
    }
    if (stack->top == -1) {
        return TRUE;
    }
    return FALSE;
}
int getTop(SeqStack* stack,EleType *e) {
    if (NULL == stack) {
        return ERROR;
    }
    *e = stack->data[stack->top];
    return OK;
}
/*
栈元素个数
*/
int getStackLength(SeqStack* stack) {
    if (NULL == stack) {
        return ERROR;
    }
    return stack->top + 1;
}
int main(int argc, char *argv[])
{
    SeqStack stack;//创建顺序栈
    initStack(&stack);//初始化
    push(&stack, 5);
    push(&stack, 4);
    push(&stack, 3);
    push(&stack, 2);
    push(&stack, 1);
    printf("压入元素个数%d\n", getStackLength(&stack));
    puts("分别为：");
    showStack(&stack);
    puts("弹出2个元素后：");
    EleType e1,e2;
    pop(&stack, &e1);
    pop(&stack, &e2);
    showStack(&stack);
    printf("弹出元素为:%d,%d\n", e1, e2);
    return 0;
}