Algorithm - queue, stack, node

Take an encryption case for example. You are given a sequence of number, 6 3 1 7 5 8 9 2 4, which is encrypted. To get the real meaning, we delete 6 and put 3 to the end, and the number becomes 1 7 5 8 9 2 4 3. Then we delete 1 and put 7 to the end, the number becomes 5 8 9 2 4 3 7. We delete 5 and put 8 to the end, getting 9 2 4 3 7 8... Eventually the numbers get deleted are 6 1 5 9 4 7 2 8 3.

Queue is a special structure, which only allows the elements at head to be deleted, which is called pop out. It only allows to input new elements at tail, means pop in. When head == tail, the queue is empty.

What is stack? Suppose we have a bucket, and we can only put in one ball each time. We now put in ball 2, 1, 3. If you want to take out ball 2, then you have to take ball 3 out first, and then ball 1.

We can use stack to determine whether a string is equal no matter if you read it forward or backward.

Now let's talk about node. We often use array to store numbers, but it is not always convenient. For example, we have a sequence of numbers, arranged in ascending order, 2 3 5 8 9 10 18 26 32. If we want to input 6 and ensure the new sequence is still in ascending order, then we have to move all the numbers after 8 if we use array.

What is node? Node is 2-3-5-8-9-10-18-26-32. If we want to input 6, we just need 2-3-5-6-8-9-10-18-26-32. Each node has two parts, one stores the data, using an int. The other stores the address of next data, using pointer.

An alternative way to realize node is to use array to simulate it. Suppose we have the data 2 3 5 8 9 10 18 26 32, we need to use another array called right to store the position of the number on the right of the data 2 3 4 5 6 7 8 9 0. For instance, right[1] = 2, means the number on the right of data[1] is in data[2]. right[9] = 0, means there is no number of the right of 9.

If we want to input 6, we only need to put it at the end, data[10] = 6. Then we need to change right[3] = 10, means we put the number on the right of data[3] to data[10]. We also need to set right[10] = 4, means the number right to data[10] is in data[4].