C++标准模板库STL stack(栈)及queue(队列)介绍

古城微笑少年丶 2023-02-19 15:25 48阅读 0赞

[算法笔记总目录][Link 1]  
一、stack  
要使用stack,应先添加头文件\#include ,并在头文件下面加，上“using namespacestd;"，然后就可以使用了.  
其定义的写法和其他STL容器相同，typename 可以任意基本数据类型或容器:

stackc typename name ;

注：stack容器内元素只能访问栈顶  
(1) push()  
push(x)将x入栈，时间复杂度为0(1),  
(2) top()  
top()获得栈顶元素，时间复杂度为0(1).  
(3) pop()  
pop()用以弹出栈顶元素，时间复杂度为0(1)。  
(4)empty()  
empty()可以检测stack 内是否为空，返回true为空，返回false 为非空，时间复杂度为0(1)。  
(5)size()  
size()返回stack内元素的个数，时间复杂度为0(1)。

//stack常用函数代码整合 
    #include <iostream>
    #include <stack>
    using namespace std;
    
     
    int main() { 
    	stack<int> st;
    	//---1、2、3---push()、top()、pop() 
    	for(int i = 1;i <= 5;i++){ 
    		st.push(i);//将i压入栈 
    	}
    	cout<<"入栈12345的栈顶为：";
    	cout<<st.top()<<endl;
    	for(int i = 1;i <= 3;i++){ 
    		st.pop();
    	}
    	cout<<"出栈3个元素后栈顶为：";
    	printf("%d\n",st.top());
    	//---4---empty()
    	cout<<"此时栈为空吗？"<<endl;
    	if(st.empty() == true)printf("Empty\n");
    	else	printf("Not Empty\n");
    	//---5---size()
    	cout<<"此时队列大小为："<<st.size()<<endl;
    
    	return 0;
    }

stack用来模拟实现一些递归, 防止程序对栈内存的限制而导致程序运行出错。一般来说，.  
程序的栈内存空间很小，对有些题目来说，如果用普通的函数来进行递归，一旦递归层数过  
深(不同机器不同，约几千至几万层)，则会导致程序运行削溃。如果用栈来模拟递归算法的  
实现，则可以避免这-方面的问题(不过这种应用出现较少)。  
二、queue  
要使用queue,应先添加头文件\#include ,并在头文件下面加上“using namespace  
std;,",然后就可以使用了。  
其定义的写法和其他STL容器相同，typename 可以是任意基本数据类型或容器:

queuec typename > name;

只能通过front()来访问队首元素，或是通过back()来访问队尾元素  
push(x)将x进行入队，时间复杂度为0(1)  
front()和back()可以分别获得队首元素和队尾元素，时间复杂度为0(1)  
pop()令队首元素出队，时间复杂度为0(1)。  
empty()检测queue是否为空，返回true则空，返回false则非空。时间复杂度为0(1)。  
size()返回queue内元素的个数，时间复杂度为0(1)。

//queue函数代码整合 
    #include <iostream>
    #include <queue>
    using namespace std;
    
    int main(){ 
    	queue<int> q;
    	cout<<"初始化queue q为："; 
    	if(q.empty() == true){ 
    		printf("Empty!");
    	}
    	cout<<endl; 
    	
    	//----1---push() 
    	for(int i = 1;i <= 5;i++){ 
    		q.push(i);//push(i)用以将i压入队列，依次入队1 2 3 4 5 
    	}
    	
    	//----2---front()、back() 
    	printf("%d %d\n",q.front(),q.back());
    
    	//----3---pop()
    	for(int i = 1;i <= 3;i++){ 
    		q.pop();//输出队首元素3次，依次输出1 2 3 
    	}
    	printf("%d\n",q.front(),q.back());
    	
    	//----4---empty()
    	cout<<"此时q为空吗，不为空有几个元素："; 
    	if(q.empty() == false){ 
    		printf("Not Empty!\n");
    	}
    
    	//----5---size()
    	cout<<"此时q有"<<q.size()<<"个元素";
    	cout<<endl;
    	return 0;
    }

当需要实现广度优先搜索时，可以不用自己手动实现:一个队列，而是用queue作为代替，以提高程序的准确性。另外有一点注意的是， 使用frontO和pop0函数前，必须用empty0判断队列是否为空，否则可能因为队空而出现错误。  
延伸: STL的容器中还有两种容器跟队列有关，分别是双端队列(deque)和优先队列(priority\_ queue), 前者是首尾皆可插入和删除的队列,后者是使用堆实现的默认将当前队列最大元素置于队首的容器。其中优先队列将在6.6节进行介绍，而双端队列则留给有兴趣的读者去了解，此处不再多作介绍。  
三、栈的概念  
栈是一种先进后出的数据结构  
![在这里插入图片描述][20200621141004787.png]  
常用函数  
\#\#\#（1）清空(clear)  
\#\#\#（2）获取栈内元素个数(size)  
\#\#\#（3）判空(empty)  
\#\#\#（4）进栈(push)  
\#\#\#（5）出栈(pop)  
\#\#\#（6）取栈顶元素(top)

//栈的函数代码整理
    #include <iostream>
    #include <cstdio>
    void clear(){ 
    	TOP = -1;
    }
    int size(){ 
    	return TOP + 1;
    }
    bool empty(){ 
    	if(TOP == -1)	return true;
    	else	return false;
    }
    void push(int x){ 
    	st[++TOP] = x;
    }
    int top(){ 
    	return st[TOP];
    }
    
    int main() { 
    	
    	return 0;
    }

四、队列  
队列是一种先进先出的数据结构，区别于栈  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]  
队列总是在队尾加入元素，而从队首移除元素，一般队首指针front指向队首元素的前一个位置，队尾指针rear指向队尾元素。  
\#\#\#（1）清空(clear)  
\#\#\#（2）获取栈内元素个数(size)  
\#\#\#（3）判空(empty)  
\#\#\#（4）入队(push)  
\#\#\#（5）出队(pop)  
\#\#\#（6）取队首元素(get\_front)  
\#\#\#（7）取队尾元素(get\_rear)

//队列的函数代码整理
    #include <iostream>
    #include <cstdio>
    #include <queue>
    #define MAXSIZE 100
    
    typedef int elemtype;
    typedef struct{ 
    	elemtype data[MAXSIZE];
    	elemtype front,rear;
    	int len;
    }SqQueue;
    void clear(SqQueue &Q){ 
    	Q.front = Q.rear = -1;
    }
    int size(){ 
    	return rear - front;
    }
    bool empty(){ 
    	if(front == rear)	return true;
    	else	return false;
    }
    void push(int x){ 
    	q[++rear] = x;
    }
    void pop(){ 
    	front++;
    }
    int get_front(){ 
    	return q[front+1];
    }
    int get_rear(){ 
    	return q[rear];
    }
    int main() { 
    	
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70 1]

[Link 1]: https://blog.csdn.net/qq_21480607/article/details/106660085
[20200621141004787.png]: https://img-blog.csdnimg.cn/20200621141004787.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200621141638448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200621141836783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxNDgwNjA3,size_16,color_FFFFFF,t_70