网站代理服务器有问题,苏州做手机网站,注册劳务公司需要什么条件多少钱,wordpress绑定域名插件栈和队列是两种常用的线性结构#xff0c;属于特殊的线性表#xff0c;是线性表相关运算的一个子集。一般来说#xff0c;线性表上的插入和删除操作不受任何限制#xff0c;但栈只能在表的一端进行插入和删除操作#xff0c;而队列则只能在一端进行插入操作#xff0c;在… 栈和队列是两种常用的线性结构属于特殊的线性表是线性表相关运算的一个子集。一般来说线性表上的插入和删除操作不受任何限制但栈只能在表的一端进行插入和删除操作而队列则只能在一端进行插入操作在另一端进行删除操作。因此栈和队列通常称为操作受限的线性表。 栈 1.栈的定义2.栈的抽象数据类型3.顺序栈3.1顺序栈的类定义3.2初始化建立空栈3.3入栈操作3.4退栈操作3.5栈判空操作3.6返回栈顶元素3.7打印栈3.8全部代码 4.链栈4.1链栈的类定义4.2创建空栈4.3销毁栈4.4入栈操作4.5退栈操作4.6判空操作4.7返回栈顶元素4.8打印栈4.9全部代码 1.栈的定义 栈是限定在表的一端进行插入和删除操作的线性表。表中允许插入和删除操作的一端称为栈顶另一端叫做栈底。当栈中没有任何元素时称为空栈。栈顶位置是动态的由一个栈顶的指针top指示其位置具体实现时一般指向当前元素的下一个空位。栈的插入操作通常称为压栈或进栈删除操作通常称为退栈或出栈。栈具有“后进先出先进后出”的特点即后进栈的元素先出栈。 栈操作示例图 假设这里有三个元素a、b、c,如果进栈顺序是abc那么出栈的顺序有几种可能呢 5种abc acb cba bac bca 2.栈的抽象数据类型 3.顺序栈 顺序栈是指用一组地址连续的存储空间依次存放栈中元素的存储结构并用一个变量top指向当前栈顶元素的下一个空位来反映栈中元素的变化情况另一个变量base指向栈底。顺序栈的存储结构如下图所示 3.1顺序栈的类定义
#define InitStackSize 100
#define StackIncrement 10
typedef int SElemType;
class Sqstack
{
private:SElemType* base;//栈底指针SElemType为栈中元素类型SElemType* top;//栈顶指针int stacksize;//栈容量
public:Sqstack();//构造函数初始化建立一空栈~Sqstack()//析构函数销毁栈{delete[]base;stacksize 0;}SElemType GetTop();//取栈顶元素void Push(SElemType e);//进栈void Pop(SElemType e);//退栈int EmptyStack();//判断栈空否若空返回1否则返回0void Print();//从栈底到栈顶输出栈中的元素
};3.2初始化建立空栈
Sqstack::Sqstack()
{base top new SElemType[InitStackSize];stacksize InitStackSize;
}3.3入栈操作
void Sqstack::Push(SElemType e)
{if (top - base stacksize){SElemType* base1 new SElemType[stacksize StackIncrement];int i 0;for (i 0; i InitStackSize; i){base1[i] base[i];}delete[]base;//释放空间base base1;top base stacksize;stacksize StackIncrement;}*top e;//插入e
}3.4退栈操作
void Sqstack::Pop(SElemType e)
{if (top base)//栈空删除操作无法进行return;e *top--;
}3.5栈判空操作
int Sqstack::EmptyStack()
{if (top base)return 1;elsereturn 0;
}3.6返回栈顶元素
SElemType Sqstack::GetTop()//返回栈顶元素
{return *(top - 1);
}3.7打印栈
void Sqstack::Print()//打印栈中元素
{int i 0;for (i 0; i *(top - 2); i){cout base[i] ;}cout endl;
}3.8全部代码
#define _CRT_SECURE_NO_WARNINGS 1
#include iostream
using namespace std;
#define InitStackSize 100
#define StackIncrement 10
typedef int SElemType;
class Sqstack
{
private:SElemType* base;//栈底指针SElemType为栈中元素类型SElemType* top;//栈顶指针int stacksize;//栈容量
public:Sqstack();//构造函数初始化建立一空栈~Sqstack()//析构函数销毁栈{delete[]base;stacksize 0;}SElemType GetTop();//取栈顶元素void Push(SElemType e);//进栈void Pop();//退栈int EmptyStack();//判断栈空否若空返回1否则返回0void Print();//从栈底到栈顶输出栈中的元素
};
Sqstack::Sqstack()
{base top new SElemType[InitStackSize];stacksize InitStackSize;
}
void Sqstack::Push(SElemType e)
{if (top - base stacksize){SElemType* base1 new SElemType[stacksize StackIncrement];int i 0;for (i 0; i InitStackSize; i){base1[i] base[i];}delete[]base;//释放空间base base1;top base stacksize;stacksize StackIncrement;}*top e;//插入e
}
void Sqstack::Pop()
{SElemType e;if (top base)//栈空删除操作无法进行return;e *top--;
}
int Sqstack::EmptyStack()//判空函数
{if (top base)return 1;elsereturn 0;
}
SElemType Sqstack::GetTop()//返回栈顶元素
{cout *(top - 1) endl;return 0;
}
void Sqstack::Print()//打印栈中元素
{int i 0;for (i 0; i *(top - 2); i){cout base[i] ;}cout endl;
}
int main()
{Sqstack l;l.Push(3);l.Push(5);l.Push(6);l.Pop();l.GetTop();l.Print();return 0;
}✅调试运行
4.链栈 链栈是指利用一组地址任意的存储空间存放栈中元素的存储结构这里使用链表来实现链栈。链栈的存储结构如下图所示 注top指向头结点a1为栈顶元素an为栈底元素栈的所有操作都在单链表的表头进行。 4.1链栈的类定义
typedef int SElemType;
typedef struct LinkNode
{SElemType data;LinkNode* next;
}LinkNode;
class LinkStack
{
private:LinkNode* top;//栈顶指针即链栈的头指针
public:LinkStack();//构造函数置空链栈~LinkStack();//析构函数释放链栈中各结点的存储空间SElemType GetTop();//获取栈顶元素void Push(SElemType e);//将元素e入栈void Pop(SElemType e);//将栈顶元素出栈int EmptyStack();//判断链栈是否为空栈
};4.2创建空栈
LinkStack::LinkStack()
{top new LinkNode;top-next NULL;
}4.3销毁栈
LinkStack::~LinkStack()//析构函数释放链栈中各结点的存储空间
{LinkNode* p top;LinkNode* q top-next;while (q){delete p;p q;q q-next;}delete p;//删除最后一个结点
}4.4入栈操作
void LinkStack::Push(SElemType e)
{LinkNode* s new LinkNode;//分配空间s-data e;s-next top-next;//插入元素etop-next s;
}4.5退栈操作
void LinkStack::Pop(SElemType e)
{if (top-next NULL)return;LinkNode* p top-next;//p指向首元结点e p-data;top-next p-next;//删除首元结点delete p;
}4.6判空操作
int LinkStack::EmptyStack()
{if (top-next NULL)return 1;else return 0;//栈非空返回0
}4.7返回栈顶元素
SElemType LinkStack::GetTop()
{return top-next-data;
}4.8打印栈
void LinkStack::print()
{LinkNode* p top-next;while (p){cout p-data ;p p-next;}cout endl;
}4.9全部代码
#define _CRT_SECURE_NO_WARNINGS 1
#include iostream
using namespace std;
typedef int SElemType;
typedef struct LinkNode
{SElemType data;LinkNode* next;
}LinkNode;
class LinkStack
{
private:LinkNode* top;//栈顶指针即链栈的头指针
public:LinkStack();//构造函数置空链栈~LinkStack();//析构函数释放链栈中各结点的存储空间SElemType GetTop();//获取栈顶元素void Push(SElemType e);//将元素e入栈void Pop();//将栈顶元素出栈int EmptyStack();//判断链栈是否为空栈void print();//打印栈
};
LinkStack::LinkStack()//构造函数置空链栈
{top new LinkNode;top-next NULL;
}
LinkStack::~LinkStack()//析构函数释放链栈中各结点的存储空间
{LinkNode* p top;LinkNode* q top-next;while (q){delete p;p q;q q-next;}delete p;//删除最后一个结点
}
void LinkStack::Push(SElemType e)
{LinkNode* s new LinkNode;//分配空间s-data e;s-next top-next;//插入元素etop-next s;
}
void LinkStack::Pop()
{SElemType e;if (top-next NULL)return;LinkNode* p top-next;//p指向首元结点e p-data;top-next p-next;//删除首元结点delete p;
}
int LinkStack::EmptyStack()
{if (top-next NULL)return 1;else return 0;//栈非空返回0
}
SElemType LinkStack::GetTop()
{cout top-next-data endl;return 0;
}
void LinkStack::print()
{LinkNode* p top-next;while (p){cout p-data ;p p-next;}cout endl;
}
int main()
{LinkStack l;l.Push(1);l.Push(2);l.Push(3);l.Push(4);l.Push(5);l.GetTop();l.Pop();l.print();
}✅运行示例 好啦关于栈的知识到这里就结束啦后期会继续更新数据结构与算法的相关知识欢迎大家持续关注、点赞和评论❤️❤️❤️
