До сих пор мы рассматривали коллекции, которые обеспечивают очень простое хранение данных, по существу абстракции над массивом. В этом разделе мы рассмотрим, что происходит, когда мы добавляем несколько очень простых поведений, которые полностью меняют полезность коллекций.
стек
Стек — это коллекция, которая возвращает объекты вызывающей стороне по схеме «последний пришел-первый вышел» (LIFO). Это означает, что последний объект, добавленный в коллекцию, будет первым возвращенным объектом.
Стеки отличаются от списков и массивов. Они не могут быть проиндексированы напрямую, объекты добавляются и удаляются разными методами, а их содержимое более непрозрачно, чем списки и массивы. Под этим я подразумеваю, что хотя коллекция на основе списка предоставляет метод Contains, стек не предоставляет. Кроме того, стек не перечисляем. Чтобы понять, почему это так, давайте посмотрим, что такое стек и как использование стека определяет эти различия.
Одной из наиболее распространенных аналогий для стека является стопка ресторанных тарелок. Это простое подпружиненное устройство, на которое укладываются чистые пластины. Пружина гарантирует, что независимо от того, сколько пластин находится в стопке, доступ к верхней пластине будет простым. Чистые тарелки добавляются в верхнюю часть стопки, и когда клиент удаляет тарелку, он или она убирает самую верхнюю тарелку (самую последнюю добавленную тарелку).
Начнем с пустой подставки для тарелок.
И затем мы добавляем красную, синюю и зеленую табличку в стойку в указанном порядке.
Ключевой момент, который необходимо понять, заключается в том, что по мере добавления новых пластин они добавляются в верхнюю часть стопки. Если клиент забирает тарелку, он или она получит последнюю добавленную тарелку (зеленая тарелка). Следующий клиент получит синюю табличку, и, наконец, красная табличка будет удалена.
Теперь, когда мы понимаем, как работает стек, давайте определим несколько новых терминов. Когда элемент добавляется в стек, он «проталкивается» методом Push . Когда элемент удаляется из стека, он «выталкивается» с помощью метода Pop . Самый верхний элемент в стеке, добавленный последним, можно «выглянуть» при использовании метода Peek . Peeking позволяет просматривать элемент, не вынимая его из стопки (точно так же, как покупатель на подставке для тарелок сможет увидеть цвет верхней тарелки). Имея в виду эти термины, давайте посмотрим на реализацию класса Stack .
Определение класса
Класс Stack определяет методы Push , Pop и Peek , свойство Count , и использует класс LinkedList<T> для хранения значений, содержащихся в стеке.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public class Stack
{
LinkedList _items = new LinkedList();
public void Push(T value)
{
throw new NotImplementedException();
}
public T Pop()
{
throw new NotImplementedException();
}
public T Peek()
{
throw new NotImplementedException();
}
public int Count
{
get;
}
}
|
От себя
| Поведение | Добавляет элемент на вершину стека. |
| Производительность | O (1) |
Поскольку мы используем связанный список в качестве нашего резервного хранилища, все, что нам нужно сделать, это добавить новый элемент в конец списка.
|
1
2
3
4
|
public void Push(T value)
{
_items.AddLast(value);
}
|
Поп
| Поведение | Удаляет и возвращает последний элемент, добавленный в стек. Если стек пуст, генерируется InvalidOperationException . |
| Производительность | O (1) |
Push добавляет элементы в конец списка, поэтому мы будем «выталкивать» их сзади. Если список пуст, выдается исключение.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
public T Pop()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«The stack is empty»);
}
T result = _items.Tail.Value;
_items.RemoveLast();
return result;
}
|
заглядывать
| Поведение | Возвращает последний элемент, добавленный в стек, но оставляет элемент в стеке. Если стек пуст, генерируется InvalidOperationException . |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
8
9
|
public T Peek()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«The stack is empty»);
}
return _items.Tail.Value;
}
|
подсчитывать
| Поведение | Возвращает количество предметов в стеке. |
| Производительность | O (1) |
Поскольку предполагается, что стек является непрозрачной структурой данных, почему у нас есть свойство Count ? Знание, является ли стек пустым ( Count == 0 ), очень полезно, тем более что Pop выдает исключение, когда стек пуст.
|
1
2
3
4
5
6
7
|
public int Count
{
get
{
return _items.Count;
}
}
|
Пример: калькулятор RPN
Классическим примером стека является калькулятор обратной польской нотации (RPN).
Синтаксис RPN довольно прост. Оно использует:
<operand> <operand> <operator>
а не традиционный
<operand> <operator> <operand>.
Другими словами, вместо того, чтобы говорить «4 + 2», мы бы сказали «4 2+». Если вы хотите понять историческое значение синтаксиса RPN, я призываю вас отправиться в Википедию или в вашу любимую поисковую систему.
Способ оценки RPN и причина, по которой стек так полезен при реализации калькулятора RPN, можно увидеть в следующем алгоритме:
|
1
2
3
4
5
6
7
8
|
for each input value
if the value is an integer
push the value on to the operand stack
else if the value is an operator
pop the left and right values from the stack
evaluate the operator
push the result on to the stack
pop answer from stack.
|
Таким образом, учитывая входную строку «4 2+», операции будут такими:
|
1
2
3
|
push (4)
push (2)
push (pop() + pop())
|
Теперь стек содержит одно значение: шесть (ответ).
Ниже приведена полная реализация простого калькулятора, который считывает уравнение (например, «4 2+») с консоли, разделяет входные данные в каждом пространстве ([«4», «2» и «+»]) и выполняет алгоритм RPN на входе. Цикл продолжается до тех пор, пока на входе не появится слово «выход».
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
void RpnLoop()
{
while (true)
{
Console.Write(«> «);
string input = Console.ReadLine();
if (input.Trim().ToLower() == «quit»)
{
break;
}
// The stack of integers not yet operated on.
Stack values = new Stack();
foreach (string token in input.Split(new char[] { ‘ ‘ }))
{
// If the value is an integer…
int value;
if (int.TryParse(token, out value))
{
// … push it to the stack.
values.Push(value);
}
else
{
// Otherwise evaluate the expression…
int rhs = values.Pop();
int lhs = values.Pop();
// … and pop the result back to the stack.
switch (token)
{
case «+»:
values.Push(lhs + rhs);
break;
case «-«:
values.Push(lhs — rhs);
break;
case «*»:
values.Push(lhs * rhs);
break;
case «/»:
values.Push(lhs / rhs);
break;
case «%»:
values.Push(lhs % rhs);
break;
default:
throw new ArgumentException(
string.Format(«Unrecognized token: {0}», token));
}
}
}
// The last item on the stack is the result.
Console.WriteLine(values.Pop());
}
}
|
Очередь
Очереди очень похожи на стеки — они предоставляют непрозрачную коллекцию, из которой объекты могут добавляться (помещаться в очередь) или удаляться (удаляться из очереди) таким образом, чтобы повысить ценность коллекции на основе списка.
Очереди представляют собой коллекцию «первым пришел — первым обслужен» (FIFO). Это означает, что элементы удаляются из очереди в том же порядке, в котором они были добавлены. Вы можете думать об очереди как о линии на кассе магазина — люди входят в линию и обслуживаются в порядке поступления.
Очереди обычно используются в приложениях для предоставления буфера для добавления элементов для последующей обработки или для упорядоченного доступа к общему ресурсу. Например, если база данных способна обрабатывать только одно соединение, можно использовать очередь, чтобы позволить потокам дождаться своей очереди (чтобы) получить доступ к базе данных.
Определение класса
Queue , как и Stack , поддерживается LinkedList . Кроме того, он предоставляет методы Enqueue (для добавления элементов), Dequeue (для удаления элементов), Peek и Count . Как и Stack , он не будет рассматриваться как коллекция общего назначения, то есть он не будет реализовывать ICollection<T> .
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public class Queue
{
LinkedList _items = new LinkedList();
public void Enqueue(T value)
{
throw new NotImplementedException();
}
public T Dequeue()
{
throw new NotImplementedException();
}
public T Peek()
{
throw new NotImplementedException();
}
public int Count
{
get;
}
}
|
Ставить
| Поведение | Добавляет элемент в конец очереди. |
| Производительность | O (1) |
Эта реализация добавляет элемент в начало связанного списка. Элемент можно так же легко добавить в конец списка. Все, что действительно имеет значение, — это то, что элементы помещаются в один конец списка и удаляются из другого (FIFO). Обратите внимание, что это противоположно классу Stack, где элементы добавляются и удаляются с одного конца (LIFO).
|
1
2
3
4
|
Public void Enqueue(T value)
{
_items.AddFirst(value);
}
|
Dequeue
| Поведение | Удаляет и возвращает самый старый элемент из очереди. InvalidOperationException если очередь пуста. |
| Производительность | O (1) |
Поскольку Enqueue добавил элемент в начало списка, Dequeue должен удалить элемент в конце списка. Если очередь не содержит элементов, генерируется исключение.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
public T Dequeue()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«The queue is empty»);
}
T last = _items.Tail.Value;
_items.RemoveLast();
return last;
}
|
заглядывать
| Поведение | Возвращает следующий элемент, который будет возвращен, если вызван Dequeue. Очередь оставлена без изменений. InvalidOperationException генерируется, если очередь пуста. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
8
9
|
public T Peek()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«The queue is empty»);
}
return _items.Tail.Value;
}
|
подсчитывать
| Поведение | Возвращает количество элементов, находящихся в данный момент в очереди. Возвращает 0, если очередь пуста. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
|
public int Count
{
get
{
return _items.Count;
}
}
|
Deque (Двусторонняя очередь)
Двусторонняя очередь, или deque, расширяет поведение очереди, позволяя добавлять или удалять элементы с обеих сторон очереди. Это новое поведение полезно в нескольких проблемных областях, особенно в задачах и планировании потоков. Это также обычно полезно для реализации других структур данных. Мы увидим пример использования deque для реализации другой структуры данных позже.
Определение класса
Класс Deque поддерживается двусвязным списком. Это позволяет нам добавлять и удалять элементы из передней или задней части списка и получать доступ к First и Last свойствам. Основные изменения между классом Queue и классом Enqueue Dequeue , что методы Enqueue , Dequeue и Peek были удвоены в First и Last вариантах.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
public class Deque
{
LinkedList _items = new LinkedList();
public void EnqueueFirst(T value)
{
throw new NotImplementedException();
}
public void EnqueueLast(T value)
{
throw new NotImplementedException();
}
public T DequeueFirst()
{
throw new NotImplementedException();
}
public T DequeueLast()
{
throw new NotImplementedException();
}
public T PeekFirst()
{
throw new NotImplementedException();
}
public T PeekLast()
{
throw new NotImplementedException();
}
public int Count
{
get;
}
}
|
Ставить
EnqueueFirst
| Поведение | Добавляет указанное значение в начало очереди. Это будет следующий предмет, снятый с производства DequeueFirst. |
| Производительность | O (1) |
|
1
2
3
4
|
public void EnqueueFirst(T value)
{
_items.AddFirst(value);
}
|
EnqueueLast
| Поведение | Добавляет указанное значение в конец очереди. Это будет следующий предмет, снятый с производства DequeueLast. |
| Производительность | O (1) |
|
1
2
3
4
|
public void EnqueueLast(T value)
{
_items.AddLast(value);
}
|
Dequeue
DequeueFirst
| Поведение | Удаляет и возвращает первый элемент в деке. InvalidOperationException генерируется, если очередь пуста. |
| Производительность | O (1) |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
public T DequeueFirst()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«DequeueFirst called when deque is empty»);
}
T temp = _items.Head.Value;
_items.RemoveFirst();
return temp;
}
|
DequeueLast
| Поведение | Удаляет и возвращает последний элемент в деке. InvalidOperationException генерируется, если очередь пуста. |
| Производительность | O (1) |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
public T DequeueLast()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«DequeueLast called when deque is empty»);
}
T temp = _items.Tail.Value;
_items.RemoveLast();
return temp;
}
|
PeekFirst
| Поведение | Возвращает первый элемент в деке, но оставляет коллекцию без изменений. InvalidOperationException генерируется, если очередь пуста. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
8
9
|
public T PeekFirst()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«PeekFirst called when deque is empty»);
}
return _items.Head.Value;
}
|
PeekLast
| Поведение | Возвращает последний элемент в деке, но оставляет коллекцию без изменений. InvalidOperationException генерируется, если очередь пуста. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
8
9
|
public T PeekLast()
{
if (_items.Count == 0)
{
throw new InvalidOperationException(«PeekLast called when deque is empty»);
}
return _items.Tail.Value;
}
|
подсчитывать
| Поведение | Возвращает количество элементов, находящихся в данный момент в деке, или 0, если деку пусто. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
|
public int Count
{
get
{
return _items.Count;
}
}
|
Пример: реализация стека
Запросы часто используются для реализации других структур данных.
Мы видели стек, реализованный с использованием LinkedList , так что теперь давайте посмотрим на стек, реализованный с помощью Deque .
Вы можете удивиться, почему я выбрал бы реализацию Stack с использованием Deque а не LinkedList . Причина заключается в производительности и возможности повторного использования кода. Связанный список имеет стоимость накладных расходов на узел и уменьшенную локальность данных — элементы распределяются в куче, и области памяти могут не находиться рядом друг с другом, что приводит к большему количеству пропусков кэша и сбоев страниц в ЦП и оборудовании памяти уровни. Более эффективная реализация очереди может использовать массив в качестве резервного хранилища, а не список. Это позволило бы снизить накладные расходы на узел и повысить производительность за счет решения некоторых локальных проблем.
Однако реализация Stack или Queue в виде массива является более сложной реализацией. Deque таким более сложным способом и используя его в качестве основы для других структур данных, мы можем реализовать преимущества производительности для всех структур, при этом нужно всего лишь написать код один раз. Это ускоряет время разработки и снижает затраты на обслуживание.
Мы рассмотрим пример Deque как массива позже в этом разделе, но сначала давайте рассмотрим пример Stack реализованного с использованием Deque .
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class Stack
{
Deque _items = new Deque();
public void Push(T value)
{
_items.EnqueueFirst(value);
}
public T Pop()
{
return _items.DequeueFirst();
}
public T Peek()
{
return _items.PeekFirst();
}
public int Count
{
get
{
return _items.Count;
}
}
}
|
Обратите внимание, что вся проверка ошибок теперь откладывается в Deque и любая оптимизация или исправление ошибок, внесенных в Deque будут автоматически применяться к классу Stack . Внедрение Queue так же просто, и поэтому читателю остается это упражнение.
Array Backing Store
Как упомянуто ранее, есть преимущество использования массива, а не связанного списка в качестве резервного хранилища для Deque<int> (deque of integer). Концептуально это кажется простым, но на самом деле есть несколько проблем, которые необходимо решить, чтобы это работало.
Давайте посмотрим на некоторые из этих проблем графически, а затем посмотрим, как мы можем с ними справиться. Попутно имейте в виду вопросы политики роста, обсуждаемые в разделе ArrayList, и то, что эти же проблемы применимы и здесь.
Когда коллекция создана, это массив 0 длины. Давайте посмотрим, как некоторые действия влияют на внутренний массив. Проходя через это, обратите внимание, что зеленый «h» и красный «t» на рисунках обозначают «голову» и «хвост» соответственно. Голова и хвост — это индексы массива, которые указывают первый и последний элементы в очереди. По мере добавления и удаления предметов взаимодействие между головой и хвостом станет более понятным.
|
1
2
|
Deque deq = new Deque();
deq.EnqueueFirst(1);
|
|
1
|
deq.EnqueueLast(2);
|
|
1
|
deq.EnqueueFirst(0);
|
Обратите внимание, что произошло в этот момент. Индекс заголовка обернут до конца массива. Теперь первым элементом в deque, который будет возвращен DequeueFirst , является значение индекса массива три (ноль).
|
1
|
deq.EnqueueLast(3);
|
На данный момент массив заполнен. При добавлении другого элемента происходит следующее:
- Политика роста будет определять размер нового массива.
- Элементы будут скопированы с головы до хвоста в новый массив.
- Новый элемент будет добавлен.
-
EnqueueFirst— элемент добавляется с нулевым индексом (операция копирования оставляет это открытым). -
EnqueueLast— элемент добавляется в конец массива.
-
|
1
|
deq.EnqueueLast(4);
|
Теперь давайте посмотрим, что происходит, когда предметы удаляются из Deque.
|
1
|
deq.DequeueFirst();
|
|
1
|
deq.DequeueLast();
|
Критическая точка, на которую следует обратить внимание, заключается в том, что независимо от емкости внутреннего массива логическим содержимым Deque являются элементы от индекса заголовка до индекса хвоста, принимая во внимание необходимость перехода в конец массива. Массив, который обеспечивает поведение обтекания от головы до хвоста, часто называют круговым буфером.
С этим пониманием того, как работает логика массива, давайте погрузимся прямо в код.
Определение класса
Методы и свойства Deque на основе массива такие же, как и на основе списка, поэтому здесь они не будут повторяться. Однако список был заменен массивом, и теперь есть три свойства, которые содержат информацию о размере, заголовке и хвосте.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
|
public class Deque
{
T[] _items = new T[0];
// The number of items in the queue.
int _size = 0;
// The index of the first (oldest) item in the queue.
int _head = 0;
// The index of the last (newest) item in the queue.
int _tail = -1;
…
}
|
Ставить
Политика роста
Когда внутренний массив должен увеличиваться, необходимо запустить алгоритм для увеличения размера массива, копирования содержимого массива и обновления значений внутреннего индекса. Метод Enqueue выполняет эту операцию и вызывается как EnqueueFirst и EnqueueLast . Параметр startingIndex индекс используется, чтобы определить, оставить ли слот массива открытым при нулевом индексе (в случае EnqueueFirst ).
Обратите особое внимание на то, как разворачиваются данные в тех случаях, когда обход от головы до хвоста требует возврата конца массива к нулю.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
private void allocateNewArray(int startingIndex)
{
int newLength = (_size == 0) ?
T[] newArray = new T[newLength];
if (_size > 0)
{
int targetIndex = startingIndex;
// Copy the contents…
// If the array has no wrapping, just copy the valid range.
// Else, copy from head to end of the array and then from 0 to the tail.
// If tail is less than head, we’ve wrapped.
if (_tail < _head)
{
// Copy the _items[head].._items[end] -> newArray[0]..newArray[N].
for (int index = _head; index < _items.Length; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
// Copy _items[0].._items[tail] -> newArray[N+1]..
for (int index = 0; index <= _tail; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
}
else
{
// Copy the _items[head].._items[tail] -> newArray[0]..newArray[N]
for (int index = _head; index <= _tail; index++)
{
newArray[targetIndex] = _items[index];
targetIndex++;
}
}
_head = startingIndex;
_tail = targetIndex — 1;
}
else
{
// Nothing in the array.
_head = 0;
_tail = -1;
}
_items = newArray;
}
|
EnqueueFirst
| Поведение | Добавляет указанное значение в начало очереди. Это будет следующий предмет, снятый с производства DequeueFirst. |
| Производительность | O (1) в большинстве случаев; O (n), когда рост необходим. |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public void EnqueueFirst(T item)
{
// If the array needs to grow.
if (_items.Length == _size)
{
allocateNewArray(1);
}
// Since we know the array isn’t full and _head is greater than 0,
// we know the slot in front of head is open.
if (_head > 0)
{
_head—;
}
else
{
// Otherwise we need to wrap around to the end of the array.
_head = _items.Length — 1;
}
_items[_head] = item;
_size++;
}
|
EnqueueLast
| Поведение | Добавляет указанное значение в конец очереди. Это будет следующий предмет, снятый с производства DequeueLast. |
| Производительность | O (1) в большинстве случаев; O (n), когда рост необходим. |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public void EnqueueLast(T item)
{
// If the array needs to grow.
if (_items.Length == _size)
{
allocateNewArray(0);
}
// Now we have a properly sized array and can focus on wrapping issues.
// If _tail is at the end of the array we need to wrap around.
if (_tail == _items.Length — 1)
{
_tail = 0;
}
else
{
_tail++;
}
_items[_tail] = item;
_size++;
}
|
Dequeue
DequeueFirst
| Поведение | Удаляет и возвращает первый элемент в деке. InvalidOperationException генерируется, если очередь пуста. |
| Производительность | O (1) |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public T DequeueFirst()
{
if (_size == 0)
{
throw new InvalidOperationException(«The deque is empty»);
}
T value = _items[_head];
if (_head == _items.Length — 1)
{
// If the head is at the last index in the array, wrap it around.
_head = 0;
}
else
{
// Move to the next slot.
_head++;
}
_size—;
return value;
}
|
DequeueLast
| Поведение | Удаляет и возвращает последний элемент в деке. InvalidOperationException генерируется, если очередь пуста. |
| Производительность | O (1) |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public T DequeueLast()
{
if (_size == 0)
{
throw new InvalidOperationException(«The deque is empty»);
}
T value = _items[_tail];
if (_tail == 0)
{
// If the tail is at the first index in the array, wrap it around.
_tail = _items.Length — 1;
}
else
{
// Move to the previous slot.
_tail—;
}
_size—;
return value;
}
|
PeekFirst
| Поведение | Возвращает первый элемент в деке, но оставляет коллекцию без изменений. InvalidOperationException если очередь пуста. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
8
9
|
public T PeekFirst()
{
if (_size == 0)
{
throw new InvalidOperationException(«The deque is empty»);
}
return _items[_head];
}
|
PeekLast
| Поведение | Возвращает последний элемент в деке, но оставляет коллекцию без изменений. InvalidOperationException если очередь пуста. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
8
9
|
public T PeekLast()
{
if (_size == 0)
{
throw new InvalidOperationException(«The deque is empty»);
}
return _items[_tail];
}
|
подсчитывать
| Поведение | Возвращает количество элементов, находящихся в данный момент в деке, или 0, если деку пусто. |
| Производительность | O (1) |
|
1
2
3
4
5
6
7
|
public int Count
{
get
{
return _size;
}
}
|
Следующий
Это завершает четвертую часть о стеках и очередях. Далее мы перейдем к бинарному дереву поиска.