发表于 2020-09-12 08:09:00   |   已被 访问: 118 次   |   分类于:   C++   |   暂无评论

stack 容器

C++ STL 中的 stack 容器是一种容器适配器（container adaptor），可以用来在 C++ 程序中复制堆栈数据结构，和编程语言概念中的常规堆栈数据结构类似，stack 容器也是“后进先出”，元素从一端被插入，也在同一端被删除，该端通常被称作“栈顶”。

如上图所示，stack 容器内最先被插入的元素，只能在最后被删除。

如果希望使用 stack 容器，需要在代码中包含头文件：

#include <stack>

一般来说，定义一个 stack 容器对象的语法如下：

stack<obj type> stackName;

stack 容器类的操作

接下来将讨论 STL 中的 stack 容器类的各种操作。

• push：push 操作用于将元素插入到 stack，正如前面讨论的，push 总是把元素插入到栈顶。

下图是一个 int 类型的 stack 容器对象 mystack：

添加元素 1 到 mystack：

添加元素 1 到 mystack

然后再添加元素 3 到 mystack:

添加元素 3 到 mystack

每次添加的新元素都位于栈顶位置，每次添加容器的 size 都增加 1。

• pop：pop 操作用于从 stack 容器中取出（remove）一个元素，被取出的元素位于栈顶，该操作完成后，stack 的 size 减 1。

我们的 mystack 已经包含两个元素了，如下图：

现在，我们调用 pop() 函数，正如前面介绍的，栈顶元素被取出（remove），mystack 的 size 由 2 变为 1，也即只包含一个元素了：

从 mystack 取出一个元素

再调用一次 pop() 函数，仅存的元素 1 也被取出，mystack 变为一个空 stack：

mystack 变为一个空 stack

• top：返回 stack 中的栈顶元素
• empty：返回 stack 是否为空
• size：返回 stack 的 size，也即 stack 中的元素数量

下面这段代码是操作C++中 stack 容器类的一个完整示例：

#include <iostream>
#include <stack>
using namespace std;
void printStack(stack <int> stk)
{
   while (!stk.empty())
      {
         cout << '\t' << stk.top();
         stk.pop();
      }
   cout << '\n';
}
 
int main ()
{
   stack <int> oddstk;
   oddstk.push(1);
   oddstk.push(3);
   oddstk.push(5);
   oddstk.push(7);
   oddstk.push(9);
 
   cout << "The stack is : ";
   printStack(oddstk);
 
   cout << "\nSize of stack: " << oddstk.size();
   cout << "\nTop of stack: " << oddstk.top();
   cout << "\noddstk.pop() : ";
   oddstk.pop();
   printStack(oddstk);
   cout<<"\nAnother pop(): ";
   oddstk.pop();
   printStack(oddstk);
   return 0;
}

编译并执行这段代码，输出如下：

# g++ t.cpp -std=c++11
# ./a.out 
The stack is :     9    7    5    3    1

Size of stack: 5
Top of stack: 9
oddstk.pop() :     7    5    3    1

Another pop():     5    3    1

queue

queue 是STL中的另一个容器，它也非常简单和有用。queue 容器与C++中队列数据结构非常相似，正如“队列”这个名字的字面意思，和 stack 容器不同，queue 容器有两个端点——前端和后端，其中的元素遵守“先进先出”的规则，也即新来的元素被插到 queue 容器的后面，最先被插入的元素最先被使用和删除。

如果希望在C++程序中使用 queue 容器，需要包含头文件：

#include <queue>

定义一个 queue 对象的代码可以如下实现：

queue<obj type> myqueue;

queue 的操作

和 stack 容器一样，我们也可以使用类似的函数方法操作 queue 容器。

• push：将元素插入到 queue 尾部
• pop：从 queue 头部取出（remove）第一个元素

下面将以整型的 queue 对象为例介绍一下相关的基本操作：

queue<int> myqueue;

myqueue.push(2);

上面两行C++代码定义了一个 int 型的 queue 容器对象 myqueue，并且调用了 push 方法往队列中插入了一个元素，此时 myqueue 如下图所示：

接着，我们继续调用 push 方法，添加元素 “4” 进入 myqueue，按照前面所讨论的，新来的元素将被插入到 queue 容器尾部：

现在，使用 pop 方法从 queue 中取出元素：

myqueue.pop();

从上图可以看出，当调用 pop() 方法后，queue 前端的元素被取出（remove）了，这意味着第一个被插入到 queue 中的元素第一个出列。

• front：返回 queue 中第一个元素的引用
• back：返回 queue 中最后一个元素的引用
• empty：检查 queue 是否为空，也即检查 queue 中是否有元素
• size：返回 queue 的 size，也即 queue 中元素的数目。

下面这段C++代码是一段完整使用 queue 的代码：

#include <iostream>
#include <queue>
using namespace std;
void printQueue(queue <int> myqueue)
{
   queue <int> secqueue = myqueue;
   while (!secqueue.empty())
   {
      cout << '\t' << secqueue.front();
      secqueue.pop();
   }
   cout << '\n';
}
int main()
   {
      queue <int> myqueue;
      myqueue.push(2);
      myqueue.push(4);
      myqueue.push(6);
      myqueue.push(8);
      cout << "The queue myqueue is : ";
      printQueue(myqueue);
      cout << "\nmyqueue.size() : " << myqueue.size();
      cout << "\nmyqueue.front() : " << myqueue.front();
      cout << "\nmyqueue.back() : " << myqueue.back();
      cout << "\nmyqueue.pop() : ";
      myqueue.pop();
      printQueue(myqueue);
      return 0;
   }

编译并执行这段C++代码，得到的输出如下：

The queue myqueue is :    2    4    6    8

myqueue.size() : 4
myqueue.front() : 2
myqueue.back() : 8

myqueue.pop() :    4    6    8

本文主要来自：https://www.softwaretestinghelp.com/stacks-and-queues-in-stl/