Entry

Datastructure: Stack: What is a stack?

Apr 4th, 2005 00:08
Knud van Eeden,

----------------------------------------------------------------------
--- Knud van Eeden --- 22 December 2004 - 08:40 pm -------------------

Datastructure: Stack: What is a stack?

---

A stack is a structure in which you can store data.

It is one of the simplest (linear) structures for storing available.

You put all data on top of each other, similar to a tray
of dining plates in a restaurant.

To add data you store it on the same side of this structure.

To remove data you remove it from the same side of this structure.

(
The common thing here is thus you only touch the 'sides' of the
structure, instead of also adding, removing or getting data from the
'interior' of the structure.

So in general any 'twosided' structure in which you can store will do.

A stack is still simpler, there any 'one sided' structure will do.

 -If you add and remove only from 'one side' it is a stack.

 -If you add to 'one side' and remove from the 'other side' it is a
  queue.

 -If you add and remove from 'both sides' it is a dequeue.
)

---

Using a string as a stack:

One of the most simple structures to use as a stack is a string.

To store data you put it on the left side of the string.

To remove data you remove it also from the left side of the string.

(or similarly store on the right and remove on the right of the string)

---

original:

  "a b c d e f g"

---

adding:

  "z a b c d e f g"

---

removing:

  "a b c d e f g"

---

Using a file as a stack:

Another possibility to store the information is using a file.

To add new information (e.g. lines) you put it in the top of the
file.

To remove information (e.g. lines) you remove it also from the top
of the file.

(or similarly store on the bottom and remove from the bottom of the
file)

  a

  b

  c

  d

  e

  f

  g

---

Using a computer memory as a stack:

Other possibilities to store the information is computer memory.

To add new information (e.g. a variable) you put it in the top of the
memory range.

To remove information (e.g. a variable) you remove it also from the top
of the memory range.

(or similarly store on the bottom and remove from the bottom of the
memory range)


  [  a  ]

  [  b  ]

  [  c  ]

  [  d  ]

  [  e  ]

  [  f  ]

  [  g  ]

---

Using an array as a stack:

Other possibilities to store the information is using an array.

To add new information (e.g. a variable) you put it in the top of the
array.

To remove information (e.g. a variable) you remove it also from the top
of the array.

(or similarly store on the bottom and remove from the bottom of the
array)

  [  a  ]

  [  b  ]

  [  c  ]

  [  d  ]

  [  e  ]

  [  f  ]

  [  g  ]

---
---

Storing data you call 'push' here.

Removing data you call 'pop' here.

---

This method of storing and removing data means that what you put
last in (e.g. on top of the file) will also be removed the first
(e.g. from the top of the file). Or in other words it is
'L'ast 'I'n 'F'irst 'O'ut, or thus LIFO.

(or similarly 'F'irst 'I'n 'L'ast 'O'ut, or thus abbreviated FILO).

---
---

Internet: see also:

---

Datastructure: Link: Overview: Can you give an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/32054/fid/1264

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