implementing a stack

It depends, what's your reasoning for wanting to know about the implementations of a stack? Is it for learning purposes or practical purposes?

Personally I deal in the practical side of things usually, so:

#include <stack>

std::stack s;
s.push(9);
s.pop();

The default underlying containing of the std::stack is a std::deque.

purely acedemic reasons, i've been building a little library just for learning purposes, vectors, linked lists, matrices.

are the only 2 viable options arrays and linked lists?

Quote:

Original post by godsenddeath are the only 2 viable options arrays and linked lists?

Pretty much. Like I said the default implementation of std::stack is a std::deque which is often implemented as a sequence (linked list or otherwise) of arrays (pages). So it has dynamic growth efficiencies similar to a linked list but with access efficiencies similar to a std::vector. I can't recall the exact details (they may be in that link from my previous post) but you get the idea.

Yes, a linked list would be a good underlying data structure for a stack. The only methods that you would need would be an addFirst, and removeFirst if you think of the first element as the top of the stack. Or conversely addLast and removeLast if you think of the last element as the top of the stack.

Example structure:

|Head| --> null if empty

|Head| --> |Top| one element

|Head| --> |Top| --> |Top - 1| --> .... --> |Last|


The two methods should not take a long time to code, and you should not over engineer your solution if a simple stack is what you need. If on the other hand you want to implement a robust solution with potential code reuse you should code a doubly linked list with a dummy node. Keep in mind this is for you own personal learning purposes, and to understand how the data structure is implemented.

The difference between a linked list and array implementation of a stack is the that you don't have to worry about resizing the array when it gets full. The only other thing that I can think about is that if you need for some reason access specific elements in the stack (highly unlikely because the stack operations are only push() and pop()), then the array implementation gives you that advantage because you can access elements in constant time.

So here is what I would suggest as far as code goes:

// Adds an element at the top of the stack.
push() a.k.a. addFirst()

// Removes an element from the top of the stack.
pop() a.k.a. removeFirst()

// Returns the element of the stack without modifying the structure
peek()

// Returns true if the stack contains no elements
isEmpty()

Hope that helps and good luck.

If i were to code a stack, i think a double linked-list would work best. For each node, not only would you have a pointer to a child node(which is your typical linked list(a singly list)), you would also have a pointer to the parent.

Quote:

Original post by fitfool If i were to code a stack, i think a double linked-list would work best. For each node, not only would you have a pointer to a child node(which is your typical linked list(a singly list)), you would also have a pointer to the parent.

Stack benefits very little from linked list, and nothing from double linked list. One will never be inserting in the middle, and removal is always on single (first) node.

Stack is not a queue. One always accesses only the top (bottom) element. One will never be inserting from middle or back, one doesn't need to traverse the elements externally, even size is not an issue.



Linked list has one and only benefit that its growth is finer grained. But the greatest benefit of LL, the ability to insert at middle efficiently, something which is not possible with arrays, is completely lost in case of stack.

When used for performance reasons, stacks are typically implemented as fixed size structures (recursion unrolling, where size can be calculated from algorithm). This approach will always be preferred, since access to elements is effectively free.

If maximum size constraint is undesirable, then the aforementioned paging will work better.

Perhaps the only case where I could imagine linked list being used for stack would be in lock-less stack implementation, but even in those, the maximum number of nodes in stack is typically fixed and pre-allocated (issues however transced the ADT stack by far and complications are too numerous to list).

But for everything else, I find linked lists to be simply sub-optimal for stack, with possible exception of certain memory configurations (the overhead however is still hard to justify compared to occasional resize).

wow that was a lot of good information, and fast. thank you very much for the help.

Quote:

Original post by Antheus Stack benefits very little from linked list, and nothing from double linked list. One will never be inserting in the middle, and removal is always on single (first) node. Stack is not a queue. One always accesses only the top (bottom) element. One will never be inserting from middle or back, one doesn't need to traverse the elements externally, even size is not an issue. Linked list has one and only benefit that its growth is finer grained. But the greatest benefit of LL, the ability to insert at middle efficiently, something which is not possible with arrays, is completely lost in case of stack. When used for performance reasons, stacks are typically implemented as fixed size structures (recursion unrolling, where size can be calculated from algorithm). This approach will always be preferred, since access to elements is effectively free. If maximum size constraint is undesirable, then the aforementioned paging will work better. Perhaps the only case where I could imagine linked list being used for stack would be in lock-less stack implementation, but even in those, the maximum number of nodes in stack is typically fixed and pre-allocated (issues however transced the ADT stack by far and complications are too numerous to list). But for everything else, I find linked lists to be simply sub-optimal for stack, with possible exception of certain memory configurations (the overhead however is still hard to justify compared to occasional resize).

Antheus, respectfully I disagree with your reply. The original post states c++ and a linked list are what godsenddeath is thinking about using for the implementation.

For my own understanding could you please expand on the following:

"middle efficiently"
"calculated from algorithm"
"lock-less stack implementation"

Or at the very least could you please provide resources where we can find more information about those terms. From your response it appears that you are talking about implementation of stacks where space overheads are not acceptable. Or are you talking about an implementation of the stack that takes threads into consideration?

Thanks in advance.

[Edited by - arroyjose on August 25, 2008 11:45:43 PM]

Quote:

Original post by arroyjose "middle efficiently"

Inserting an item into the middle of a linked list is very simple: all you need to do is update the next/prev pointers of the preceding/following items in the list. In contrast, inserting an item into the middle of an array is quite expensive, as all the items after the new one have to be 'shunted' forward to make room. The point is that the linked list's ease of middle-insertion is irrelevant because you never do that with a stack anyway.

Quote:

"calculated from algorithm"

It's possible to use the properties of an algorithm and the properties of your dataset to calculate at least an upper bound on the number of items that will be in the stack at any given time. This allows you to perform a single allocation up-front for the entire stack, rather than waiting to allocate memory for each individual item as and when you add it. In performance terms, allocating a single contiguous block one is far preferable to allocating a number of small blocks, partly due to things like cache coherency and partly due to the overhead of allocations.

Quote:

"lock-less stack implementation"

A lockless data structure is one that can be used from multiple threads without any of those threads ever 'blocking' on the structure. They're important when writing high-performance multithreaded systems.

An array-like structure (deque, vector and so forth) ought to be be the default container for a stack. However as mentioned earlier linked-lists have certain properties which can be highly useful, so occasionally they're a better choice.
For instance items can be moved directly onto a linked stack without having to reconstruct (that is copy) the object. A free list would be the classic example of this.
Objects can also be inserted into multiple linked-lists simultaneously, so if you've got a main array which should to be fast to traverse then you could still track a subset of these objects on a separate (doubly-)linked stack.
There are plenty of other reasons why you might favor one or the other, the point being that the ideal choice of underlying datastructure for any particular application depends a great deal the on specific circumstances.

Quote:

Original post by arroyjose Or at the very least could you please provide resources where we can find more information about those terms. From your response it appears that you are talking about implementation of stacks where space overheads are not acceptable. Or are you talking about an implementation of the stack that takes threads into consideration?

For a beginner question, I strayed too far.

Stack is an ADT, and is defined in language and platform agnostic manner.

While it's tempting to create feature rich implementation, it's important to understand that stack is fully defined with above operations, and anything else is redundant, and even invalid. It represents a basic building block for algorithms in that form.


Space efficiency (C++).
D - unaligned, unpadded size of data type stored in stack
O - overhead of each element
H - hidden cost (allocators, new/delete, malloc/free, VM)
n - number of elements in stack

Array implementation:
Space cost: H + O + n*D.
On typical 32-bit machine, with stack storing characters, using standard C++ settings, the number will be approximately n*1. H and O will be either 0 (stack allocation) or perhaps 2*sizeof(void) ~ 64 bytes.

Linked list implementation:
Space cost: n * (H + O + D)
Since each node needs to store pointer to next element, and each element is allocated from the heap, O is pointer to next element, H is cost of alignment/padding within each node.

Again for chars, D = 1, O = sizeof(void*) + sizeof(int)-1, H = ?. Typically, this will be n * 8, since members within each node will be aligned/padded, and since pointer to next element needs to be stored with each node.

Expression evaluation is one textbook case of application of stacks.

Considering that an expression will have some fixed size (16k characters - 204 lines of 80-character wide display), it's reasonable to assume that using array is most efficient storage. Representation using linked lists would cost 130kb.

But, since 640kb is enough for everyone, why worry? The question asked was, what is the most efficient representation of data in stack? The above answers it, overhead factor of 8 is not uncommon if using linked lists. That is clearly not efficient.


At same time, hard-coding limits is often considered bad practice. Using compact array representation, we simply chain several stacks like linked list would. We gain 1*sizeof(void*) overhead per such page, which in case of 16kb pages is 0.02% overhead.

Studies of optimal page sizes can now be made.

Contrary to intuition, pre-allocated free lists are not necessarily a good solution. Rationale: Stack has perfectly predictable allocation patters. push and pop always insert at very predictable location. As such, keeping a list of nodes somewhere (the number of nodes is obviously fixed) does gain anything, since those nodes could be used as array storage of stack directly.

Quote:

"calculated from algorithm"

Canonical definition of quicksort uses recursion (divide and conquer class of algorithms). While all text-books warn that it has worst-case performance of O(n^2), it can be shown that recursion depth will be log(n). Assuming that we can have an indexable array (32-bits on 32-bit machine), it can be deduced that stack version of QS will require depth of 32.

Recursive, back-tracking and divide and conquer can often benefit from conversion to stack storage instead of recursion. Similarily, estimates as above can be made to show that surprisingly small stacks are adequate.

Cost of performing 1 time 32-element allocation can be considered to be 0 compared to 1 heap allocation/de-allocation per recursion (of which there can be millions) in case of QS.

Quote:

"lock-less stack implementation"

Lock-less algorithms deliberately trash shared memory for potential performance benefits. This class of algorithms requires support from OS/hardware in form of atomic swap and compare.

These operations have incredibly strict requirements, and trying to implement array storage for stack proves difficult or impossible. In this case, the "excessive" cost of allocation per value, as well as increased cost may be a valid trade-off considering that now multiple cores can operate on same data. Increasing cost of each operation by 10-100% may be acceptable if 8 cores can now operate on this same data, resulting in 4-8 times performance gain.

For everything else, as well as hundreds of studies and elaborations from 1950's, and authors the likes of Knuth et al, this is all part of CS fundamentals, and those sources will definitely explain these topics much more accurately and considerably more in depth.

Thank you Antheus for taking the time to explain the topics.

When I learned about data structures we covered stacks and some of their applications, but I can't recall ever covering what are the advantages and disadvantages of different implementations in this detail.

A stack using an array

datatype stack[MAX];
int index = 0;

Push:
ASSERT(index < MAX-1);
stack[index++] = temp;

Pop:
ASSERT(index > 0);
temp = stack[--index];

Quote:

Original post by LessBread Push: ASSERT(index < MAX-1); stack[index++] = temp;

I think is should be:

ASSERT(index < MAX);

Quote:

Original post by Gage64 Quote: Original post by LessBread Push: ASSERT(index < MAX-1); stack[index++] = temp; I think is should be: ASSERT(index < MAX);

My notes on that snippet are sparse, so I don't recall what I was thinking exactly when I saved that pseudo code. Perhaps some earlier version prefixed the index incrementation:

ASSERT(index < MAX-1);stack[++index] = temp;

and I didn't correct the bounds check after changing it. The purpose of the pseudo code was to briefly describe the operations of a stack using an array, in particular how push and pop affect the index. That pseudo code wasn't meant to be used as is.

Another possibility is that I maintained that bounds check to keep the stack operations similar to those for a queue, a similar description of which follows the stack description in my notes. Here is that pseudo code:

A queue using an arraydatatype queue[MAX];int head = 0; int tail = 0;Put:ASSERT(tail < MAX-1);queue[tail++] = temp;Get:ASSERT(head < MAX-1);temp = queue[head++];

This pseudo code wasn't meant to be used as is either.

Quote:

Original post by LessBread My notes on that snippet are sparse, so I don't recall what I was thinking exactly when I saved that pseudo code. Perhaps some earlier version prefixed the index incrementation:

I think this is because 'index' is not a good name for that variable. It is not clear what the variable represents by just looking at it's name.

For example, if it's the index of the next slot to be occupied, it should be called 'next' or something similar. Then it's obvious that it should be post-incremented on insertions.

It's named index because it represents an index into the array. The name next suggests a chain of some kind rather than a stack. As an alternative to the name index, we could use a pointer, name it esp and then increment, decrement and dereference as needed...

Quote:

Original post by LessBread It's named index because it represents an index into the array.

... which brings exactly zero semantic information when compared to the usage. Not only is stack[index] redundant, but it would let me write index = rand() % MAX while still making sense (I mean, that's still an index, isn't it).

size, nextIndex or firstFreeIndex are more appropriate names here.

Quote:

Original post by ToohrVyk Quote: Original post by LessBread It's named index because it represents an index into the array. ... which brings exactly zero semantic information when compared to the usage. Not only is stack[index] redundant, but it would let me write index = rand() % MAX while still making sense (I mean, that's still an index, isn't it). size, nextIndex or firstFreeIndex are more appropriate names here.

Yes index = rand() % MAX is still an index but that manipulation does not describe an operation on a stack, so no it wouldn't make sense at all. The semantics of nextIndex and firstFreeIndex are biased towards push. size is better but it's vague because it omits the units. Size in terms of what? Index is the index into the array, post-increment the index to push onto the array, pre-decrement the index to pop from the array. Why complicate simple matters?