数据结构----栈和队列

（一）栈

1.栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

2.代码实现

1.栈的构成

#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;
typedef int STDateType;
typedef struct Stack
{STDateType* a;int top;int capacity;
}ST;

这里栈我使用结构体来实现，ps->top来代表栈顶，ps->capacity代表一共开辟的空间，用来和ps->top比较，来判断这个栈到底满没满。

2.初始化

void Init(ST*ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

3.栈的销毁

void Destory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

记住这里free的是ps->a，而不是ps，你是让指针ps->a开辟的空间，而不是这个结构体开辟的空间，所以你要销毁指针的。

4.往栈顶存放数据

void Push(ST* ps, STDateType x)
{assert(ps);if (ps->capacity == 0){STDateType* b = (STDateType*)malloc(sizeof(STDateType) * 4);if (b == NULL){perror("malloc");exit(0);}ps->capacity = 4;ps->a = b;}if ( ps->top  == ps->capacity){STDateType newcapacity = 2 * ps->capacity;STDateType* b = (STDateType*)realloc(ps->a, newcapacity*sizeof(STDateType));if (b==NULL){perror("relloc");exit(0);}ps->a = b;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}

开始的时候栈的指针ps->a可能没有开辟空间，是第一次使用，所以我们要先确定这个情况。

当ps->top==ps->capacity时，我们的ps->top已经跳到栈的外面了，这时它们正好相等，所以来通过这个判断。

这里我直接开辟一个新的指针来接收新开辟的空间，是防止直接用ps->a指针来开辟额外的空间失败后，导致ps->a=NULL，使得我们不知道原来开辟空间的地址，会造成空间的浪费。

这个函数中如果开辟失败，会跳出函数，并报错。如果开辟成功，我让指针a指向这个新的空间，并将新的空间数量给ps->capacity，将数字放入栈顶，并使得ps->top指向下一个位置。

5.取得栈顶的数值(但不对栈顶的数字进行销毁)

STDateType  Top(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top-1];
}

这里的ps->top>0的判断，是因为当ps->top==0时，你再ps->top-1，会出现越界访问。并且只有当你放入值的时候，ps->top至少是>=1的，所以当ps->top==0时，没有放入值。

6.去掉栈顶的数据

void Pop(ST* ps)
{assert(ps);if(ps->top>0)ps->top--;else{perror("Pop");exit(0);}
}

这里我们只需要将ps->top--就可以，因为当我们下一次的赋值时，这个原来的值会被覆盖。

7.判断这个栈是否为空

bool Empty(ST* ps)
{assert(ps);return ps->top == 0;
}

bool是用来判断的，返回值只有true与false，当ps->top==0时，就会返回true，反之为false。

8.判断这个栈的数据个数

int Size(ST* ps)
{assert(ps);return ps->top;
}

（二）.队列

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

通过这些描述，我们也可以知道队列和栈非常的相似。所以我们只需要改动一下栈的代码就可以。我下面只展示需要改动的代码，如果没有改动的代码，一切与上面的一样。

1.取队列的头个值

STDateType  Top(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[0];
}

这里我只是将ps->a[]中的值改成了0。其他没有变化

2.去掉队列头一个数值

void Pop(ST* ps)
{assert(ps);if (ps->top > 0){int i;for (i = 0; i < ps->top -1; i++){ps->a[i] = ps->a[i + 1];}ps->top--;}else{perror("Pop");exit(0);}
}

这里我用到的是覆盖的想法，将前一个与后一个进行覆盖，但是这里要注意的是i<ps->top-1,而不是ps->top。

如果这一篇文章对你有用的话，希望得到你的三连，谢谢大家观看。