在前面我们已经学习了哪些线性数据结构呢?大家一起来回顾一下:C语言学过的数组,数据结构中的线性表和顺序表和链表。那我们今天再来介绍数据结构里的两个线性结构--栈和队列。
目录
一、栈的概念及结构
二、用数组实现栈
1. 栈的初始化和销毁
2. 从栈顶插入数据
3. 删除栈顶元素
4. 取栈顶元素
5. 计算栈中元素的数量
6. 判断栈是否为空
三、用链表实现栈
四、两种实现对比
1. 支持操作
2. 时间效率
3. 空间效率
五、栈的应用
一、栈的概念及结构
栈:一种特殊的线性表,只允许在固定一端插入和删除元素。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
二、用数组实现栈
栈的实现一般可以使用数组或链表实现,相对而言数组的结构实现更优一些。
使用数组实现栈时,我们可以将数组的尾部作为栈顶。入栈与出栈操作分别对应在数组尾部添加元素与删除元素。那我们先通过数组实现栈。
先在头文件中定义需要实现的功能接口:
//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 倍)进行扩容的,扩容后的容量也可能超出实际需求。因此,基于数组实现的栈可能造成一定的空间浪费。
然而,由于链表节点需要额外存储指针,因此链表节点占用的空间相对较大。
综上,我们不能简单地确定哪种实现更加节省内存,需要针对具体情况进行分析。
五、栈的应用
- 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页,浏览器就会对上一个网页执行入栈,这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进,那么需要两个栈来配合实现。
- 程序内存管理。每次调用函数时,系统都会在栈顶添加一个栈帧,用于记录函数的上下文信息。在递归函数中,向下递推阶段会不断执行入栈操作,而向上回溯阶段则会不断执行出栈操作。