STXXL Stack

This section introduces into the STXXL stack container (to learn more about the structure of stxxl::stack, see section Stack).

STXXL stacks are last in first out (LIFO), i.e. inserting and extracting elements are only allowed from one end of the container and the element on top is the element added most recently.

Creating a STXXL stack

Before using a STXXL stack, we initially have to define and then to instantiate a stack object. To manage the configuration of the stack type we used the generator template. A minimal configuration is shown below - as one can see the value_type (integer in our case) is the only stricly neccessary parameter. See stxxl::STACK_GENERATOR for additional configuration parameters and information.

typedef stxxl::STACK_GENERATOR<int>::result stack;
stack my_stack;  // create empty stack object

Hint: STXXL stack provides specialized implementations for a certain access pattern. If the access pattern is known before, such a customization might gain a significant speedup. The default stack is stxxl::normal_stack which is the best for a random sequence of push'es and pop's. See Stack section for more details.

Insert / Access / Delete elements

To insert an element on top of the stack call push():

my_stack.push(7);
my_stack.push(2);
my_stack.push(5);
// stack from bottom to top: |7|2|5|

To access the top element call top():

std::cout << "element on top of stack is: " << my_stack.top << std::endl;  // prints out 5

To remove the top element call pop().

my_stack.pop();  // removes element 5

Determine size / Check whether stack is empty

To determine the size (i.e. the number of elements) of stack instance, call size():

std::cout << "size of stack: " << my_stack.size() << std::endl;

To check if the stack is empty, call empty() which returns true in case of emptyness:

// loop till stack is empty
while (!my_stack.empty())
{
  // do something
}

A minimal working example of STXXL's stack

(See examples/containers/stack1.cpp for the sourcecode of the following example).

#include <stxxl/stack>

int main()
{
    typedef stxxl::STACK_GENERATOR<int>::result stack_type;
    stack_type my_stack;

    my_stack.push(8);
    my_stack.push(7);
    my_stack.push(4);
    assert(my_stack.size() == 3);

    assert(my_stack.top() == 4);
    my_stack.pop();

    assert(my_stack.top() == 7);
    my_stack.pop();

    assert(my_stack.top() == 8);
    my_stack.pop();

    assert(my_stack.empty());

    return 0;
}

See examples/containers/stack2.cpp for the sourcecode of a more comprehensive example.