stack

manipulate stack objects as dynamic arrays
1.1K Downloads
Updated 28 Aug 2009

View License

The stack object implemented here is a partial solution to the problem of dynamic arrays.

It is well known that appending elements to matlab arrays is inefficient (appending an element to a nx1 vector requires at least n assignments), e.g.

tic;v=[];for i=1:1e5,v=[v,i];end;toc; % O(n^2), approx 30 sec
tic;v=zeros(1e5,1); for i=1:numel(v),v(i)=i;end;toc; % O(n), approx 0.004 sec

In some applications we don't know the final length of the array. One solution is the use of stack objects.

A stack is a linked list containing the top item and a pointer to the top of the stack below. Here it is implemented as a nested cell array: s = {} (empty stack) or s = {x,s1} where s1 is a stack.

tic;
s={};
for i=1:1e5
s=push(i,s);
end;
w=stack2mat(s,1e5);
isequal(v,w) % returns 1
toc; % approx 3 sec

The code for push and pop is rather trivial. The functions stack2mat and stack2cell are useful if you need to access elements of the stack other than the last.

NOTE: The reason this is called a "partial" solution to the problem of dynamic arrays:
1. the memory overhead seems to be 120 bytes per stack element (doubles use 8 bytes)
2. large stacks (e.g 1e6 elements) can cause matlab to terminate unexpectedly, which seems to be from a bug in the way matlab handles large nested cell arrays (only tested in R2009a).

Cite As

Ben Petschel (2024). stack (https://www.mathworks.com/matlabcentral/fileexchange/25162-stack), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2009a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.0.0.0