
//Stack.h
#pragma once
#include<stdio.h>
#include <stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//数组实现
	int top;//栈顶
	int capacity;//栈的容量
}ST;
//栈的初始化和销毁
void STInit(ST* ps);
void STDestroy(ST* ps);
//插入(只能从栈顶插入)
void STPush(ST* ps, STDataType x);
//栈中元素的删除
void STPop(ST* ps);
//取栈顶元素
STDataType STTop(ST* ps);
//计算栈中元素的数量
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);

1. 栈的初始化和销毁


void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//top=0指向的是栈顶元素的下一个
	//我们也可以让top=-1，这样top就指向栈顶元素
	ps->capacity = 0;
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

2. 从栈顶插入数据


void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//空间不够直接扩容
	if (ps->top == ps->capacity)
	{
		//一开始没有给容量多大，因此需要判断
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//ps->a为空的话，realloc相当于malloc
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

3. 删除栈顶元素


void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

4. 取栈顶元素


STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

5. 计算栈中元素的数量


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

6. 判断栈是否为空


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

三、用链表实现栈

使用链表实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。

对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为“头插法”。而对于出栈操作，只需将头节点从链表中删除即可。

实现逻辑与数组相似，因此在这里直接给出实现代码：


//基于链表实现的栈
typedef struct {
    ListNode *top;//将头节点作为栈顶
    int size;//栈的长度
} LinkedListStack;
 
//栈的初始化
LinkedListStack *newLinkedListStack() 
{
    LinkedListStack *s = malloc(sizeof(LinkedListStack));
    s->top = NULL;
    s->size = 0;
    return s;
}
 
//栈的销毁
void delLinkedListStack(LinkedListStack *s) 
{
    while (s->top) 
    {
        ListNode *n = s->top->next;
        free(s->top);
        s->top = n;
    }
    free(s);
}
 
//计算栈中元素的数量
int size(LinkedListStack *s) 
{
    return s->size;
}
 
//判断栈是否为空
bool isEmpty(LinkedListStack *s) 
{
    return size(s) == 0;
}
 
//从栈顶插入数据
void push(LinkedListStack *s, int num) 
{
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->next = s->top;//更新新加节点指针域
    node->val = num;//更新新加节点数据域
    s->top = node;//更新栈顶
    s->size++;//更新栈大小
}
 
//取栈顶元素
int peek(LinkedListStack *s) {
    if (s->size == 0) 
    {
        printf("栈为空\n");
        return -1;
    }
    return s->top->val;
}
 
//删除栈顶元素
int pop(LinkedListStack *s) 
{
    int val = peek(s);
    ListNode *tmp = s->top;
    s->top = s->top->next;
    //释放内存
    free(tmp);
    s->size--;
    return val;
}

四、两种实现对比

1. 支持操作

两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问，但这已超出了栈的定义范畴，因此一般不会用到。

2. 时间效率

在基于数组的实现中，入栈和出栈操作都在预先分配好的连续内存中进行，具有很好的缓存本地性，因此效率较高。然而，如果入栈时超出数组容量，会触发扩容机制，导致该次入栈操作的时间复杂度变为O(N) 。

在基于链表的实现中，链表的扩容非常灵活，不存在上述数组扩容时效率降低的问题。但是，入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。

综上所述，当入栈与出栈操作的元素是基本数据类型时，例如int或double我们可以得出以下结论。

基于数组实现的栈在扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。
基于链表实现的栈可以提供更加稳定的效率表现。

3. 空间效率

在初始化列表时，系统会为列表分配“初始容量”，该容量可能超出实际需求；并且，扩容机制通常是按照特定倍率（例如 2 倍）进行扩容的，扩容后的容量也可能超出实际需求。因此，基于数组实现的栈可能造成一定的空间浪费。

然而，由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。

综上，我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。

五、栈的应用

浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/527821