数据结构与算法-栈

在这里插入图片描述

栈和队列是两种常用的线性结构，属于特殊的线性表，是线性表相关运算的一个子集。一般来说，线性表上的插入和删除操作不受任何限制，但栈只能在表的一端进行插入和删除操作，而队列则只能在一端进行插入操作，在另一端进行删除操作。因此，栈和队列通常称为操作受限的线性表。

栈

🎈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();
}