【數據結構】STL-stack

std::stack

template <class T, class Container = deque<T> > class stack;
LIFO stack
Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.

stacks are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed/popped from the “back” of the specific container, which is known as the top of the stack.

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall support the following operations:

  • empty
  • size
  • back
  • push_back
  • pop_back

The standard container classes vectordeque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used.

 

Template parameters

T
Type of the elements.
Aliased as member type stack::value_type.
Container
Type of the internal underlying container object where the elements are stored.
Its value_type shall be T.
Aliased as member type stack::container_type.

 

Member types

member type definition notes
value_type The first template parameter (T) Type of the elements
container_type The second template parameter (Container) Type of the underlying container
size_type an unsigned integral type usually the same as size_t

Member functions

std::stack::stack

explicit stack (const container_type& ctnr = container_type());
Construct stack
Constructs a stack container adaptor object.

A container adaptor keeps internally a container object as data. This container object is a copy of the ctnr argument passed to the constructor, if any, otherwise it is an empty container.

 

Parameters

ctnr
Container object.
container_type is the type of the underlying container type (defined as an alias of the second class template parameter, Container; see member types).
alloc
Allocator object.
Alloc shall be a type for which uses_allocator::value is true (for other types, the constructor does not even participate in overload resolution).
x
stack of the same type (i.e., with the same template arguments, T and Container).

Example

// 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

Complexity

One container construction (which for standard containers is up to linear in its size).

std::stack::empty

bool empty() const;
Test whether container is empty
Returns whether the stack is empty: i.e. whether its size is zero.

This member function effectively calls member empty of the underlying container object.

Parameters

none

Return Value

trueif the underlying container‘s size is 0, false otherwise.

Example

// 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;
}

 

The example initializes the content of the stack to a sequence of numbers (form 1 to 10). It then pops the elements one by one until it is empty and calculates their sum.

Output:

total: 55

Complexity

Constant (calling empty on the underlying container).

std::stack::size

size_type size() const;
Return size
Returns the number of elements in the stack.

This member function effectively calls member size of the underlying container object.

Parameters

none

Return Value

The number of elements in the underlying container.

Member type size_type is an unsigned integral type.

Example

// 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

Complexity

Constant (calling size on the underlying container).

std::stack::top

      value_type& top();
const value_type& top() const;
Access next element
Returns a reference to the top element in the stack.

Since stacks are last-in first-out containers, the top element is the last element inserted into the stack.

This member function effectively calls member back of the underlying container object.

Parameters

none

Return value

A reference to the top element in the stack.

Member type value_type is the type of the elements in the container (defined as an alias of the first class template parameter, T).

Example

// 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;
}
Edit & Run

Output:

mystack.top() is now 15

Complexity

Constant (calling back on the underlying container).

std::stack::push

void push (const value_type& val);
Insert element
Inserts a new element at the top of the stack, above its current top element. The content of this new element is initialized to a copy of val.

This member function effectively calls the member function push_back of the underlying container object.

Parameters

val
Value to which the inserted element is initialized.
Member type value_type is the type of the elements in the container (defined as an alias of the first class template parameter, T).

Return value

none

Example

// 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

Complexity

std::stack::pop

One call to push_back on the underlying container.
void pop();
Remove top element
Removes the element on top of the stack, effectively reducing its size by one.

The element removed is the latest element inserted into the stack, whose value can be retrieved by calling member stack::top.

This calls the removed element’s destructor.

This member function effectively calls the member function pop_back of the underlying container object.

Parameters

none

Return value

none

Example

// 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

Complexity

Constant (calling pop_back on the underlying container).

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注