【数据结构】栈和队列(上)

目录

一、栈（先进后出、后进先出的线性表）

1、栈的概念及结构

2、栈的底层结构分析

二、代码实现

1、定义一个栈

2、栈的初始化

3、入栈

3、增容

4、出栈

5、取栈顶

6、销毁栈

---

一、栈（先进后出、后进先出的线性表）

1、栈的概念及结构

栈：一种特殊的线性表，只允许在固定的一端进行插入和删除数据的操作。进行数据插入、删除的一端为栈顶，不可进行操作的一端则是栈底。对于任意一个数据结构，我们都要分析一下它的逻辑结构和物理结构，既然是线性表，那么说明逻辑结构一定是线性的

逻辑结构：是线性的

物理结构：也是线性的

对于栈的操作主要有如下两个：

一个是压栈，另一个则是出栈。其中压栈是栈的插入操作（也叫做进栈、入栈）；出栈则是栈的删除操作，出数据也在栈顶。

2、栈的底层结构分析

既然我们已经对栈这一个数据结构的概念有了初步的了解，那么现在，我们来深入探讨一下，栈的底层结构是什么？既然他是线性的，那么他是数组还是链表呢？

我们从这里分析：

我们可以从上图看到链表的结构，由于栈只能从栈顶操作数据，假设栈的底层是链表，如果链表的尾部为栈顶的话，每一次访问栈顶都要去遍历一次链表，那么无疑使时间复杂度增加到了O(N)，相反，如果链表的头部为栈顶，对数据进行插入删除时的时间复杂度就会好很多，为O(1)。

我们来画个图看看数组，从数组中插入删除数据，可以把数组的尾当做栈顶插入删除数据，时间复杂度认为O(1)，既然这样，链表和数组作为栈的底层结构，入栈和出栈的时间复杂度都为O(1)，那么，我们来换个维度来考虑：

以上是使用链表和数组结构写的栈的构造代码，我们可以看出，左图中的结构使用了链表，每向栈中插入一个数据，空间不仅仅会增加int类型的4字节，还会增加指针8字节的大小，相比于数组结构，链表结构对空间的使用会更大，所以，我们还是更推荐用数组作为栈的底层结构。

二、代码实现

下面，我们来实现一下栈的代码：

1、定义一个栈

我们要定义一下栈的结构，由于栈的底层是数组，又要开辟空间，我们就定义一个动态的数组好了:

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;

2、栈的初始化

下面，我们来定义一个初始化方法：

void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}

3、入栈

当要向数组插入数据首先要看栈中是否为空，若不为空，插入数据后ps->top要++，指向栈顶

3、增容

注意：这里又出现一个问题，当ps->top==ps->capacity时，说明空间已经不够了，如果要继续插入数据，我们需要进行一个增容操作：

这里，ps->capacity=newcapacity

void StackPush(ST* ps,STDatatype x)
{assert(ps);//这里做一个断言操作，防止对空指针解引用if(ps->top == ps->capacity){int newcapacity = ps->capacity==0?4:2*ps->capacity;(STDataType*)tmp = (STDataType*)realloc(ps->arr,newcapacity*sizeof(STDataType));if(tmp == NULL){perror("realloc fail!");exit(1);    }ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}

4、出栈

出栈操作：

每当遇到数据结构中的出数据操作时，我们都要考虑其是否有数据可以为我们所用，所以写出栈操作之前，我们首先要判断栈是否为空，这里，我们可以定义一个方法：

bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;//判断top（即有效数据个数是否为零，如果为零，则返回ture）
}

其次，假设，ps->top，不为零，则出栈操作直接可以写成--ps->top；

void Stackpop(ST* ps)
{assert(ps);if(!StackEmpty(ps)){--ps->top;    }
}

5、取栈顶

下一个操作是：取栈顶操作，与出栈顶（有效的数据个数会减少）操作不同，去栈顶操作不会删除数据，而只是将栈顶的数据复制一下并使用。

STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps);return ps->arr[ps->top-1];
}

6、销毁栈

接下来，我们看一下对于栈的销毁操作：

void StackDestroy(ST* ps)
{if(ps->arr)free(ps->arr);ps->arr = NULL;//这里有一点ps->top = ps->capacity = 0;
}

这里有一个小tips：将ps->arr = NULL，这里可能有同学会有疑问，为什么写出栈操作时，只需要--ps->top，不需要将数据free，这是因为，在数组中，arr表示数组首元素的地址，如果你将ps->arr free掉，那么整个数组的数据都会被销毁，而链表的每一个空间都是独立存在的，假设你将上一个结点的空间销毁了，不会影响下一个结点，数组则不然。

以下是测试代码：

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"void test01()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);/*StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);*//*while (!StackEmpty(&st)){int top = StackTop(&st);printf("%d ", top);StackPop(&st);}*/int size = StackSize(&st);printf("size:%d", size);StackDestroy(&st);
}int main()
{test01();return 0;
}