The Stack ADT
Stacks of Coins and Plates
Stacks of Rocks and Books
TOP OF THE STACK TOP OF THE STACK
Add,
remove
rock and
book from
the top, or
else…
Stack at logical level
• A stack is an ADT in
which elements add
added and removed
from only one end
(i.e.,at the top of the
stack).
• A stack is a LIFO “last
in, first out”
structure.
Stack at Logical Level
• What operations would be
appropriate for a stack?
Stack Operations
Transformer
s change state
• Push
• Pop
Observers
• Top
• IsEmpty observe state
• IsFull
Stack at Application Level
• For what types of problems would be
stack be useful for?
• LIFO: good for reversing data
• If we push a, b, c, d into a stack, and
then pop all elements out, we get
d, c, b, a
• In OS/language: function call stack
• Finding Palindromes
• Expression evaluation and Syntax
Parsing
Function call stack
• For what types of
problems would be stack
be useful for?
• LIFO: good for reversing
data
• If we push a, b, c, d into
a stack, and then pop
all elements out, we get
d, c, b, a
• In OS/language: function
call stack
• Finding Palindromes
• Expression evaluation
and Syntax Parsing
Use stack to reverse
• Sometimes you need to output in
reverse orders Convert decimal to binary:
DisplayInBinary (int num) while (num>0)
digit = num
% 2 print
digit
num = num /
2
• The binary
representation
is printed
backward
Use stack to backtrack
• In maze-walking algorithm, we can use stack
to store all nodes that we led us to current
node, so that we can backtrack when needed.
•Goal: find a path via
white blocks from (0,0)
to (5,5)
•Need to explore: try
diff. next step
•and backtrack (when
reach dead-end): i.e.,
reverse back to previous
Stack Implementation
• array-based implementation: static or
dynamic array
• linked-structure implementation
class StackType
{
public:
StackType( );
bool IsFull () const;
bool IsEmpty() const;
2
void Push( ItemType item );
unuse
void Pop();
d
slots
ItemType Top();
private: ‘c
’
int top; Stac
items[MAX_ITEMS]; ‘b k
ItemType
}; ’ item
‘a s
1
3 ’
Class Interface
(Memory reversed to better illustrate
Diagram
concept)
StackType class
Private data:
StackTyp
top
e
[MAX_ITEMS-1]
IsEmpty
IsFull .
.
.
Push [
2
Pop ]
items [0]
[
1
Top ]
Initialize stack
How to initialize data member top?
0 or -1
Depends on what top stores:
* initialized to 0: If it’s the next open slot
*initialized to -1: if it’s the index of stack top
element
Need to be consistent in all member functions, Top(),
Push(), Pop(), isfull, isEmpty()…
Below we use second option:
StackType::StackType( )
{
top = -1; //index of top element in stack
}
// pre: the stack has been initialized
// post: return true if the stack is empty, false ow
bool StackType::IsEmpty() const
{
return(top == -1);
}
//pre:
//post:
bool StackType::IsFull() const
{
return (top = = MAX_ITEMS-1);
}
void StackType::Push(ItemType newItem)
{
if( IsFull() )
throw FullStack():
top++;
items[top] =
newItem;
}
void
StackType::Pop()
{
if( IsEmpty() )
throw EmptyStack();
top--;
}
ItemType
StackType::Top()
{
if (IsEmpty())
throw EmptyStack();
return items[top];
Tracing Client Code
letter
‘V’ char letter = ‘V’;
StackType charStack;
[Link](letter);
Private data: [Link](‘C’);
top [Link](‘S’);
if ( )
[MAX_ITEMS-1] [Link]( );
. [Link](‘K’);
. while (!
[Link]( ))
[2]
{ letter = [Link]();
[Link](0)}
[1]
items [ 0 ]
Stack Implementation: linked structure
• One advantage of an ADT is that the
implementation can be changed without the
program using it knowing about it.
• in-object array implementation: has a fixed
max. size
• dynamically allocated array (as in lab2?):
can be grown when needed, but lots of
copy!
• Linked structure: dynamically allocate the
space for each element as it is pushed onto
stack.
ItemType is char
class StackType
StackTyp
e
Top Private data:
IsEmpty
topPtr
IsFull ‘C’ ‘V’
Push
Pop
~StackType
Deleting top element from the stack
item
NodeType*
item = topPtr->info;
tempPtr;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
topPtr ‘B’ ‘X’ ‘C’ ‘L’
tempPtr
Deleting top element from the stack
item ‘B’
NodeType* tempPtr;
item = topPtr->info;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
topPtr ‘B’ ‘X’ ‘C’ ‘L’
tempPtr
Deleting item from the stack
item ‘B’
NodeType*
tempPtr; item =
topPtr->info;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
topPtr ‘B’ ‘X’ ‘C’ ‘L’
tempPtr
Deleting item from the stack
item ‘B’
NodeType* tempPtr;
item = topPtr->info;
tempPtr = topPtr;
topPtr = topPtr->next;
delete tempPtr;
topPtr ‘B’ ‘X’ ‘C’ ‘L’
tempPtr
Deleting item from the stack
item ‘B’
NodeType<ItemType>*
tempPtr; item = topPtr-
>info;
tempPtr = topPtr;
topPtr = topPtr->next;
delete
tempPtr;
topPtr ‘X’ ‘C’ ‘L’
tempPtr
Array vs Linked Structure
• Drawback of array-based
implementation:
• at any point of time, array is either
filled or not
• memory is either not enough,
• or wasted
• Linked Structure: allocate on demand
• Drawback: need to store lots of
addresses (in pointer field of node)
• if ItemType is small compared to
pointer, then it’s not memory
efficient
Efficiency comparison
C++ Standard Template Library
• a set of C++ class templates that
provides common programming
data structures and functions
• lists, stacks, queues, hash table,
many more…
• all data structures/container are
implemented as class template, which
can be parameterized:
• vector<int>, vector<double> …
• stack<int>, stack<char>
• the type in <> is type parameter,
specifying the type of items that the
stack stores…
Sample code using STL stack
Sample code using STL stack
More info on
stack
3
5