One disadvantage of using an array to implement a stack is the wasted space---most of the time most of the array is unused. A more elegant and economical implementation of a stack uses a linked list, which is a data structure that links together individual data objects as if they were ``links'' in a ``chain'' of data.
Here is a sketch of a linked-list-based ``stack'' that holds 1, then 5, and then 20 at the bottom:
Say that we pop an object from the stack; the picture changes to this:
Here is a sketch of a linked-list-based ``stack'' that holds 1, then 5, and then 20 at the bottom:
---
top ---> | 1 |
|---| ---
| o-|---> | 5 |
--- |---| ----
| o-|---> | 20 |
--- |----|
|null|
----
The list consists of three ``cells,'' each of which holds a data object and a ``link'' to another cell. A variable, top, holds the address of the first cell in the list. An empty stack looks like this:top ---> null
(That is, variable top holds value, null.) Each time an object is pushed, a cell is constructed, the object is inserted into the cell, and the cell is linked to the front of the chain of cells. For example, pushing 20 onto the empty stack gives us ----
top ---> | 20 |
|--- |
|null|
----
After 5 and then 1 are pushed, we obtain the picture first seen.Say that we pop an object from the stack; the picture changes to this:
---
top ---> | 5 |
|---| ----
| o-|---> | 20 |
--- |----|
|null|
----
Download Program With OUTPUT
EmoticonEmoticon