Chapter: Object Oriented Programming and Data Structure : Linear Data Structures

Array Based Implementation

First, if we want to store letters, we can use type char. Next, since a stack usually holds a bunch of items with the same type (e.g., char), we can use an array to hold the contents of the stack.

Array Based Implementation:

First, if we want to store letters, we can use type char. Next, since a stack usually holds a bunch of items with the same type (e.g., char), we can use an array to hold the contents of the stack. Now, consider how we'll use this array of characters, call it contents, to hold the contents of the stack. At some point we'll have to decide how big this array is; keep in mind that a normal array has a fixed size.

Let's choose the array to be of size 4 for now. So, an array getting A, then B, will look like:

-----------------

| A | B | | |

-----------------

0 1 2 3 contents

So, a sequence of pops produce the following effects:

1. letter = Pop(stack)

2. stack (made up of 'contents' and 'top')

3. ----------------- ----- -----

4. | A | B | | | | 1 | | C |

5. ----------------- ----- -----

6. 0 1 2 3 top letter

7. contents

8. letter = Pop(stack)

9. stack (made up of 'contents' and 'top')

10. ----------------- ----- -----

11. | A | | | | | 0 | | B |

12. ----------------- ----- -----

13. 0 1 2 3 top letter

14. contents

15. letter = Pop(stack)

16. stack (made up of 'contents' and 'top')

17. ----------------- ----- -----

18. | | | | | | -1| | A |

19. ----------------- ----- -----

20. 0 1 2 3 top letter

What happens if we apply the following set of operations?

1. Push(stack, 'D')

2. Push(stack, 'E')

3. Push(stack, 'F')

4. Push(stack, 'G')

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Linear Data Structures : Array Based Implementation |