Data Structures - Stack, Queue

[Achilles]

Data Structures

Queuepurpose:

A queue is a line. Works on a FIFO (first in first our) basis. Example: A line of people; the first person to get to the line gets attended to first.

Stack purpose:

A stack is exactly what is says it is. Works in a LIFO (last in first out) basis. Example: A stack of CD's; the last CD that you put on is the first one that comes off.

For these you can use _ArrayDisplay() to see them, but note that the item at 0 index is used only by the stack/quere, do not change its value.

Functions (preceded by _Stack_ or Queue_)

• Create
• Empty
• GetSize
• IsEmpty
• Peek - views the next item
• Pop - removes the next item
• Push - adds an item

Download here: DataStructures.zip Previous downloads 27

Stack.zip

Edited April 3, 2009 by Achilles

[zfisherdrums]

I just made a stack class to help with one of my programs, and I realized how helpful it could be.

For those of you who don't know what a stack does, it's basically an array where you can add items on top (PUSH), look at the item on top (PEEK) or take off the item on top (POP). It's useful for anything where you could visualize you're array as a stack. For example, in a media player the first song could be the bottom of the stack, and every song that plays after goes on top, one by one. But, if the user presses back, you just pop your stack once and play that song.

The first item in the array is the index at which new items are added. Do NOT mess with that number and expect the stack to work fine. You can use _ArrayDisplay() with a stack, because all it is is an array.

Download DataStructures.au3 with example here: Stack.zip

Nice implementation! I think I may be able to use this.

Just a couple questions:

1 - Do you think there could be a performance improvement if _Stack_Empty simply Dim'ed the array instead of iterating all indexes and re-setting them?

2 - I could see there being a problem if users push values of -1 or empty strings onto the stack. How would consumers of this implementation be guaranteed that they are always retrieving valid data?

Thanks again for the library/examples!

Zach Fisher...

Edited March 1, 2009 by zfisherdrums

[Achilles]

Nice implementation! I think I may be able to use this.

Just a couple questions:

1 - Do you think there could be a performance improvement if _Stack_Empty simply Dim'ed the array instead of iterating all indexes and re-setting them?

2 - I could see there being a problem if users push values of -1 or empty strings onto the stack. How would consumers of this implementation be guaranteed that they are always retrieving valid data?

Thanks again for the library/examples!

Zach Fisher...

1. Redimming doesn't blank the array, as you can see when you max out the size and it automatically doubles. I could make a new array, I might do some checking to see which is faster.

2. I'm not sure what to do about that... I could change it to return blank, but that doesn't solve the problem 'cause the user could want blank as an item in the stack. My suggestion would be for the user to check _Stack_IsEmpty before calling pop, if they think there's a chance of the return value is confusing the program.

Thanks for your comments/questions.

[Achilles]

Updated

Now includes _Quere_* functions