Day 7：栈

本文主要是介绍Day 7：栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

栈的原理

        定义：栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈）。

        栈顶：允许进行操作的一端。

        空栈：当栈中没有元素。

        栈底:另一固定端.

        特点：后进先出。（后面进去的元素先出去。如：an）

        核心问题：检查是否出现回路，例如：C0->C5->C6->C7->C0。

        和栈的关系：先把C0、C1（即没有前驱的元素）放入栈，再取出。依次执行上述操作。（第二次没有前驱的元素就是C2、C3。)

        想象成从A地前往D地，到达D地后返回A地的过程。 

顺序栈

        定义

        具有顺序表同样的存储结构，由数组定义，配合用数组下标表示的栈顶指针top（相对指针）完成各种操作。

        栈的实现

                结构体创建

typedef int data_t;
typedef struct
{data_t * date;/*用指针指向栈的存储空间*/int maxlen;	  /*当前栈最大存储元素个数（特点：提供用户可以以参数的形式提供个数）*/int top;	  /*指示栈顶位置的变量（数组下标）*/
}sqstack;

                创建栈

sqstack* stack_create(int maxlen)
{	/*1.malloc sqstack内存空间：存放指向栈的指针，栈顶位置，最大存储个数*/sqstack* s = malloc(sizeof(sqstack));	/*2.malloc data内存空间：存放栈的数据*/s->date = malloc(maxlen*sizeof(data_t));if (s == NULL || s->date == NULL){return NULL;}/*3.初始化*/memset(s->date, 0, maxlen*sizeof(data_t);s->maxlen = maxlen;s->top = -1;return s;
}

                入栈

        整体思路：

        1.检查栈是否满？

        2.top++;

        3.data[top]=value;

stack_push(sqstack* s, data_t value)
{/*检查栈满？*/if (s->top == s->maxlen-1){return -1;}s->top = s->top + 1;s->date[top] = value;return 0;
}

                 栈空or栈满

/*full or empty == 1*/
int stack_empty(sqstack* s)
{if (s->top == -1){printf("empty!\n");return 1;}return 0;
}
int stack_full(sqstack* s)
{if (s->top == s->maxlen - 1){printf("full");return 1;}return 0;
}

                出栈 

int stack_pop(sqstack* s)
{if (s->top == -1){return -1;}s->top = s->top - 1;return s->date[s->top+1];
}

                查看栈顶 

int stack_top(sqstack* s)
{return s->date[s->top];
}

                栈清空 

int stack_clear(sqstack* s)
{if (s == NULL){return -1;}s->top = 1;return 0;
}

                栈释放

int stack_free(sqstack* s)
{/*核心逻辑：先释放后申请的内存空间（因为释放先申请的内存空间就无法找到后申请的地址）*/if (s == NULL){return -1;}if (s->date != NULL){free(s->date);}free(s);return 0;
}

 链式栈

        

        

这篇关于Day 7：栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---