栈stack和队列

一· 栈和队列

栈和队列是两种重要的线性结构。从数据结构来看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集（也具有顺序结构和链式结构），它们是操作受限的线性表，因此，可称为限定性的数据结构。

二· 栈

定义 ：只能在表的一端（栈顶）进行插入和删除运算的线性表。

逻辑结构：与线性表相同，仍为一对一关系。

存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见。
链栈：

运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则

栈的示意图：
应用：如果需要按照保存数据时相反的顺序来使用数据，则可以利用栈来实现。（具体可参照课本《数据结构》）

1. 递归
2. 数值转换
3. 四则运算表达式求值
4. 括号匹配问题

栈的表示和操作的实现

base==top 是栈空的表现

top指示真正的栈顶元素之上的下标地址

#define MAXSIZE  100
typedef struct
{
		SElemType   *base;//用于栈底指针
		SElemType   *top;//用于栈顶指针
		int         stacksize;
}SqStack;
1
2
3
4
5
6
7

基本操作
1.头文件

#include<stack>
1

2 . 栈的初始化

stack<int> s1;      //创建一个空栈s1
stack<int> s2(s1);  //用s1初始化s2
1
2

3 .判断栈内是否为空empty()(为空返回true,非空返回false)

bool  empty();
while(!s1.empty())
1
2

4 .入栈push()

s1.push(10);
s1.push(20);
s1.push(30);   
s1.push(100);  //表s1中有四个元素，从栈顶到栈底依次为100，30，20，10
1
2
3
4

5 .删除堆栈中最顶层元素pop()。

s1.push(10);
s1.push(20);
s1.push(30);
s1.push(100);
s1.pop();    //此时s1中有三个元素，从栈顶到栈底依次为30，20，10

1
2
3
4
5
6

6 .获得栈顶元素top()

s1.push(10);
s1.push(20);
s1.push(30);
cout << s1.top() <<endl;   //输出元素30
1
2
3
4

7 .返回栈内元素的个数size()

cout << s1.size() <<endl;
1

操作实现

#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;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

结果

40
4
输出栈内现在元素：
30 20 10
1
2
3
4

三.队列

1 .定义：队列是只允许在一端进行插入操作，另一端进行删除操作的线性表，遵循 先进先出 原则。

2.队列的顺序表示和实现
队列的顺序存储结构

#define MAXQSIZE 100
typedef struct
{
		QElemType *base;      //存储空间的基地址
		int  front;      //头指针
		int  rear;      //尾指针
}SqStack;
1
2
3
4
5
6
7

设两个整形变量front和rear分别指示队列头元素和队列尾元素（即头指针和尾指针）
约定：初始化创建空队列时，令front=rear=0,每当插入新的队列尾元素时，尾指针 rear增1;每当删除队列头元素时，头指针front增1；。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置，如图所示。

3.应用（参照课本内容）

1. 舞伴问题
2. 银行排队模拟

4 .基本操作
1 . 头文件

#include<queue>
1

2 .队列初始化

queue<int> q;        //定义空队列q
queue<double> q[20]; //规定元素个数为20
1
2

3 .入队push()

q.push(10);
q.push(20);
q.push(30);
q.push(40);  //从队头到队尾元素依次为10，20，30，40
1
2
3
4

4 .删除队头元素pop()

q.push(10);
q.push(20);
q.push(30);
q.push(40); 
q.pop(); //从队头到队尾元素依次为20，30，40
1
2
3
4
5

5 .返回队头元素front()

q.push(10);
q.push(20);
q.push(30);
q.push(100);
cout << q.front() <<endl;  //输出结果为10
1
2
3
4
5

6 .返回队尾元素back()

q.push(10);
q.push(20);
q.push(30);
q.push(100);
cout << q.back() <<endl;  //输出结果为100
1
2
3
4
5

7 .返回队列中元素的个数size()

q.push(10);
q.push(20);
q.push(30);
q.push(100);
cout << q.size() <<endl;//输出结果为4
1
2
3
4
5

8.判断队列是否为空empty() （队列为空返回真，非空返回假）

while(!q.empty())
1

操作实现

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

结果

4
10
40
输出队列内现在的元素
20 30 40
1
2
3
4
5