In PHP, arrays are so powerful that they include all of these data structures, so you don’t need to pay much attention to them. Over time, the concept of data structures has faded, not that THERE are no data structures in PHP.

In PHP, there is an extension Data Structures that includes these common Data Structures. For details, see the connection Data Structures

PHP data structure

  • PriorityQueue PriorityQueue
  • Dual-end queue Deque
  • Queue FIFO(First in, first out)
  • Stack LIFO(first in, last out)

  • Hash table Hash

    • The Set collection
    • The Map of a dictionary

Introduction to data Structure

PriorityQueue PriorityQueue

PriorityQueue is very similar to Queue. The value is pushed into the queue with the specified priority, and the value with the highest priority is always at the front of the queue.

Pay attention to

  • Retain the first-in, first-out order for values with the same priority.
  • Iterating over a PriorityQueue is destructive and amounts to a continuous eject operation until the queue is empty.

Set the capacity

The default capacity is 8. You can set the capacity manually. The capacity is not the length of the queue, but the storage space. Make sure you have enough memory when you reallocate capacity

  • If the value is less than or equal to the current capacity, the capacity remains unchanged.

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

Get capacity

  • If the configured capacity is greater than the actual occupied capacity, the configured capacity is returned. Conversely, return the actual capacity.

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

    Set Priorities

    A larger value indicates a higher priority

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

    The sample

    $queue = new Ds\PriorityQueue(); $queue->push(' shaseng ', 2); $queue->push(' tseng ', 5); $queue->push(' 1 ', 1); $queue->push(); $queue->push(); $queue->push(' sun Wukong ', 4); $cout = $queue->count(); for($i=0; $i<$cout; $i++) { echo $queue->pop(); echo PHP_EOL; }

The output

Tang monk Sun Wukong pig eight quit sand monk white dragon horse

Application scenarios

  • MySQL query in order to speed up the query speed, to avoid sorting cannot use index, no sorting, in the server side code level to manually sort and then return.
  • Other Application Scenarios…

Dual-end queue Deque

There are two Pointers to the head and the tail. You can insert and eject at the head and tail, respectively.

advantages

  • Supports array syntax (square brackets).
  • Takes less memory than an array for the same number of values.
  • When its size drops low enough, the allocated memory is automatically freed.
  • Get (), set(), push(), pop(), shift(), and unshift() are all O(1).

disadvantages

  • The value of the capacity to be set. It must be a power of 2. The default value is 8. For example, 2 ^ 2
  • Insert () and remove() are O(n).

Class Method Description

Dual-end queue Deque

The sample

$deque = new Ds\Deque(); $deque->push(... [' Tang seng ', 'Sun Wukong ',' Pig Bajie ', 'Sha Seng ',' White Dragon Horse ']); $clone = $deque->copy(); $count = $deque->count(); $deque->first().PHP_EOL; $deque->last().php_eol; Echo '-- start at the end of the line ----'.PHP_EOL; for($i=0; $i<$count; $i++) { echo $deque->pop(); echo PHP_EOL; } echo '-- start at the head of the team ----'.PHP_EOL; for($i=0; $i<$count; $i++) { echo $clone->shift(); echo PHP_EOL; }

The output

Head: Tang's monk tail: white dragon horse ---- start from team tail ---- white dragon horse sand monk pig eight quit Sun Wukong Tang's monk -- start from team head ---- Tang's monk Sun Wukong pig eight quit sand monk white dragon horse

Application scenarios

  • Multiple application scenarios

Queue FIFO(First in, first out)

Queues are “first in, first out” or “FIFO” collections that allow access to only the values at the front of the queue.

The sample

$queue = new Ds\Queue(); $queue - > push (' tang's monk '); $queue->push(... [' Sun Wukong ', 'Pig bajie ']); $queue->push([' shaseng ', 'shaseng ']); print_r($queue);

The output

Ds \ Queue Object ([0] = [1] = > > tang's monk monkey [2] = > pig [3] = > Array ([0] = > sand monk [1] = > white dragon horse))

Stack LIFO(first in, last out)

A Stack is a “last in, first out” or “LIFO” collection that allows access only to the values at the top of the structure.

The sample

$Stack = new Ds\Stack(); $Stack - > push (' tang's monk '); $Stack->push(... [' Sun Wukong ', 'Pig bajie ']); $Stack->push(... [' Shaseng ', 'Bailongma ']); $cout = $Stack->count(); for($i=0; $i<$cout; $i++) { echo $Stack->pop(); echo PHP_EOL; }

The output

Bai Long Ma Sha's monk Pig bajie Sun Wu empty Tang Seng

The Map of a dictionary

A Map is a sequential collection of key and value pairs [key=>value], similar to an array. The key can be of any type, but must be unique. If a value is added to the map using the same key, the later value replaces the previous one.

advantages

  • Keys and values can be of any type, including objects
  • Support for array syntax.
  • Preserve the insertion order.
  • Performance and memory efficiency are similar to data.
  • Automatically free the allocated memory when the size drops low enough.

disadvantages

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

The Set collection

A Set is a Set of unique values. Only a Set of keys does not store a value, and the key cannot be repeated.

advantages

  • Values can be of any type, including objects.
  • Support for array syntax.
  • Preserve the insertion order.
  • Automatically free the allocated memory when the size drops low enough.
  • Add (), remove(), and contains() are all O(1).

disadvantages

  • Do not support push(), pop(), insert(), shift(), or unshift()
  • Get () is O(n) if there is a deleted value in the buffer before the index being accessed, otherwise it is O(1).

The difference between Map and Set

  1. Different storage methods. Map: [key => value]; Set: […keys];
  2. Maps and sets are ordered by keys, so changing keys is not allowed.