STL模板总结归纳（stack,queue和priority_queue）

た入场券 2022-09-29 12:56 188阅读 0赞

**1.stack**： 堆栈是一个线性表，插入和删除只在表的一端进行。这一端称为栈顶(Stack Top)，另一端则为栈底(Stack Bottom)。堆栈的元素插入称为入栈，元素的删除称为出栈。由于元素的入栈和出栈总在栈顶进行，因此，堆栈是一个后进先出(Last In First Out)表，即 LIFO 表。

![20170315214116588][]

//----------------------------------------- 读取堆栈的栈顶元素
    #include <stack>
    #include <iostream>
    using namespace std;
    int main()
    {
        // 创建堆栈对象
        stack<int> s;
        // 元素入栈
        s.push(3);
        s.push(19);
        s.push(23);
        s.push(36);
        s.push(50);
        s.push(4);
    
        // 元素依次出栈
        while(!s.empty())
        {
            // 打印栈顶元素，打印出：4 50 36 23 19 3
            cout << s.top() << endl;
            // 出栈
            s.pop();
        }
    
        return 0;
    }

参考例题：TOJ 1218（代码来自wyt）

#include<iostream>
    #include<string>
    #include<stack>
    using namespace std;
    int main()
    {
    	stack<int> s;
    	int a;
    	int t;
    	string s1;
    	while (cin >> s1)
    	{
    		if (s1 == "push")
    		{
    			cin >> a;
    			s.push(a);
    		}
    		else if (s1 == "top")
    		{
    			if (s.size()>0)
    			cout << s.top() << endl;
    			else
    			cout << "None" << endl;
    		}
    		else if (s1 == "pop")
    		{
    			if (s.size() > 0)
    			{
    				cout << s.top() << endl;
    				s.pop();
    			}
    			else
    			cout << "None" << endl;
    		}
    		else if (s1 == "exit")
    		break;
    		else if (s1 == "clear")
    		{
    			while (!s.empty())
    			{
    				t = s.top();
    				s.pop();
    			}
    		}
    	}
    }

**2.queue**：  queue单向队列与栈有点类似，一个是在同一端存取数据，另一个是在一端存入数据，另一端取出数据。单向队列中的数据是先进先出（First In First Out,FIFO）。

queue 的基本操作有：  
入队，如例：q.push(x); 将x 接到队列的末端。  
出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。  
访问队首元素，如例：q.front()，即最早被压入队列的元素。  
访问队尾元素，如例：q.back()，即最后被压入队列的元素。  
判断队列空，如例：q.empty()，当队列空时，返回true。  
访问队列中的元素个数，如例：q.size()。

注意：出队列时要先调用front()取得第一个元素，再调用pop().

**3.priority\_queue：**

**优先级默认是最大顶堆，若要用最小的：** `priority_queue<` `int` `, vector<` `int` `>, greater<` `int` `> > q;`

代码举例：  
 ``

#include <iostream>
    #include <queue>
    using namespace std;
    int main()
    {
        priority_queue<int, vector<int>, greater<int> > q;
        for( int i= 0; i< 10; ++i ) 
    	q.push( rand() );
        while( !q.empty() )
    	{
            cout << q.top() << endl;
            q.pop();
        }   
        getchar();
        return 0;
    }

[20170315214116588]: /images/20220708/63db9dc2b22e46eface4ff353de2a9a5.png