栈和队列
- 一· 栈和队列
- 二· 栈
- 三.队列
一· 栈和队列
栈和队列是两种重要的线性结构。从数据结构来看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集（也具有顺序结构和链式结构），它们是操作受限的线性表，因此，可称为限定性的数据结构。
二· 栈
定义 ：只能在表的一端（栈顶）进行插入和删除运算的线性表。
逻辑结构：与线性表相同，仍为一对一关系。
存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见。
链栈：
运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则
栈的示意图：
应用：如果需要按照保存数据时相反的顺序来使用数据，则可以利用栈来实现。（具体可参照课本《数据结构》）
- 递归
- 数值转换
- 四则运算表达式求值
- 括号匹配问题
栈的表示和操作的实现
base==top 是栈空的表现
top指示真正的栈顶元素之上的下标地址
#define MAXSIZE 100
typedef struct
{SElemType *base;//用于栈底指针SElemType *top;//用于栈顶指针int stacksize;
}SqStack;
基本操作
1.头文件
#include<stack>
2 . 栈的初始化
stack<int> s1; //创建一个空栈s1
stack<int> s2(s1); //用s1初始化s2
3 .判断栈内是否为空empty()(为空返回true,非空返回false)
bool empty();
while(!s1.empty())
4 .入栈push()
s1.push(10);
s1.push(20);
s1.push(30);
s1.push(100); //表s1中有四个元素，从栈顶到栈底依次为100，30，20，10
5 .删除堆栈中最顶层元素pop()。
s1.push(10);
s1.push(20);
s1.push(30);
s1.push(100);
s1.pop(); //此时s1中有三个元素，从栈顶到栈底依次为30，20，106 .获得栈顶元素top()
s1.push(10);
s1.push(20);
s1.push(30);
cout << s1.top() <<endl; //输出元素30
7 .返回栈内元素的个数size()
cout << s1.size() <<endl;
操作实现
#include<iostream>
#include<stack>//栈的头文件
using namespace std;int main()
{stack<int> s1;s1.push(10);//10入栈s1.push(20);//20入栈s1.push(30);//30入栈s1.push(40);//40入栈cout<<s1.top()<<endl;//输出栈顶元素cout<<s1.size()<<endl;//输出栈内元素的个数s1.pop();//删除栈顶元素cout << "输出栈内现在元素：" << endl; while(!s1.empty()) //s1非空，此循环是将栈内元素全部输出{cout << s1.top() << " "; // 输出栈顶元素s1.pop(); //删除栈顶元素 } return 0;}
结果
40
4
输出栈内现在元素：
30 20 10
三.队列
1 .定义：队列是只允许在一端进行插入操作，另一端进行删除操作的线性表，遵循 先进先出 原则。
2.队列的顺序表示和实现
队列的顺序存储结构
#define MAXQSIZE 100
typedef struct
{QElemType *base; //存储空间的基地址int front; //头指针int rear; //尾指针
}SqStack;
设两个整形变量front和rear分别指示队列头元素和队列尾元素（即头指针和尾指针）
约定：初始化创建空队列时，令front=rear=0,每当插入新的队列尾元素时，尾指针 rear增1;每当删除队列头元素时，头指针front增1；。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如图所示。
3.应用（参照课本内容）
- 舞伴问题
- 银行排队模拟
4 .基本操作
1 . 头文件
#include<queue>
2 .队列初始化
queue<int> q; //定义空队列q
queue<double> q[20]; //规定元素个数为20
3 .入队push()
q.push(10);
q.push(20);
q.push(30);
q.push(40); //从队头到队尾元素依次为10，20，30，40
4 .删除队头元素pop()
q.push(10);
q.push(20);
q.push(30);
q.push(40);
q.pop(); //从队头到队尾元素依次为20，30，40
5 .返回队头元素front()
q.push(10);
q.push(20);
q.push(30);
q.push(100);
cout << q.front() <<endl; //输出结果为10
6 .返回队尾元素back()
q.push(10);
q.push(20);
q.push(30);
q.push(100);
cout << q.back() <<endl; //输出结果为100
7 .返回队列中元素的个数size()
q.push(10);
q.push(20);
q.push(30);
q.push(100);
cout << q.size() <<endl;//输出结果为4
8.判断队列是否为空empty() （队列为空返回真，非空返回假）
while(!q.empty())
操作实现
#include<iostream>
#include<queue>
using namespace std;
int main()
{queue<int> q; //q为空队列 q.push(10);q.push(20);q.push(30);q.push(40); //将10，20，30，40入队，从队头到队尾依次为10，20，30，40 cout << q.size() << endl; //输出队列中元素的个数cout << q.front() << endl ;//返回队头元素cout << q.back() << endl ;//返回队尾元素q.pop(); //删除队头元素 cout << "输出队列内现在元素：" << endl; while(!q.empty()) //q非空，此循环是将队列内元素全部输出{cout << q.front() << " "; //输出队头元素q.pop(); //删除队头元素} return 0;
}
结果
4
10
40
输出队列内现在的元素
20 30 40
