【数据结构】栈

文章目录

• 1.栈的概念及结构
• 2.栈的实现
• • 2.1初始化
  • 2.2入栈
  • 2.3出栈
  • 2.4栈顶元素
  • 2.5栈中有效元素个数
  • 2.6检测栈是否为空
  • 2.7销毁栈
  • 2.8栈的打印

    

    今天学习一种新的数据结构——栈

    1.栈的概念及结构

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

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

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

    

    栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

    

    typedef int StackDataType;
    //动态
    typedef struct Stack
    {
    	StackDataType* arr;//数组实现
    	int top;//栈顶，有效元素的下一个
    	int capacity;//数组容量
    }Stack;
    

    2.栈的实现

    栈这种数据结构的特点就是后进先出，由于它的特性，它的使用方法也就不像链表那样麻烦。基本使用如下：

    2.1初始化

    //初始化
    void StackInit(Stack* ps)
    {
    	assert(ps);
    	ps->arr = NULL;
    	ps->capacity = 0;
    	ps->top = 0;
    }
    

    2.2入栈

    入栈前，应检查数组的大小。若数组满了，应进行扩容。

    //入栈
    void StackPush(Stack* ps, StackDataType x)
    {
    	assert(ps);
    	//检查容量
    	if (ps->top == ps->capacity)
    	{
    		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		//扩容
    		StackDataType* tmp = (StackDataType*)realloc(ps->arr, sizeof(StackDataType) * newcapacity);
    		if (!tmp)
    		{
    			perror("realloc");
    			return;
    		}
    		ps->arr = tmp;
    		ps->capacity = newcapacity;
    	}
    	//数据入栈
    	ps->arr[ps->top] = x;
    	ps->top++;
    }
    

    2.3出栈

    由于我们使用的是数组，所以出栈就非常简单，只需将栈顶下移即可。

    //出栈
    void StackPop(Stack* ps)
    {
    	assert(ps);
    	//栈中得有元素
    	assert(ps->top);
    	//出栈
    	ps->top--;
    }
    

    2.4栈顶元素

    //栈顶元素
    StackDataType StackTopElement(Stack* ps)
    {
    	assert(ps);
    	assert(ps->top);
    	return ps->arr[ps->top - 1];
    }
    

    2.5栈中有效元素个数

    由于数组下标从0开始，我们的栈顶指向的是当前元素的下一个位置；因此，直接返回栈顶即可。

    //有效元素个数
    int StackSize(Stack* ps)
    {
    	assert(ps);
    	return ps->top;
    }
    

    2.6检测栈是否为空

    如果为空返回非零结果，如果不为空返回0

    //是否为空，如果为空返回非零结果，如果不为空返回0 
    int StackEmpty(Stack* ps)
    {
    	assert(ps);
    	return ps->top == 0;
    }
    

    2.7销毁栈

    //销毁栈
    void StackDestroy(Stack* ps)
    {
    	assert(ps);
    	free(ps->arr);
    	ps->arr = NULL;
    	ps->capacity = 0;
    	ps->top = 0;
    }
    

    2.8栈的打印

    由于栈的特性，它的打印方式和数组不同。它是先获取栈顶元素打印，然后出栈。

    int main()
    {
    	Stack stack;
    	StackInit(&stack);
    	StackPush(&stack, 1);
    	StackPush(&stack, 2);
    	StackPush(&stack, 3);
    	StackPush(&stack, 4);
    	StackPush(&stack, 5);
    	while (!StackEmpty(&stack))
    	{
    		int top = StackTopElement(&stack);
    		printf("%d ", top);
    		StackPop(&stack);
    	}
    	return 0;
    }