Stack

From DmWiki

A stack is a simple data structure that works on the FILO (First In Last Out) principle. This simply means that the last item you "push" (add) onto the stack is the first item you "pop" (remove) from the stack. It’s easy to imagine a simple stack of common household plates when thinking about the workings of a stack.

Table of contents

1 Types of Stacks 1.1 Static-Length Stacks 1.2 Dynamic-Length Stacks 2 STL Stacks in C++ 3 Uses of Stacks

Types of Stacks

Stacks are generally implemented in two ways. A static-length stack has a given size and cannot be changed, and a variable-length stack changes its size whenever entries are pushed and popped.

Static-Length Stacks

A simple implementation of a static-length stack would use an array. The first entry in the array would be the "bottom" of the stack, and the last entry that contained data would be the "top".

#define STACK_SIZE 256
struct Stack {
    char data[STACK_SIZE];
    int num_entries = 0;
};

void push (Stack &stack, char data) {
    if (stack.num_entries == STACK_SIZE)
        return; // error, stack overflow
    stack.data[stack.num_entries] = data;
    ++stack.num_entries;
}

char pop (Stack &stack) {
    if (stack.num_entries == 0)
        return; // error, stack underflow
    --stack.num_entries;
    return stack.data[stack.num_entries];
}

Dynamic-Length Stacks

A simple implementation of a dynamic-length stack would be based on a linked list. In this case, the head of the linked list would be the top of the stack.

STL Stacks in C++

The Standard Template Library included with C++ features a ready-to-use stack container. It is used like this:

std::stack<datatype> stackname;
stackname.push(value);
value2=stackname.top(); //value2 now equals value
stackname.pop();        //stack is now empty

Uses of Stacks

TODO: uses of stacks

• function calls
• mathematical calculations
• anytime you need to "pause" what you're working on, work on something else for awhile, and then resume where you were before - especially if the "work on something else" might involve more pause/resume cycles

This article is a stub. You can help improve the article by expanding it.