• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • ✅ Time to vote for the top 3 models! The POLL for Hive's 6th HD Modeling Contest: Mechanical is now open! 📅 Poll close on July 16, 2024! 🔗 Cast your vote now!

The QueueStack

Level 31
Joined
Jul 10, 2007
Messages
6,306
graveyard this please, the structure is useless

Requires knowledge of the QueueQueue.

To use, see the QueueStack library.

Imagine that a set of objects were encoded into a code-
3,5,7,9

Recall that when encoding anything, things are written from left to right, but read out from right to left.

Write: 3,5,7,9
Read: 9,7,5,3

Remember that the premise of the usefulness of QueueQueues were saving objects rather than sets of data? If there were to be 3 items with different maximum charges

Code:
item 1
    16

item 2
    102

item 3
    12

And 3 items were to be saved: 1, 2, and 3, it would be written 1,16,2,102,3,12 but read out as 12,3,102,2,16,1. Based on the 1, you know that the max charge is 16. If you were given the charge, would you know the corresponding item? If only max charges could be stored, then sure (12->1), but remember that 12 represents a range of the values from 0 to 12. Furthermore, how do you even know how big the 12 is? The maximum for each item charge is different. To read values out of a save/load code, it requires dividing the save/load code by the value's maximum+1. For example, reading the 12 out of it would requiring dividing it by 13. How do you know what to divide it by when a random property with a random value may or may not be there? You don't, it's like trying to divide a black box out of a blob.

So essentially, writing a QueueQueue representing a set of objects straight into a save/load code will give an unreadable code. The only possible way to read the code out is to read the object first, then the properties. So for example, rather than writing the item first, the item charges would be written first, then the item.

So rather than 1,16,2,102,3,12, write 16,1,102,2,12,3. Why not just reverse all of them? Because then the actual objects would be read backwards. All that needs to be backwards are the objects and the properties directly to the right of them, that way the when reading from right to left, one can read the object and then read its properties.

Taking 16,1,102,2,12,3, the first value is a 3, which is an item. Based on that 3, the code knows to next divide by 13, then it knows to read another item, then based on that item (2), divide by 103, etc.

So, if a QueueQueue were to have a set of data
Code:
1	6
	7
	8
	9
	10

2	11
	12
	13
	14
	15

3	16
	17
	18
	19
	20

4	21
	22
	23
	24
	25

5	26
	27
	28
	29
	30

It would be this as a QueueStack
Code:
6	1
	7
	8
	9
	10

11	2
	12
	13
	14
	15

16	3
	17
	18
	19
	20

21	4
	22
	23
	24
	25

26	5
	27
	28
	29
	30

It might look funky, but think of the rows of a given object as being stacks.
Code:
1	6

In the QueueQueue, the 1 is written, then the 6 (the 6 placed after the 1). In the same way, the 1 and then the 6 are written, but the 6 goes in front of the 1 rather than after it. If there was a set of columns on a row in a QueueQueue

Code:
1  3  5  7  9

It would be reversed in a QueueStack

Code:
9 7 5 3 1

If they were to have some arbitrary data under them, the data would not follow. Keep in mind that only the [1 3 5 7 9] are a row, the rest are just in columns that happen to be next to each other.

QueueQueue (with added lines so that columns and rows can be seen)
Code:
----------------------
|1|  |3|  |5|  |7|  |9|
----------------------
|8|  |2|  |0|  |9|  |1|
|1|  |2|  |9|  |1|  |0|
|6|  |7|  |2|  |3|  |1|
|4|  |4|  |5|  |7|  |8|

QueueStack
Code:
----------------------
|9|  |7|  |5|  |3|  |1|
----------------------
|8|  |2|  |0|  |9|  |1|
|1|  |2|  |9|  |1|  |0|
|6|  |7|  |2|  |3|  |1|
|4|  |4|  |5|  |7|  |8|

Notice that the columns did not reverse, only the rows.

To understand the diagram more, 9 points to 7 (next column), but 8 doesn't point to 2. 2 is the next row of 7 and 8 is the next row of 9.
Code:
----------------------
|9|  |7|  |5|  |3|  |1|
----------------------
|8|  |2|  |0|  |9|  |1|

In reality though, it actually looks more like this
Code:
head: 9 8

9: 7 2
7: 5 0
5: 3 9
3: 1 1

QueueStacks are extremely difficult to add to and loop through. Essentially, a QueueStack is a QueueQueue of pure stack pointers. The stack pointers then point to a collection of nodes. The loop itself actually loops through the QueueQueue + the nodes within the stacks in the QueueQueue (and not all of the stacks can have nodes in them).
 
Last edited:
Level 31
Joined
Jul 10, 2007
Messages
6,306
Get rid of the tut. It's useless. I gotta code a ListStack to get the concept working right. Notice this

Code:
----------------------
|9|  |7|  |5|  |3|  |1|
----------------------
|8|  |2|  |0|  |9|  |1|
|1|  |2|  |9|  |1|  |0|
|6|  |7|  |2|  |3|  |1|
|4|  |4|  |5|  |7|  |8|

The upper right corner would be the last object put into the code but the bottom right corner would be the last value actually written, meaning that the entire concept fails.

A ListStack could do the row stacks but then read the column backwards. It couldn't be a StackStack as that would have 0 order to it.

However, if you are having a ListStack, then you need to store initial values into stacks of queues in order to maintain the proper order. The first value written into the code should be the first value the user provides. It's read out backwards, but the first value is a special value as it can be added to the code rather than multiplied in.


edit
Nevermind, let me think on this for a while. A ListStack wouldn't work either.

Thinking this is smarter
Code:
----------------------
|1|  |3|  |5|  |7|  |9|
----------------------
|8|  |2|  |0|  |9|  |1|
|1|  |2|  |9|  |1|  |0|
|6|  |7|  |2|  |3|  |1|
|4|  |4|  |5|  |7|  |8|


to


----------------------
|9|  |7|  |5|  |3|  |1|
----------------------
|1|  |9|  |0|  |2|  |8|
|0|  |1|  |9|  |2|  |1|
|1|  |3|  |2|  |7|  |6|
|8|  |7|  |5|  |4|  |4|


edit
yea, graveyard this please =)
 
Last edited:
Top