A stack overflow typically occurs when a new element must be pushed onto a stack, but the stack doesn't have sufficient memory in which to place the new element. We can liken this to a cup; when we try to fill it with more water than it can physically hold it will overflow.

Stacks are normally dynamic structures that grow and shrink as elements are pushed and popped from them and therefore do not (or should not) suffer from stack overflows. We can still run into problems if there is insufficient memory in which to grow the stack, however that is another problem entirely; it has nothing to do with stack overflow -- it's a systemic memory allocation problem.

Stack overflows only occur in fixed-length stacks where a new element is pushed onto the stack when the stack is already full or there is insufficient capacity for the new element. The main problem here is what do we do with the new element? The best solution is to simply throw an exception and let the caller (the code that invoked the push operation) deal with the problem.

Stack overflows can also occur at the system level. Every thread of execution has its own thread-local call stack and each time we invoke a function we consume a stack frame that holds the function's local variables, formal arguments, return address and exception handling information. However, call stacks are fixed-length and thus have a limited capacity. When we overflow a call stack, the system generates a stack overflow error and terminates the process because there's simply no way to recover from this; we've invoked a function for which a stack frame cannot be generated. Recursive functions are particularly susceptible to stack overflow errors.

A stack underflow (or underrun as it's more usually called) occurs when we try to pop an element from an empty stack. For example:

std::stack<int> stk;

stk.push (42);

stk.pop();

stk.pop(); // stack underflow...

We can guard against this by testing if the stack is empty before popping:

std::stack<int> stk; stk.push (42);

if (!stk.empty()) stk.pop(); // ok

if (!stk.empty()) stk.pop(); // stack underflow avoided...

However, this is often inefficient as an underrun is (or at least should be) a rare occurrence; an exceptional circumstance. Like all exceptions, we should provide an exception handler to deal with it:

std::stack<int> stk;

stk.push (42);

try {

stk.pop();

}

catch (std::exception& e) {

// handle the exception...

}

Underruns often occur in data structures used for buffering. Typically we use buffers in order to synchronise two processes executing at different frequencies, typically where one process must operate at a fixed frequency. For example, when writing data to a DVD we can usually read data from the hard-drive much quicker than we can physically write it to DVD, so we use a buffer to "queue" the data that is waiting to be written. We begin writing when the buffer is full and as each element is popped from the front of the buffer to be written to the DVD, a new element is pushed onto the back of the buffer. The reading process may be interrupted briefly by other processes that require access to the hard-drive, but so long as the queue contains data waiting to be written this won't affect the writing process. An underrun will only occur if the reading process is interrupted to the extent the queue is emptied completely. While DVD hardware and software can guard against this to a certain degree, if there are too many underruns during a write, the DVD could be corrupted. Digital audio playback is another example; whenever an underrun occurs, we hear the audio stuttering.

Stacks aren't generally use for buffering as such because the data isn't being "queued" for processing in the order that it arrives; first-in, first-out (or FIFO). A stack is a last-in, first-out (or LIFO) structure and we usually use them in backtracking algorithms, however we must still guard against stack overflows and underruns or at least throw exceptions when they occur so the callers can deal with them in an appropriate manner.

Resources

Top Categories

Product

Company