首页 > 其他分享 >STL-stack和queue堆栈和队列

STL-stack和queue堆栈和队列

时间:2024-01-22 20:13:34浏览次数:37  
标签:priority STL queue 队列 int push include stack

STL-stack和queue堆栈和队列

目录

堆栈和队列特性

stack为堆栈,比较简单, 内部元素都是需要 先进后出,也就是说只有栈顶的元素Top才可以被访问到

队列和栈一样,是一种线性结构,
1、先进先出
2、队尾添加,队首删除
队尾:允许被添加的一端,队首允许被删除的一端
入队,出队

堆栈主要操作

构造函数

#include<stack>

stack<int> st1;
stack<T>  ST;  			 // 支持其他格式

主要操作

- empty     //是否为空
- size		//大小
- push      //入栈
- pop       //出栈

栈顶插入和删除

"""栈顶"""
stack<int> st;
int item=st.top();

// 插入、删除
stack<float>  st;
st.push(item);
st.pop();

大小相关

stack<char> st;

st.size();
st.empty();

简单案例

#include <iostream>  
#include <stack>  
using  namespace  std;  
   
int  main ()  
{  
   stack< int > mystack;  
   
   for  ( int  i=0; i<5; ++i) mystack.push(i);  
   
   cout <<  "Popping out elements..." ;  
   while  (!mystack.empty())  
   {  
      cout <<  " "  << mystack.top();  
      mystack.pop();  
   }  
   cout << endl;  
   
   return  0;  
}

队列的主要操作

构造函数

- empty      	//是否为空
- size			//大小
- front			//访问 队首数据
- back			//访问 队尾数据
- push			//入队
- pop			//出队
#include <queue>
std::queue<int> myQueue;


// 队列
queue<int> q1;

queue<T> 		//这类适配器类都默认封装了一个 deque<T> 容器,也可以通过指定第二个模板类型参数来使用其他类型的容器
vector<int> v1 = {1,2,3,4,5}; 
// 1,2,3,4,5依此入栈
queue<int, vector<int>> q4(v1);
//底层容器必须提供这些操作:front()、back()、push_back()、pop_front()、empty() 和 size()。
    
//优先队列
priority_queue<int> q;
priority_queue<int,vector<int>,greater<int>> q;

大小相关

queue<float> myQueue;

//是否为空,返回为ture,false;
myQueue.empty(); 

// 元素个数  获得元素个数
myQueue.size();
std::cout << "0. size: " << myQueue.size() << std::endl; // 输出:0

索引访问

#include <queue>
// 返回队首元素
queue<int> myqueue3;
myqueue3.push(77);
myqueue3.push(66);

//q.front();     //队首
int& a1 = myqueue3.front(); // 返回队首 77
int a2 = myqueue3.front();  //  返回队首 77
myqueue3.front() = 88;      // 给头元素77赋值为88
cout << "front:" << myqueue3.front() << std::endl; // 输出:88


//返回队尾元素
//q.back();     //队尾
queue<int> myqueue4;
myqueue4.push(15);
myqueue4.push(22);
int& b1 = myqueue4.back();  // 22
int b2 = myqueue4.back();   // 22
myqueue4.back() = 33; 		// 给末尾元素22赋值为33

入队/出队

// q.push(x);      //入队,将元素 x 从队尾插入(尾插法)


queue<int>  q1;
q1.push(1);   //入队
q1.push(2);   //入队
// 添加一个元素(队尾添加)

//q1.pop();       //出队  删除对首元素,并返回其值
q.pop();       
q.pop();

优先队列priority_queue

优先队列是一种会按照默认或自定义的优先级进行自动排序的队列,其特点是优先级高的元素排在队首.

priority_queue<Type, Container, Functional>

Type为数据类型, Container为保存数据的容器,Functional为元素比较方式。
 
如果不写后两个参数,那么容器默认用的是vector,比较方式默认用operator<,也就是优先队列是大顶堆,队头元素最大。

初始化构造

#include<queue>

//默认声明:
priority_queue<int> pq;

//以less为排列规则(大顶堆,表示顶堆元素比其他都大)
priority_queue<int,vector<int>,less<int> > pq;   

//以greater为排列规则(小顶堆,表示顶堆元素比其他都小)
priority_queue<int,vector<int>,greater<int> > pq; 
push(x)  将令 x 入队
top()    可以获得队首元素(即堆顶元素)
pop()    令队首元素(即堆顶元素)出队
empty() 检测优先队列是否为空,返回 true 则空,返回 false 则非空。
size() 返回优先队列内元素的个数

优先队列没有 front() 函数与 back() 函数,而只能通过 top() 函数来访问队首元素

#include<iostream>
#include<queue>
using namespace std;
 
int main(){
	priority_queue<int> p;
	p.push(1);
	p.push(2);
	p.push(8);
	p.push(5);
	p.push(43);
	for(int i=0;i<5;i++){
		cout<<p.top()<< " ";
		p.pop();
	}
	return 0;
}

// 43 8 5 2 1    //默认是大顶堆

小顶堆

priority_queue<int, vector<int>, greater<int> > pq;
//其中,greater是STL内建的关系运算类函数对象(也就是仿函数),并且是一个二元运算符。
#include<iostream>
#include<queue>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,greater<int>> q;
    q.push(3);
    q.push(4);
    q.push(1);
    
    for(int i=0;i<3;i++){
		cout<<q.top()<< " ";
		q.pop();
	}
    return 0;
}
// 1 3 4     //小顶堆

自定义结构体排序

#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct fruit
{
    string name;
    int price;
} f1, f2, f3;


struct cmp
{
    bool operator()(fruit fl, fruit f2)
    {
        return f1.price > f2.price;  // 降序
    }
};
int main()
{
    priority_queue<fruit, vector<fruit>, cmp> q;
    f1.name = "apple";
    f1.price = 3;
    f2.name = "melon";
    f2.price = 4;
    f3.name = "banana";
    f3.price = 1;
    q.push(f1);
    q.push(f2);
    q.push(f3);
    cout << q.top().name << "  " << q.top().price << endl;
    return 0;
}

参考资料

https://blog.csdn.net/dark_cy/article/details/83827622

https://blog.csdn.net/m0_38059875/article/details/105602271

标签:priority,STL,queue,队列,int,push,include,stack
From: https://www.cnblogs.com/tian777/p/17980863

相关文章

  • STL-vector向量
    STL-vector向量目录STL-vector向量1.头文件2.构造函数3.索引存取元素4.遍历元素4.capacity相关5.插入元素6.删除元素7.排序和翻转8.底层原理9.特殊记忆函数总结参考资料vector数组是一个能存放任意数据类型(类,结构,普通变量类型等)的动态数组,在数据结构中就相当于顺序储存的线性......
  • STL-deque双端队列
    STL-deque双端队列目录STL-deque双端队列创建初始化插入元素删除元素遍历容器函数总览deque和vector参考资料deque是double-endedqueue的缩写,又称双端队列容器,可以对其两段的数据进行操作,因为它没有capacity属性,因此不会像vector那样”旧空间不足而重新配置一块更大空间,然后......
  • STL-Set集合
    STL-Set集合目录STL-Set集合导入构造插入删除查找元素遍历元素成员方法multisetunordered_set参考资料set集合unordered_set无序集合set的元素不像map那样可以同时拥有实值和键值,set的元素即是键值又是实值。set不允许两个元素有相同的键值。不允许出现相同的两个se......
  • STL-map/unordered_map映射
    STL-map/unordered_map映射目录STL-map/unordered_map映射1.构造初始化2.数据插入3.数据查找4.迭代器遍历5.删除和清空6.成员方法7.multimap8.unordered_map9.unordered_multimap10.底层原理11.总结12.参考资料键值对容器Map映射是一种类似于字典的数据结构。它是(键,值)对的序......
  • tensorflow-gpu error:CUDNN_STATUS_ALLOC_FAILED或者self._traceback = tf_stack.extr
    tensorflow-gpuerror:CUDNN_STATUS_ALLOC_FAILED或者self._traceback=tf_stack.extract_stack() 在有些情况下,因为深度学习框架版本更新,细节的变动会使我们的代码最初对应修改:报错信息(出现其中一种):1.Couldnotcreatecudnnhandle:CUDNN_STATUS_ALLOC_FAILED2.self._trac......
  • C++中lambda与priority_queue一起使用
    想写这篇博客的原因是在刷力扣的347.前K个高频元素一题时,需要使用到优先队列priority_queue,其定义如下:template<classT,classContainer=std::vector<T>,classCompare=std::less<typenameContainer::value_type>>classpriority_queue;第三个参数......
  • Queue-Linked List Implementation【1月22日学习笔记】
    点击查看代码//Queue-LinkedListImplementation#include<iostream>usingnamespacestd;structnode{ intdata; node*next;};node*front=NULL;node*rear=NULL;//末指针·,则不用遍历整个链表,constanttimevoidEnqueue(intx){ node*temp=newnode; ......
  • 【glibc】glib库队列GQueue介绍
    队列是一种向最后添加条目,从最前删除条目的数据结构,这种数据结构在处理按顺序到达的数据是很有用。glib库提供的队列GQueue是一个双端队列,它的实现基础是双向链表,所以它支持在队列的两端进行添加和删除,也支持很多其它的操作,比如在队列中进行插入和删除,但是我不推荐使用这样的功能......
  • Infix to postfix conversion using stack【1月21日学习笔记】
    点击查看代码//Infixtopostfixconversionusingstack#include<iostream>#include<stack>//stackfromstandardtemplatelibrary(STL)#include<string>usingnamespacestd;stringInfixToPostfix(stringexp);boolHasHigherPrecedence(charopr1,......
  • STL—函数对象
    函数对象概念1、重载函数调用操作符的类,其对象常称为函数对象2、函数对象使用重载的()时,行为类似函数调用,也叫仿函数本质函数对象(仿函数)是一个类,不是一个函数函数对象的使用特点:1、函数对象在使用时,可以像普通函数那样调用,也可以有参数,可以有返回值2、函数对象超出普通函数的概念,函......