Algorithms: stacks, queues, linked lists

Posted on Edited on

This article describes the characteristics of the three data structures

queue

A string of encrypted QQ numbers is: 631758924. His decryption method is as follows: delete the first number, put the second number at the end, delete the third number, and put the fourth number at the end.. .To the last deleted numbers are connected together is the result after decryption
Implement the decryption process in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
list_input = []
# input
while True:
    number = input("give me number to input:\n")
    if number == 'done':
        break
    list_input.append(number)
# deleted numbers
delete = []
while True:
    if len(list_input) != 1:
        delete.append(list_input[0])
        del list_input[0]
        list_input.append(list_input[0])
        del list_input[0]
    else:
        delete.append(list_input[0])
        del list_input[0]
        break

print(delete)

The final output is: 615947283

It is more troublesome to use C in the book. First initialize an array int q[101], then add the number 0 before the input number, set the first number as head, and set the last position of the number at the end of the queue as tail.

If the tail is set as the tail of the queue, when there is only one element left in the queue, the coincidence of the head and the tail will bring some trouble. Here it is stipulated that when the head of the team and the tail of the team coincide, the queue is empty.

Delete a number: head++; add a new number: put the number to be added into q[tail], then tail++.

In this queue, the newcomers always stand at the back of the queue, the earlier the people who come, the earlier they can buy tickets, that is, the people who come first serve first, we call it “First In First Out” principle.

stack

‘xyzyx’ is a palindrome string, the so-called palindrome string refers to the same sequence of characters in both forward and reverse reading. Through the data structure of the stack, we can easily determine whether a string is a palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
list_input = []
while True:
    number = input("give me number to input:\n")
    if number == 'done':
        break
    list_input.append(number)

# If length is 3, mid_point is 1
mid_point = int(len(list_input)/2)
for i in range(0,mid_point):
    if list_input[i] != list_input[len(list_input)-1-i]:
        print("Not a palindrome")
        break
    elif i == mid_point-1:
        print("A palindrome")

In the book, in order to highlight the characteristics of the stack, that is, last in and then out (for example, when eating potato chips, if you want to eat the last slice, you must eat all of them), the author created a character array as a stack, and then put The first half of the test’s palindrome is placed on the stack:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
top = 0; //Initialization of stack
for (i=0;i<=mid;i++)
{
s[++top] = a[i];
}```

Then compare the second half of the characters with the characters in the stack one by one:
````C
for(i=next;i<=len-1;i++>)
{
if(a[i] != s[top])
break;
top--;
}

Because top is incremented by one each time a character is pushed into the stack at the beginning, the left side of the middle character, s[top], will not unexpectedly present the same character as a[i] on the right side of the middle character. Once top=0, it means that all characters in the stack have been output, and the tested character is indeed a palindrome.