C++ Stack(堆栈) 是一个容器类的改编,为程序员提供了堆栈的全部功能,——也就是说实现了一个先进后出(FILO)的数据结构。

c++ stl栈stack的头文件为

#include <stack> 

c++ stl栈stack的成员函数介绍

操作 比较和分配堆栈

empty() 堆栈为空则返回真

pop() 移除栈顶元素

push() 在栈顶增加元素

size() 返回栈中元素数目

top() 返回栈顶元素

 

 

栈(stack)是限制插入和删除只能在一个位置上进行的线性表,该位置在表的末端,叫做栈顶。添加元素只能在尾节点后添加,删除元素只能删除尾节点,查看节点也只能查看尾节点。添加、删除、查看依次为入栈(push)、出栈(pop)、栈顶节点(top)。形象的说,栈是一个先进后出(LIFO)表,先进去的节点要等到后边进去的节点出来才能出来。

如图1,是一个栈的形象图,top指针指向的是栈顶节点,所以我们可以通过top访问到2节点,但是0和1节点由于先于2进入这个表,所以是不可见的。如果把0节点当做头节点,2节点当做尾节点,那么栈限制了访问权限,只可以访问尾节点。

如图2,当添加一个节点3的时候,只能在栈顶节点,也就是尾节点后添加,这样3节点变成了栈顶,2节点变成了不可见节点,访问的时候只能访问到3节点。入栈时限制了插入地址,只能在栈顶添加节点。

当我们执行出栈的命令时,图2的栈顶元素是3节点,删除的时候只能允许删除栈顶的元素,这样子3节点被删除,top指向删除后的栈顶2节点,如图3所示。

栈有两种是实现结构,一种是顺序存储结构,也就是利用数组实现,一种是链式存储结构,可以用单链表实现。数组实现栈很简单,用一个下标标记top来表示栈顶,top==-1时,栈空,top==0时,表示栈里只有一个元素,通过访问top为下标的数组元素即可。出栈top自减,入栈top自加就OK了。

单链表实现栈要比单链表的实现简单点。我们通过在表的尾端插入来实现push,通过删除尾节点来实现pop,获取尾节点的元素来表示top。我修改了链表那一章的单链表代码,把头节点当做栈顶节点,实现了一个简单的栈模板,仅供学习所用。代码会不定时更新。代码下载

=====================================================================================================

写在前面

这一篇博客系统学习一下C++中stack这个容器。根据维基百科——堆栈解释:

堆栈(英语:stack)又称为栈或堆叠,是计算机科学中一种特殊的串列形式的抽象资料型别,其特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。另外栈也可以用一维数组或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列。

由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

与之前一样,主要根据CPlusPlus官网stack容器介绍内容进行整理:std::stack

stack类与头文件包含

stack头文件引用如下:

#include <stack> 

stack::stack

构造一个stack,可使用方法如下,代码来自:std::stack::stack

// constructing stacks
#include <iostream>       // std::cout
#include <stack>          // std::stack
#include <vector>         // std::vector
#include <deque>          // std::deque

int main ()
{
  std::deque<int> mydeque (3,100);          // deque with 3 elements
  std::vector<int> myvector (2,200);        // vector with 2 elements

  std::stack<int> first;                    // empty stack
  std::stack<int> second (mydeque);         // stack initialized to copy of deque

  std::stack<int,std::vector<int> > third;  // empty stack using vector
  std::stack<int,std::vector<int> > fourth (myvector);

  std::cout << "size of first: " << first.size() << '\n';
  std::cout << "size of second: " << second.size() << '\n';
  std::cout << "size of third: " << third.size() << '\n';
  std::cout << "size of fourth: " << fourth.size() << '\n';

  return 0;
}
//
//Output:
//size of first: 0
//size of second: 3
//size of third: 0
//size of fourth: 2

从以上代码可以得知stack可以直接创建一个空白的,也可以由queue和vector创建。

stack-Member functions

这里写图片描述

1.stack::empty
测试容器是否为空,返回堆栈是否为空:即其大小是否为零。该成员函数有效地将成员空的底层容器对象调用为空。

代码如下:

// stack::empty
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;
  int sum (0);

  for (int i=1;i<=10;i++) mystack.push(i);

  while (!mystack.empty())
  {
     sum += mystack.top();
     mystack.pop();
  }

  std::cout << "total: " << sum << '\n';

  return 0;
}
\\Output:
\\total: 55

2.stack::size
返回大小,返回堆栈中元素的数量。该成员函数有效地调用底层容器对象的成员大小。

代码如下:

// stack::size
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> myints;
  std::cout << "0. size: " << myints.size() << '\n';

  for (int i=0; i<5; i++) myints.push(i);
  std::cout << "1. size: " << myints.size() << '\n';

  myints.pop();
  std::cout << "2. size: " << myints.size() << '\n';

  return 0;
}
//Output:
//0. size: 0
//1. size: 5
//2. size: 4

3.stack::top
访问下一个元素,返回堆栈中顶层元素的引用。由于堆栈是后进先出容器,顶层元素是插入到堆栈中的最后一个元素。该成员函数有效地调用底层容器对象的成员。

代码如下:

// stack::top
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  mystack.push(10);
  mystack.push(20);

  mystack.top() -= 5;

  std::cout << "mystack.top() is now " << mystack.top() << '\n';

  return 0;
}
//Output:
//mystack.top() is now 15
  •  

4.stack::push
插入元素,在堆栈的顶部插入一个新元素,位于当前顶层元素的上方。 这个新元素的内容被初始化为val的副本。该成员函数有效地调用底层容器对象的成员函数push_back。

代码如下:

// stack::push/pop
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  for (int i=0; i<5; ++i) mystack.push(i);

  std::cout << "Popping out elements...";
  while (!mystack.empty())
  {
     std::cout << ' ' << mystack.top();
     mystack.pop();
  }
  std::cout << '\n';

  return 0;
}

4.stack::emplace
构建并插入元素,在堆栈顶部添加一个新元素,位于当前顶层元素上方。 这个新元素是通过构造函数的参数传递参数构建的。该成员函数有效地调用底层容器的成员函数emplace_back,并转发参数。

代码如下:

// stack::emplace
#include <iostream>       // std::cin, std::cout
#include <stack>          // std::stack
#include <string>         // std::string, std::getline(string)

int main ()
{
  std::stack<std::string> mystack;

  mystack.emplace ("First sentence");
  mystack.emplace ("Second sentence");

  std::cout << "mystack contains:\n";
  while (!mystack.empty())
  {
    std::cout << mystack.top() << '\n';
    mystack.pop();
  }

  return 0;
}

5.stack::pop

// stack::push/pop
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> mystack;

  for (int i=0; i<5; ++i) mystack.push(i);

  std::cout << "Popping out elements...";
  while (!mystack.empty())
  {
     std::cout << ' ' << mystack.top();
     mystack.pop();
  }
  std::cout << '\n';

  return 0;
}
//Output:
//Popping out elements... 4 3 2 1 0

6.stack::swap
交换内容,用x的内容交换容器适配器(* this)的内容。该成员函数调用非成员函数swap(unqualified)来交换基础容器。noexcept说明符匹配底层容器上的交换操作。

// stack::swap
#include <iostream>       // std::cout
#include <stack>          // std::stack

int main ()
{
  std::stack<int> foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);

  foo.swap(bar);

  std::cout << "size of foo: " << foo.size() << '\n';
  std::cout << "size of bar: " << bar.size() << '\n';

  return 0;
}
//Output:
//size of foo: 2
//size of bar: 3
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐