ssy的小天地

愿汝如是 千金不换

0%

数据结构与算法之栈与队列

发表于 分类于

本节主要介绍了栈和队列的实现及其应用。

栈

  • 后进先出：一种限制访问端口的线性表

  • 引理：设k是最后一个出栈的，那么k把序列一分为二；在k之前入栈的元素，一定比在k之后入栈的元素要提前出栈

    image-20221209140126898

  • 给定一个入栈序列，序列长度为N，共有$f(N)$种出栈序列：
    $$
    f(N)=\frac1{N+1}\times C_{2N}^N
    $$

栈的实现方式

1.顺序栈

  • 用一块连续的内存存储数据，即用一维数组来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//LinearStack.h
#include<iostream>
using namespace std;
template<class T>
class LinearStack
{
public:
    LinearStack(int LSMaxSize);// 构造函数，创建栈
    ~LinearStack();  //析构函数，删除栈
    bool IsEmpty();  //判断栈是否为空，栈空返回true，否则返回false
    bool IsFull();   //判断栈是否已满
    int GetElementNumber(); //求栈中元素个数
    bool Push(const T& x); //在栈顶插入元素，成功返回true
    bool Top(T& x);       //求栈顶元素
    bool Pop(T& x); //从栈顶删除一个元素
    void OutPut(ostream& out); //将顺序栈输出
private:
    int top;     //用来表示栈顶
    int MaxSize; //栈中最大元素个数
    T* element;  //一维动态数组
};

//构造函数
template<class T>
LinearStack<T>::LinearStack(int LSMaxSize)
{
    MaxSize = LSMaxSize;
    element = new T[LSMaxSize];
    top = -1;
}
//析构函数
template<class T>
LinearStack<T>::~LinearStack()
{
    delete []element;
}
//判断栈是否为空
template<class T>
bool LinearStack<T>::IsEmpty()
{
    return (top == -1);
}
//判断栈是否已满
template<class T>
bool LinearStack<T>::IsFull()
{
    return ((top + 1) == MaxSize);
}

//实现进栈
template<class T>
bool LinearStack<T>::Push(const T& x)
{
    if (IsFull())
        return false;
    else
    {
        top++;
        element[top] = x;
        return true;
    }
}
//求栈顶元素
template<class T>
bool LinearStack<T>::Top(T& x)
{
    if (IsEmpty())
        return false;
    else
    {
        x = element[top];
        return true;
    }
}
//实现出栈
template<class T>
bool LinearStack<T>::Pop(T& x)
{
    if (IsEmpty())
        return false;
    else
    {
        x = element[top];
        top--;
        return true;
    }
}
//实现顺序栈的输出，栈底到栈顶。
template<class T>
void LinearStack<T>::OutPut(ostream& out)
{
    for (int i = 0; i <= top; i++)
        out << element[i] << endl;

}
//重载<<运算符
template<class T>
ostream& operator<<(ostream& cout, const LinearStack<T>& x)
{
    x.OutPut(cout);
    return cout;
}
  • 利用顺序栈实现十进制转其他进制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//LinearStack_appliction.cpp
//将十进制数转换为其他进制
#include<iostream>
#include"LinearStack.h"//包含之前写的类的定义和实现
using namespace std;
void con(int n, int base)//转换函数
{
    int x, y;
    y = n;
    LinearStack<int>s(100);
    while (y)
    {
        s.Push(y % base);
        y = y / base;
    }
    cout << "转换后的数为:";
    while (!s.IsEmpty())
    {
        s.Pop(x);
        cout << x;
    }
}
int main()
{
    int n, base;
    cout << "请输入十进制数和要转换的数的基数:";
    cin >> n >> base;
    con(n, base);

    return 0;
}

结果如下：

image-20221209152352220

2.链式栈

  • 相比顺序栈，链式栈不需要事先确定栈大小的问题，栈的大小随着出入栈操作不断的自己改变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#ifndef _LINKED_STACK_H
#define _LINKED_STACK_H

template<typename T>
class LinkStack;

//定义一个栈元素节点类
template<typename T>
class StackNode
{
	friend class LinkStack<T>;//声明栈类为节点类的友元，以便访问其私有数据
public:
	StackNode(){};
	StackNode(T _data) :data(_data), link(nullptr){};
	~StackNode(){};
private:
	T data;
	StackNode<T>* link;
};

//栈类
template<typename T>
class LinkStack
{
public:	
	LinkStack();
	~LinkStack();

	void Push(const T& _data);//入栈
	void Pop();//删除
	T& Top();//返回栈顶数据
	bool Empty();//判断栈是否为空
	int Size();//返回栈的大小

private:
	StackNode<T> *top;//栈顶指针
	int size;//栈当前的大小
};

//构造函数和析构函数
template <typename T>
LinkStack<T>::LinkStack()
:top(nullptr), size(0)
{
}
template <typename T>
LinkStack<T>::~LinkStack()
{
	while (!Empty()){
		Pop();
	}
}

//push函数
template <typename T>
void LinkStack<T>::Push(const T& _data)
{
	StackNode<T> *tmp = new StackNode<T>(_data);//生成一个新的栈元素节点，并赋初值_data
	tmp->link = top;//push的元素节点指向原来的栈顶
	top = tmp;//push的元素节点做为栈顶

	size++;//栈的大小+1
}

//pop函数
template <typename T>
void LinkStack<T>::Pop()
{
	if (!Empty()){
		StackNode<T> *tmp = top->link;//保存栈顶的下一个元素，因为它将成为栈顶
		delete top;
		top = tmp;

		size--;//栈大小-1
	}
	else exit(1);
}

//返回栈顶数据
template <typename T>
T& LinkStack<T>::Top()
{
	if (!Empty())
		return top->data;//栈不空返回栈顶数据
	else
		exit(1);
}

//检查栈是否为空
template <typename T>
bool LinkStack<T>::Empty()
{
	if (size > 0)
		return false;
	else
		return true;
}

//返回栈的大小
template <typename T>
int LinkStack<T>::Size()
{
	return size;
}

#endif
  • main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include "LinkedStack.h"

using namespace std;

int main()
{
	LinkStack<int> st;
	

	for (int i = 1; i <= 11; i++){
		st.Push(i); //入栈
	}

	while (!st.Empty())
	{
		cout << "size = " << st.Size() << "\t"; //打印当前栈的大小
		cout << "top = " << st.Top() << endl; //打印当前栈顶数据
		st.Pop();//出栈
	}
	return 0;
}

结果如下：

1
2
3
4
5
6
7
8
9
10
11
size = 11       top = 11
size = 10       top = 10
size = 9        top = 9
size = 8        top = 8
size = 7        top = 7
size = 6        top = 6
size = 5        top = 5
size = 4        top = 4
size = 3        top = 3
size = 2        top = 2
size = 1        top = 1

栈的应用—表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<iostream>     //输入的表达式要以'#'结尾，如‘5+6*3/(3-1)#’
#include<cstring>
#include<cstdio>
#include<cctype>
#include<stack>
using namespace std;
 
stack<char> opter;    //运算符栈
stack<double> opval;  //操作数栈
 
int getIndex(char theta)   //获取theta所对应的索引
{
	int index = 0;
	switch (theta)
	{
	case '+':
		index = 0;
		break;
	case '-':
		index = 1;
		break;
	case '*':
		index = 2;
		break;
	case '/':
		index = 3;
		break;
	case '(':
		index = 4;
		break;
	case ')':
		index = 5;
		break;
	case '#':
		index = 6;
	default:break;
	}
	return index;
}
 
char getPriority(char theta1, char theta2)   //获取theta1与theta2之间的优先级
{
	const char priority[][7] =     //算符间的优先级关系
	{
		{ '>','>','<','<','<','>','>' },
		{ '>','>','<','<','<','>','>' },
		{ '>','>','>','>','<','>','>' },
		{ '>','>','>','>','<','>','>' },
		{ '<','<','<','<','<','=','0' },
		{ '>','>','>','>','0','>','>' },
		{ '<','<','<','<','<','0','=' },
	};
 
	int index1 = getIndex(theta1);
	int index2 = getIndex(theta2);
	return priority[index1][index2];
}
 
double calculate(double b, char theta, double a)   //计算b theta a
{
	switch (theta)
	{
	case '+':
		return b + a;
        break;
	case '-':
		return b - a;
        break;
	case '*':
		return b * a;
        break;
	case '/':
		return b / a;
        break;
	default:
		return 0;
        break;
	}
}
 
double getAnswer()   //表达式求值
{
	opter.push('#');      //首先将'#'入栈opter
	int counter = 0;      //添加变量counter表示有多少个数字相继入栈，实现多位数的四则运算
	char c = getchar();
	while (c != '#' || opter.top() != '#')   //终止条件
	{
		if (isdigit(c))   //如果c在'0'~'9'之间
		{
			if (counter == 1)   //counter==1表示上一字符也是数字，所以要合并，比如12*12，要算12，而不是单独的1和2
			{
				double t = opval.top();
				opval.pop();
				opval.push(t * 10 + (c - '0'));
				counter = 1;
			}
			else
			{
				opval.push(c - '0');     //将c对应的数值入栈opval
				counter++;
			}
			c = getchar();
		}
		else
		{
			counter = 0;   //counter置零
			switch (getPriority(opter.top(), c))   //获取运算符栈opter栈顶元素与c之间的优先级，用'>'，'<'，'='表示
			{
			case '<':               //<则将c入栈opter
				opter.push(c);
				c = getchar();
				break;
			case '=':               //=将opter栈顶元素弹出，用于括号的处理
				opter.pop();
				c = getchar();
				break;
			case '>':               //>则计算
				char theta = opter.top();
				opter.pop();//出栈操作只是删除栈顶元素，并不返回该元素的值
				double a = opval.top();
				opval.pop();
				double b = opval.top();
				opval.pop();
				opval.push(calculate(b, theta, a));
			}
		}
	}
	return opval.top();   //返回opval栈顶元素的值
}
 
int main()
{
	//freopen("test.txt", "r", stdin);
	int t;     // 需要计算的表达式的个数
    cout<<"Please enther the comput times:";
	cin >> t;
	getchar();//将空格读掉
    int i=1;
	while (t--)
	{
		while (!opter.empty())opter.pop();
		while (!opval.empty())opval.pop();
        cout<<"The expression "<<i<<" is:";
		double ans = getAnswer();
        getchar();//将空格读掉
		cout << "The answer of expression "<<i<<" is:"<<ans<< endl;
        i++;
	}
	return 0;
}

结果如下：

image-20221209170543118

队列

  • 先进先出

  • 限制访问点的线性表：

    • 按照到达的顺序来释放元素
    • 所有的插入在表的一端进行，所有的删除都在表的另一端进行

  • 顺序队列示意图：

    image-20221209175359377

  • 循环队列示意图：

    image-20221209175447316
    • 入队：$r=(r+1)\%N$
    • 出队：$f=(f+1)\%N$
    • 队满：$(r+1)\%N=f$
    • 队空：$r=f$

列表的实现方式

1.循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
循环队列
*/
#include <iostream>
#define MaxSize 10 // 队列中元素的最大个数
using namespace std;
typedef int ElemType;
struct SqQueue {
    ElemType data[MaxSize]; // 队列中元素的最多个数
    int front, rear;        // 队头指针，队尾指针
};
// 初始化队列
void InitQueue(SqQueue &Q) { Q.front = Q.rear = 0; }
// 队列判空
bool QueueEmpty(SqQueue &Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}
// 入队
bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) { // 队满
        return false;
    } else {
        Q.data[Q.rear] = x; // 赋值给下一队尾
        Q.rear = (Q.rear + 1) % MaxSize; // 在逻辑上将存储空间变为“环状”，物理上仍然是静态数组
        return true;
    }
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.rear == Q.front) { // 队空
        return false;
    } else {
        x = Q.data[Q.front];
        Q.front = (Q.front + 1) % MaxSize; // 队头指针后移
        return true;
    }
}
// 获取队头元素
bool GetHead(SqQueue &Q, ElemType &x) {
    if (Q.rear == Q.front) { // 队空
        return false;
    } else {
        x = Q.data[Q.front];
        return true;
    }
}
// 获取队列长度
bool GetLength(SqQueue &Q, ElemType &len) {
    if (Q.front == Q.rear) {
        len = 0;
    } else {
        len = Q.front; // 指向队头
        while ((len + 1) % MaxSize != Q.rear) {
            len++;
        }
        len = len - Q.front + 1; // 如果有元素出队，会导致Q.front不为0，影响长度的判断，且初始化队列时，Q.front置为0，同样影响长度
    }
    return true;
}
int main() 
{
    SqQueue Q;
    InitQueue(Q);
    ElemType head, pop, length;
    for (int i = 1; i < 6; i++) {
        EnQueue(Q, i);
    }
    GetHead(Q, head);
    cout << "队头元素：" << head << endl;
    GetLength(Q, length);
    cout << "队列长度：" << length << endl;
    DeQueue(Q, pop);
    cout << "出队元素：" << pop << endl;
    GetHead(Q, head);
    cout << "队头元素：" << head << endl;
    GetLength(Q, length);
    cout << "队列长度：" << length << endl;
}

结果如下：

image-20221209181437866

2.链式队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
using namespace std;

class node{
public :
    int data;
    node * next;
    node * prev;
};

class queue{
private :
    node * head;//首节点
    node * tail;//尾节点
public:
    queue();
    void enQueue(int data);
    node * outQueue();
    void print();//循序打印
    int isEmpty();
};

queue::queue(){//初始化
    head=new node();
    tail=new node();
    head->next=tail;
    head->prev=NULL;
    tail->next=NULL;
    tail->prev=head;
}
void queue::enQueue(int data){//入队
    node * n=new node();
    n->data=data;
    n->next=head->next;
    n->prev=head;
    head->next->prev=n;
    head->next=n;
}
void queue::print(){
    node * n=head;
    while(n->next->next!=NULL){
        cout<<n->next->data<<"  ";
        n=n->next;
    }
}
node * queue::outQueue(){//出队
    node * n=tail->prev;
    if(n->prev==NULL){
        return NULL;
    }else{
        n->next->prev=n->prev;
        n->prev->next=n->next;
        n->next=NULL;
        n->prev=NULL;
        return n;
    }
}
int queue::isEmpty(){//判断队列是否为空
    node * n=tail->prev;
    if(n->prev==NULL){
        return 0;
    }else{
        return 1;
    }
}

int main(){//测试
    queue * q=new queue();
    cout<<"入队:1"<<endl;
    q->enQueue(1);
    cout<<"入队:2"<<endl;
    q->enQueue(2);
    cout<<"入队:3"<<endl;
    q->enQueue(3);
    cout<<"入队:4"<<endl;
    q->enQueue(4);
    cout<<"打印:";
    q->print();
    if(q->isEmpty()!=0){
        cout<<endl<<"出队:"<<q->outQueue()->data<<endl;    
    }
    cout<<"打印";
    q->print();
    cout<<endl;
    cout<<"入队:5"<<endl;
    q->enQueue(5);
    cout<<"打印:";
    q->print();
    cout<<endl;
    return 0;
}

结果如下：

image-20221209182332363

列表的应用—农夫过河

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//农夫过河问题
//问题描述：
//有一个农夫带一只羊、一筐菜和一只狼过河
//如果没有农夫看管，则狼要吃羊，羊要吃菜
//但是船很小，只够农夫带一样东西过河
//问农夫该如何解此难题？
//解题思路：
//农夫过河问题，用0000的二进制分别代表河的一岸的农夫、羊、菜、狼，假如农夫带狼过河则0000变为1001。
//总共有16种状态，每次过河的操作(8种操作)都会变成另外一个状态，直到得到1111，可以得到一个状态树，保存满足条件的路径。
//不满足题目要求的状态有1001(9),0110(6),1000(8),1010(10),0101(5),0111(7),即5~10都不合法。
//建立一个当前搜索队列，保存遍历的状态，出现重复的状态则不进行这次变化（避免死循环），若队尾出现0，退出搜索。
#include<iostream>
#include<queue>
using namespace std;
queue<int> q;
int visit[20];//用来保存当前状态的前一状态，注意不能直接int visit[20]={-1}初始化，初始化成0可以，但其他数字要用循环老老实实一个一个赋值
int a[4]={8,12,10,9};//用来表示4种状态转换操作：8(1000)——nothing；12(1100)——sheep；10(1010)——vegetable；9(1001)——wolf。

bool judge(int x){//用来判断是否为合法状态
     if(x>=5&&x<=10) return false; 
     else if(x>15 || x<0) return false;
     else if(visit[x]!=-1) return false;
     else return true;
 }
 
void BFS(){ //树的广度搜索，寻找最短路径
     int current=q.front();
     q.pop();
     for(int i=0;i<4;i++ ){  //每次有四种选择，空船，带羊，带菜，带狼
         int next=a[i]^current; //异或运算，相同为0，不同为1，即求出当前的运动状态
         if(judge(next)){    
	         q.push(next);
	         visit[next]=current; //visit[当前状态]=当前状态的前一个状态
	         if(next == 15) return; //15(1111)
         }
     }
     BFS();
 }
 
void print_result(int a,int b){
    switch(b-a){
        case -8:cout<<"nothing_come"<<endl;break;
        case -12:cout<<"sheep_come"<<endl;break;
        case -10:cout<<"vegetable_come"<<endl;break;
        case -9:cout<<"wolf_come"<<endl;break;
        case 8:cout<<"nothing_go"<<endl;break;
        case 12:cout<<"sheep_go"<<endl;break;
        case 10:cout<<"vegetable_go"<<endl;break;
        case 9:cout<<"wolf_go"<<endl;break;
    }
}
int main(){
    int start=0;
    for(int i=0;i<16;i++) visit[i]=-1; //初始化16种状态
    q.push(start); //从0000开始
    visit[start]=-2; //标记源节点
    BFS();
    int x=15; //15(1111)
    int re[20];//根据visit数组来获得路径顺序，即状态序列
    int index=0;
    while(x!=-2){
        re[index++]=x;
        x=visit[x];
    }
    for(int i=index-1;i>0;i--){//根据a数组即状态序列的变换打印状态转换过程
           print_result(re[i],re[i-1]);
    }
    cout<<"succeed"<<endl;
    return 0;
}

结果如下：

1
2
3
4
5
6
7
8
sheep_go
nothing_come
vegetable_go
sheep_come
wolf_go
nothing_come
sheep_go
succeed
欢迎来到ssy的世界