© Andrew H. Jones & Cheng-Kok Koh 1
ECE36800 Data structures
Stacks
Chapter 4 (pp. 127-150)
© Andrew H. Jones & Cheng-Kok Koh 2
Overview
● Stack definition
● Primitive operators
● Stack implementations
– Linked list
– Array of fixed size
– Array of variable size
● Reference pages: pp. 127-250
© Andrew H. Jones & Cheng-Kok Koh 3
Stacks
● A stack is an ordered collection of items into which new items may be
inserted and from which items may be deleted only at one end, called the
top of the stack
● Can also be called LIFO (Last In First Out)
● A stack of papers, for example
– The stack is either empty or not empty
– Only the top item is visible
– Items are ordered (from bottom to top)
– Items may be added or removed only at top
● Other examples:
– A call stack of frames for function calls
– A spring-loaded plate dispenser for buffet
© Andrew H. Jones & Cheng-Kok Koh 4
Primitive operators
● Push(S, i)
– Add item i on the top of stack S
– Must make sure it does not cause overflow
● Pop(S)
– Get the top item of stack S, remove it from S and return it, e.g., i =
Pop(S)
– Must make sure that stack was not empty
● Stack_top(S)
– Return the top item of stack S with no change to S, e.g., i = Stack_top(S)
– Must make sure that stack was not empty
● Empty(S) (or Is_empty(S))
– Return true if stack S is empty; false otherwise
© Andrew H. Jones & Cheng-Kok Koh 5
Linked list implementation
● Seek O(1) time complexity for all primitive operations
● Empty list == Empty stack
● Head of list == Stack top
– Meaningful only if list is not empty
● Insert at head = Push
– To check for overflow, verify that the address returned by
malloc is not NULL
● Remove at head = Pop
– Meaningful only if list is not empty
© Andrew H. Jones & Cheng-Kok Koh 6
Linked list example
3 6 1
S (also stack top)
NULL
3 = Pop(S)
6 1
S (also stack top)
NULL
4 6 1
S (also stack top)
NULL
Push(S, 4)
© Andrew H. Jones & Cheng-Kok Koh 7
Array implementation
● Use a struct to store three fields:
– Address of the array to store items
– Total size of the array (the maximum number of items that can be on
the stack)
– Index of the stack top
● Assume that stack top index initialized to -1 for an empty stack
– Empty stack == Stack top index -1
– Stack top == item in array at location indexed by stack top (if not -1)
– Push == Increment stack top index, store item in array at location
indexed by stack top (if the stack top index < array size)
– Pop == Store in a temporary variable the item in the array at location
indexed by the stack top (if not -1), decrement stack top index, return
value stored in the temporary variable
© Andrew H. Jones & Cheng-Kok Koh 8
Array example (assume an array
size of 5)
1
6
3
?
?
Stack top = 2
1
6
3
?
?
Stack top = 1
1
6
4
?
?
Stack top = 2
3 = Pop(S) Push(S, 4)
3 is not over-written in the
array even though it is no
longer a valid entry in
Stack S
© Andrew H. Jones & Cheng-Kok Koh 9
C program for implementing a stack
with an array of static size
● Slides from page 9 (this page) to page 23 not
covered in class
● The size of the array for storing items on a
stack is fixed in the program (called
STACK_INT_SIZE), and not stored in the struct
for stack
● Array is statically allocated within the struct
© Andrew H. Jones & Cheng-Kok Koh 10
/*-----------------------------------------
* program: stack_int.h
* Implement a stack for integers
* Programmer: ece36800
*---------------------------------------*/
#ifndef __stack_int__
#define __stack_int__
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#define STACK_INT_SIZE 100
© Andrew H. Jones & Cheng-Kok Koh 11
// declare stack structure
struct Stack_Int
{
int Top;
int Items[STACK_INT_SIZE];
};
typedef struct Stack_Int Stack_Int_t;
// function prototypes
void Stack_Int_Init(Stack_Int_t *S_Ptr);
int Stack_Int_Empty(Stack_Int_t *S_Ptr);
int Stack_Int_Stacktop(Stack_Int_t *S_Ptr);
int Stack_Int_Pop(Stack_Int_t *S_Ptr);
int Stack_Int_Push(Stack_Int_t *S_Ptr,
int Item);
#endif // __stack_int__
stack_int.h cont..
© Andrew H. Jones & Cheng-Kok Koh 12
/*-----------------------------------------
* program: stack_int.c
* Programmer: ece36800
* Description: define stack functions
*-----------------------------------------*/
#include
#include "stack_int.h"
void Stack_Int_Init(Stack_Int_t *S_Ptr)
{
/* initialize the stack of integers */
S_Ptr->Top = -1;
} /* Stack_Int_Init() */
int Stack_Int_Empty(Stack_Int_t *S_Ptr)
{
/* is stack empty?? (TRUE/FALSE) */
return (S_Ptr->Top < 0);
} /* Stack_Int_Empty() */
© Andrew H. Jones & Cheng-Kok Koh 13
stack_int.c cont..
int Stack_Int_Push (
Stack_Int_t *S_Ptr,
int Item)
{
/* place Item on top of stack */
if (S_Ptr->Top >= STACK_INT_SIZE - 1)
{
return (FALSE);
}
S_Ptr->Items[++(S_Ptr->Top)] = Item;
return (TRUE);
} /* Stack_Int_Push */
© Andrew H. Jones & Cheng-Kok Koh 14
int Stack_Int_Stacktop(Stack_Int_t *S_Ptr)
{
/* view and return item at top of stack */
return (S_Ptr->Items[S_Ptr->Top]);
} /* Stack_Int_Stacktop() */
int Stack_Int_Pop(Stack_Int_t *S_Ptr)
{
/* pull top item off stack */
int Results = 0;
Results = S_Ptr->Items[S_Ptr->Top];
(S_Ptr->Top)--;
return (Results);
} /* Stack_Int_Pop() */
stack_int.c cont..
© Andrew H. Jones & Cheng-Kok Koh 15
/*-----------------------------------------
* program: insert_at_bottom.c
* Programmer: ece36800
* Description:
* develop function that would insert a new item at the bottom
* of the stack using only the public stack functions
*-----------------------------------------*/
#include
#include "stack_int.h"
void Insert_At_Bottom (Stack_Int_t *S_Ptr, int Item)
{
Stack_Int_t Aux_Stack; // for storing the contents of stack in reverse
int Temp = 0;
Stack_Int_Init(&Aux_Stack);
while (!Stack_Int_Empty(S_Ptr)) // store contents in reverse
{
Temp = Stack_Int_Pop(S_Ptr);
Stack_Int_Push(&Aux_Stack, Temp);
}
Stack_Int_Push(S_Ptr, Item); // new item at bottom
while (!Stack_Int_Empty(&Aux_Stack)) // put back the rest
{
Temp = Stack_Int_Pop(&Aux_Stack);
Stack_Int_Push(S_Ptr, Temp);
}
} /* Insert_At_Bottom() */
© Andrew H. Jones & Cheng-Kok Koh 16
int main(void)
{
Stack_Int_t Stack;
Stack_Int_Init(&Stack);
Stack_Int_Push(&Stack, 5);
Stack_Int_Push(&Stack, 4);
Stack_Int_Push(&Stack, 3);
Insert_At_Bottom(&Stack, 6);
printf("Top:");
while (!Stack_Int_Empty(&Stack))
{
printf("\t%d\n", Stack_Int_Pop(&Stack));
}
return 0;
} /* main() */
insert_at_bottom.c cont..
© Andrew H. Jones & Cheng-Kok Koh 17
Complexity Analysis
● Push: O(1)
● Pop: O(1)
● Stack Top: O(1)
● Empty: O(1)
● Insert at Bottom: O(n) time complexity, O(n)
space complexity (additional memory needed to
perform the computation)
© Andrew H. Jones & Cheng-Kok Koh 18
What is wrong?
● Pop still executes on a empty stack!
● Implementation needs to consider memory
constraints
– When Push executes on a full stack, what
happens?
● How to solve these problems?
© Andrew H. Jones & Cheng-Kok Koh 19
Solutions
● A not-so-elegant solution by assert(expression)
– Abort if expression is false
● Should handle failure gracefully
– Check if stack empty before proceeding
– Use a global error variable
● Set variable to error code and check it
● Create error recovery/notification functions
© Andrew H. Jones & Cheng-Kok Koh 20
int Stack_Int_Stacktop(Stack_Int_t *S_Ptr)
{
/* view and return item at top of stack */
int Result = 0;
/* precondition: what must be satisfied to execute
the operation */
assert(!Stack_Int_Empty(S_Ptr));
Result = S_Ptr->Items[S_Ptr->Top];
return Result;
} /* Stack_Int_Stacktop() */
stack_int.c changes for preconditions
Have to include assert.h
In plain English: the expression in assert() means
“Stack not empty”. Therefore, abort if stack not empty is false
or abort if stack is empty
© Andrew H. Jones & Cheng-Kok Koh 21
Other ways to enforce precondition
● How about:
● Or define the macro (in .h file)
and use (in .c files):
assert( (S_Ptr != NULL)
&& (!Stack_Int_Empty(S_Ptr)));
#define Stack_Int_OK(SP) ((NULL != (SP)) \
&& ((SP)->Top >= -1) \
&& ((SP)->Top < STACK_INT_SIZE))
assert( (Stack_Int_OK(S_Ptr))
&& (!Stack_Int_Empty(S_Ptr)));
© Andrew H. Jones & Cheng-Kok Koh 22
stack_int.h additions for error variable..
// error codes
#define STACK_INT_NO_ERROR 0
#define STACK_INT_OVERFLOW -1
#define STACK_INT_UNDERFLOW -2
// global error variable
extern int Stack_Int_Errno;
// error handling functions
int Stack_Int_Error(void);
void Stack_Int_Clear_Error(void);
void Stack_Int_Print_Error(void);
© Andrew H. Jones & Cheng-Kok Koh 23
stack_int.c additions for error variable..
int Stack_Int_Stacktop(Stack_Int_t *S_Ptr)
{
/* view and return item at top of stack */
if (Stack_Int_Empty(S_Ptr))
{
Stack_Int_Errno = STACK_INT_UNDERFLOW;
return (0);
}
return (S_Ptr->Items[S_Ptr->Top]);
} /* Stack_Int_Stacktop() */
Must test Stack_Int_Errno at the
completion of each stack function call
© Andrew H. Jones & Cheng-Kok Koh 24
Stack implemented with an array of
variable size
● Static memory allocation usually inappropriate for dynamically
growing data structures
– Use malloc() or calloc() to allocate memory
– Use free() to deallocate memory
– Use realloc() to grow/shrink allocated memory
● If realloc succeeds, it returns the address of the new (re-sized) array at a possibly
new location and all contents of original array up to min(old size, new size) are correct
– If the re-sized array is at a new location, the old array is freed by realloc
– Otherwise, the array is simply re-sized in-situ
● If realloc fails, it returns NULL and the old array remains intact
● Always store the address returned by realloc at a temporary variable and check
whether the temporary variable stores a NULL address
● If the temporary variable stores a non-NULL address, re-sizing is successful and we
can safely replace the old address with the address in the temporary variable;
otherwise, we handle the failure to re-size gracefully
● Always free memory after using the stack
© Andrew H. Jones & Cheng-Kok Koh 25
How to Grow Stack
● Grow the size of the array by a multiplicative factor
● new size = (1+r) * original size, r > 0
● For example, r = 1 implies that we double the size
of the array
● Assume initial stack size of 1, and operation cost
of pushing n items (assume it costs 1 operation to
copy or push an item): 1 + 2 + 3 + 1 + 5 + 1 + 1 +
1 + 9 + 1 + 1 + 1 + …
– Grow stack O(log n) times
– Total complexity: Copy items O(n), push items O(n)
– On the average, O(1) for a stack push
© Andrew H. Jones & Cheng-Kok Koh 26
1 1
2
Push(S,1) Push(S,2) Push(S,3) Push(S,4) Push(S,5) Push(S,6) Push(S,7) Push(S,8)
Push 1 1 1 1 1 1 1 1
Copy 0 1 2 0 4 0 0 0
Total 1 2 3 1 5 1 1 1
1
2
3
?
1
2
3
4
1
2
3
5
?
?
?
4
1
2
3
5
6
?
?
4
1
2
3
5
6
7
?
4
1
2
3
5
6
7
8
4
Altogether, 1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 = 15 operations
for pushing 8 items onto the stack, i.e., ~ 2 operations per push
© Andrew H. Jones & Cheng-Kok Koh 27
How (NOT) to Grow Stack
● Increase its size by a fixed amount, F > 0
● new size = old size + F
● Assume initial stack size of 1, and F = 1
● Operation cost of pushing n items (assume it
costs 1 operation to copy or push an item): 1 + 2
+ 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + …
● Total complexity: Copy items O(n2), push items
O(n)
● Average cost of stack push is O(n)
© Andrew H. Jones & Cheng-Kok Koh 28
1 1
2
Push(S,1) Push(S,2) Push(S,3) Push(S,4) Push(S,5) Push(S,6) Push(S,7) Push(S,8)
Push 1 1 1 1 1 1 1 1
Copy 0 1 2 3 4 5 6 7
Total 1 2 3 4 5 6 7 8
1
2
3
1
2
3
4
1
2
3
5
4
1
2
3
5
6
4
1
2
3
5
6
7
4
1
2
3
5
6
7
8
4
Altogether, 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36 operations
for pushing 8 items onto the stack, i.e., ~ 4 (or 8/2) operations per push
© Andrew H. Jones & Cheng-Kok Koh 29
When to Shrink Stack (If you have to)
● Load factor a = (# items/size of stack)
● After some pop operations, a may be low
● Assume we grow and shrink stack by the same factor
– Shrink size by new size = old size / (1 + r)
● Shrink size of stack by a factor of (1+r) when a = 1/
(1+r)2
● What happen when you shrink the stack by a factor of
(1+r) when a = 1/(1+r)?
© Andrew H. Jones & Cheng-Kok Koh 30
C program for implementation a
stack with an array of variable size
● Slides from page 30 (this page) to page 42 not
covered in class
● Array is dynamically allocated within the struct
Stack_ Dyn
● Initial size is 1000, and r is 0.5, multiplicative
factor is (1+0.5) = 1.5
© Andrew H. Jones & Cheng-Kok Koh 31
/*-----------------------------------------
* program: stack_dyn.h
* Programmer: ece36800
* Description:
* implement a dynamic stack of ints
*-----------------------------------------*/
#ifndef __stack_dyn__
#define __stack_dyn__
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#define STACK_INITIAL_SIZE 1000
#define STACK_GROW_FACTOR 1.5
© Andrew H. Jones & Cheng-Kok Koh 32
stack_dyn.h cont..// define stack element type
typedef int Stack_El_t;
// declare stack structure
struct Stack_Dyn
{
int Top;
Stack_El_t *Items;
int Size;
int Minimum_Size;
};
typedef struct Stack_Dyn Stack_Dyn_t;
// function prototypes
int Stack_Dyn_Init(Stack_Dyn_t *S_Ptr, int Initial_Size);
void Stack_Dyn_Deinit(Stack_Dyn_t *S_Ptr);
Stack_Dyn_t *Stack_Dyn_New(int Initial_Size);
void Stack_Dyn_Delete(Stack_Dyn_t *S_Ptr);
int Stack_Dyn_Empty(Stack_Dyn_t *S_Ptr);
Stack_El_t Stack_Dyn_Stacktop(Stack_Dyn_t *S_Ptr);
Stack_El_t Stack_Dyn_Pop(Stack_Dyn_t *S_Ptr);
int Stack_Dyn_Push(Stack_Dyn_t *S_Ptr, Stack_El_t Item);
#endif // __stack_dyn__
© Andrew H. Jones & Cheng-Kok Koh 33
/*-----------------------------------------
* program: stack_dyn.c
* Programmer: ece36800
* Description: Definitions of public function
* Dynamic memory allocation for stack (arrays)
*-----------------------------------------*/
#include
#include
#include
#include "stack_dyn.h"
void Stack_Dyn_Deinit(Stack_Dyn_t *S_Ptr)
{
/* deallocate memory of stack */
free(S_Ptr->Items);
S_Ptr->Items = NULL;
S_Ptr->Size = 0;
S_Ptr->Minimum_Size = 0;
S_Ptr->Top = -1;
} /* Stack_Dyn_Deinit() */
© Andrew H. Jones & Cheng-Kok Koh 34
stack_dyn.c cont..
int Stack_Dyn_Init (
Stack_Dyn_t *S_Ptr,
int Initial_Size)
{
/* initialize the stack of type El_t */
if (Initial_Size <= 0)
Initial_Size = STACK_INITIAL_SIZE;
S_Ptr->Top = -1;
S_Ptr->Size = Initial_Size;
S_Ptr->Minimum_Size = Initial_Size;
S_Ptr->Items = (Stack_El_t *)
malloc(sizeof(Stack_El_t) * Initial_Size);
if (S_Ptr->Items == NULL)
{
S_Ptr->Size = 0;
return FALSE; // out of memory!
}
return TRUE;
} /* Stack_Dyn_Init() */
© Andrew H. Jones & Cheng-Kok Koh 35
stack_dyn.c cont..
Stack_Dyn_t *Stack_Dyn_New (int Initial_Size)
{
/* initialize the stack of type El_t */
Stack_Dyn_t *Result_Ptr = NULL;
Result_Ptr = (Stack_Dyn_t *)
malloc(sizeof(Stack_Dyn_t));
if (Result_Ptr == NULL)
{
return NULL; // out of memory!
}
if (!Stack_Dyn_Init(Result_Ptr, Initial_Size))
{
free (Result_Ptr);
return NULL;
}
return Result_Ptr;
} /* Stack_Dyn_New() */
© Andrew H. Jones & Cheng-Kok Koh 36
stack_dyn.c cont..
void Stack_Dyn_Delete(Stack_Dyn_t *S_Ptr)
{
/* delete stack and the struct from memory */
Stack_Dyn_Deinit(S_Ptr);
free(S_Ptr);
} /* Stack_Dyn_Delete() */
int Stack_Dyn_Empty(Stack_Dyn_t *S_Ptr)
{
/* is stack empty?? (TRUE/FALSE) */
return (S_Ptr->Top < 0);
} /* Stack_Dyn_Empty() */
Stack_El_t Stack_Dyn_Stacktop(Stack_Dyn_t *S_Ptr)
{
/* view and return item at top of stack */
return (S_Ptr->Items[S_Ptr->Top]);
} /* Stack_Dyn_Stacktop() */
© Andrew H. Jones & Cheng-Kok Koh 37
stack_dyn.c cont..
Stack_El_t Stack_Dyn_Pop(Stack_Dyn_t *S_Ptr)
{
/* pull top item off stack (adjust stack) */
Stack_El_t Result = 0;
int New_Size = 0;
Stack_El_t *New_Items = NULL;
Result = S_Ptr->Items[S_Ptr->Top];
S_Ptr->Top--;
if ( (S_Ptr->Size == S_Ptr->Minimum_Size)
|| ((int)((S_Ptr->Top + 1) * STACK_GROW_FACTOR
* STACK_GROW_FACTOR) + 1) >= S_Ptr->Size)
{
return (Result); // no stack adjustment
}
New_Size = (int)((S_Ptr->Top + 1) *
STACK_GROW_FACTOR) + 1;
if (New_Size <= S_Ptr->Top + 1)
{
return (Result); // no stack adjustment
}

© Andrew H. Jones & Cheng-Kok Koh 38
if (New_Size < S_Ptr->Minimum_Size)
{
New_Size = S_Ptr->Minimum_Size;
}
New_Items = (Stack_El_t *)realloc(S_Ptr->Items,
sizeof(Stack_El_t) * New_Size);
if (New_Items == NULL)
{
return Result; // problem with memory
}
S_Ptr->Size = New_Size;
S_Ptr->Items = New_Items;
return Result; // stack adjusted correctly
} /* Stack_Dyn_Pop() */
stack_dyn.c cont..
© Andrew H. Jones & Cheng-Kok Koh 39
stack_dyn.c cont..int Stack_Dyn_Push (
Stack_Dyn_t *S_Ptr,
Stack_El_t Item)
{
/* place Item on top of stack (adjust stack) */
int New_Size = 0;
Stack_El_t *New_Items = NULL;
if (S_Ptr->Top >= S_Ptr->Size - 1)
{
New_Size = (int)(STACK_GROW_FACTOR * S_Ptr->Size)+ 1;
if (New_Size <= S_Ptr->Size)
return FALSE; // overflow

New_Items = (Stack_El_t *)realloc(S_Ptr->Items,
sizeof(Stack_El_t) * New_Size);
if (New_Items == NULL)
return FALSE; // out of memory!

S_Ptr->Size = New_Size;
S_Ptr->Items = New_Items;
}
S_Ptr->Items[++S_Ptr->Top] = Item;
return (TRUE);
} /* Stack_Dyn_Push */
© Andrew H. Jones & Cheng-Kok Koh 40
/*-----------------------------------------
* program: insert_at_bottom_dyn.c
* Programmer: ece36800
* Description:
* develop function that would insert a new item at the
* bottom of the stack using only the public stack functions
*---------------------------------------*/
#include
#include "stack_dyn.h"
void Insert_At_Bottom(Stack_Dyn_t *S_Ptr, Stack_El_t Item)
{
/* insert Item at bottom of stack */
Stack_Dyn_t *Aux_Stack; /* only pointer! */
int Temp = 0;
Aux_Stack = Stack_Dyn_New(0);
while (!Stack_Dyn_Empty(S_Ptr))
{
Temp = Stack_Dyn_Pop(S_Ptr);
Stack_Dyn_Push(Aux_Stack, Temp);
}
Stack_Dyn_Push(S_Ptr, Item);
while (!Stack_Dyn_Empty(Aux_Stack))
{
Temp = Stack_Dyn_Pop(Aux_Stack);
Stack_Dyn_Push(S_Ptr, Temp);
}
Stack_Dyn_Delete(Aux_Stack);
} /* Insert_At_Bottom() */
© Andrew H. Jones & Cheng-Kok Koh 41
insert_at_bottom_dyn.c cont..
int main(void)
{
Stack_Dyn_t Stack; /* memory allocated for struct */
Stack_Dyn_Init(&Stack, 0);
Stack_Dyn_Push(&Stack, 5);
Stack_Dyn_Push(&Stack, 4);
Stack_Dyn_Push(&Stack, 3);
Insert_At_Bottom(&Stack, 6);
printf("Top:");
while (!Stack_Dyn_Empty(&Stack))
{
printf("\t%d\n", Stack_Dyn_Pop(&Stack));
}
Stack_Dyn_Deinit(&Stack);
return 0;
} /* main() */
© Andrew H. Jones & Cheng-Kok Koh 42
Further comments
● Releasing resources is important!
– A call to init() should have a corresponding call to deinit()
[new() « delete() in C++]
● Make sure all unused memory/fields are destroyed
● Used Stack_El_t for stack content type
– Need only modify the typedef and recompile
– How to have multiple stacks of different types?
● Cut and paste in C
● Typecast in C
● Create templates in C++

学霸联盟