Detailed introduction to Data Structures extension in php

Because arrays are too powerful in PHP, these data structures are included, so there is no need to pay attention to these data structures, and these concepts will fade over time. There is an extension in PHP called Data Structures, which includes these common data structures. Let’s introduce it today.

In PHP, because arrays are too powerful, these data structures are included, so there is no need to pay attention to these data structures, and these concepts will fade over time. , does not mean that there are no data structures in PHP.

There is an extension Data Structures in PHP, which includes these common data structures.

PHP Data Structure

• Priority QueuePriorityQueue

• Double-ended QueueDeque

• Queue FIFO (first in, first out)

• Stack LIFO (first in, last out)

• Hash table Hash

• Set Collection
• Map Dictionary

Data Structure Introduction

Priority QueuePriorityQueue

PriorityQueue is very similar to Queue. Values ​​are pushed into the queue with the specified priority, and the value with the highest priority will always be at the front of the queue.

Note

• For values ​​with the same priority, the "first in, first out" order is preserved.

• Iterating PriorityQueue is destructive and is equivalent to continuous pop operations until the queue is empty.

Set capacity

The default capacity is 8, you can set the capacity manually. This capacity does not refer to the length of the queue, but to the storage space. Make sure there is enough memory when reallocating capacity

If the value is less than or equal to the current capacity, the capacity will remain unchanged.

$queue = new Ds\PriorityQueue(); 
$queue->allocate(8);

Get capacity

When the capacity is currently set manually, if the set capacity is greater than the actual occupied capacity, the set capacity will be returned. Otherwise, the actual capacity is returned.

$queue = new Ds\PriorityQueue(); 
// 此时返回默认值 8
$queue->capacity();

Set priority

The larger the value, the higher the priority

$queue = new Ds\PriorityQueue(); 
$queue->push('value1', 1);
$queue->push('value2', 2);

Example

$queue = new Ds\PriorityQueue(); 
$queue->push('沙僧', 2);
$queue->push('唐僧', 5);
$queue->push('白龙马', 1);
$queue->push('猪八戒', 3);
$queue->push('孙悟空', 4);
$cout = $queue->count();
for($i=0; $ipop();
  echo PHP_EOL;
}

Output

唐僧
孙悟空
猪八戒
沙僧
白龙马

Application scenario

• MySQL In order to speed up the query and avoid sorting without using the index, sorting was not performed and manual sorting was performed at the server code level before returning.

• Other application scenarios...

Double-ended queue Deque

has two pointers pointing to the head and tail respectively . Insertion and ejection can be performed at the head and tail respectively.

Advantages

• Supports array syntax (square brackets).

• Uses less memory than an array for the same number of values.

• Automatically free allocated memory when its size drops low enough.

• get(), set(), push(), pop(), shift() and unshift() are all O(1).

Disadvantages

• The set capacity value must be a power of 2, and the default value is 8. For example, 2^2

• insert() and remove() are O(n).

Class method description

Double-ended queueDeque

Example

$deque = new Ds\Deque();
$deque->push(...['唐僧', '孙悟空', '猪八戒', '沙僧', '白龙马']);
$clone = $deque->copy();
$count = $deque->count();
echo '头：'.$deque->first().PHP_EOL;
echo '尾：'.$deque->last().PHP_EOL;
echo '--- 从队尾开始 ----'.PHP_EOL;
for($i=0; $ipop();
    echo PHP_EOL;
}

echo '--- 从队头开始 ----'.PHP_EOL;
for($i=0; $ishift();
    echo PHP_EOL;
}

Output

头：唐僧
尾：白龙马
--- 从队尾开始 ----
白龙马
沙僧
猪八戒
孙悟空
唐僧
--- 从队头开始 ----
唐僧
孙悟空
猪八戒
沙僧
白龙马

Application scenario

• Multiple application scenarios

Queue FIFO (first in, first out)

The queue is a "first in, first out" or "FIFO" collection, which only allows Access the value at the front of the queue.

Example

$queue = new Ds\Queue(); 
$queue->push('唐僧');
$queue->push(...['孙悟空', '猪八戒']);
$queue->push(['沙僧', '白龙马']);
print_r($queue);

Output

Ds\Queue Object
(
    [0] => 唐僧
    [1] => 孙悟空
    [2] => 猪八戒
    [3] => Array
        (
            [0] => 沙僧
            [1] => 白龙马
        )
)

Stack LIFO (First In, Last Out)

Stack is a "last in first out" or "LIFO" collection that Only the value at the top of the structure is allowed to be accessed.

Example

$Stack = new Ds\Stack(); 
$Stack->push('唐僧');
$Stack->push(...['孙悟空', '猪八戒']);
$Stack->push(...['沙僧', '白龙马']);

$cout = $Stack->count();
for($i=0; $ipop();
    echo PHP_EOL;
}

Output

白龙马
沙僧
猪八戒
孙悟空
唐僧

Map Dictionary

Map is a sequential collection of key-value pairs [key=>value], similar to an array. Keys can be of any type but must be unique. If values ​​are added to the map using the same key, the later addition will replace the previous value.

Advantages

• Keys and values ​​can be of any type, including objects

• Supports array syntax.

• Preserve insertion order.

• Performance and memory efficiency are similar to data.

• Automatically free allocated memory when the size drops low enough.

Disadvantages

• When an object is used as a key, it cannot be converted to an array.

Set Set

Set is a series of unique values. There is only one set of keys that do not store values, and the keys cannot be repeated.

Advantages

• Values ​​can be of any type, including objects.

• Supports array syntax.

• Preserve insertion order.

• Automatically free allocated memory when the size drops low enough.

• The complexity of add(), remove() and contains() is O(1).

Disadvantages

• Does not support push(), pop(), insert(), shift() or unshift()

• If there is a deleted value in the buffer before the index being accessed, get() is O(n), otherwise it is O(1).

The difference between Map and Set

• The storage methods are different. Map stores the form [key => value], and Set stores the form [...keys];

• Map and Set both use keys to ensure orderliness. Therefore, modification of the key is not allowed.

Recommended learning: php video tutorial

The above is the detailed content of Detailed introduction to Data Structures extension in php. For more information, please follow other related articles on the PHP Chinese website!