Алгоритмы и структуры данных для начинающих: стеки и очереди

Метод Push

• 
  Поведение: Добавляет элемент на вершину стека.
  
• 
  Сложность: O(1).
  

Поскольку мы используем связный список для хранения элементов, можно просто добавить новый в конец списка.
public void Push(T value)
{
_items.AddLast(value);
}
Метод Pop

• 
  Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException.
  
• 
  Сложность: O(1).
  

Push добавляет элементы в конец списка, поэтому забирать их будет также с конца. В случае, если список пуст, будет выбрасываться исключение.
public T Pop()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("The stack is empty");
}

T result = _items.Tail.Value;

_items.RemoveLast();

return result;

}
Метод Peek

• 
  Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException.
  
• 
  Сложность: O(1).
  

public T Peek()
{
if (_items.Count == 0)
{
throw new InvalidOperationException("The stack is empty");
}

return _items.Tail.Value;

}
Метод Count

• 
  Поведение: Возвращает количество элементов в стеке.
  
• 
  Сложность: O(1).
  

Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.
public int Count
{
get
{
return _items.Count;
}
}
Пример: калькулятор в обратной польской записи
Классический пример использования стека — калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:
<операнд> <операнд> <оператор>
вместо традиционного:
<операнд> <оператор> <операнд>
Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.
То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:
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 +» действия будут следующие:
push(4)
push(2)
push(pop() + pop())
В конце на стеке окажется одно значение — 6.
Далее приводится полный код простого калькулятора, который считывает выражение (например, 4 2 +) из консоли, разбивает входные данные по пробелам (["4", "2", "+"]) и выполняет алгоритм вычисления. Вычисление продолжается до тех пор, пока не будет встречено слово quit.
void RpnLoop()
{
while (true)
{
Console.Write("> ");
string input = Console.ReadLine();
if (input.Trim().ToLower() == "quit")
{
break;
}
// Стек еще не обработанных значений.
Stack values = new Stack();

foreach (string token in input.Split(new char[] { ' ' }))

{
// Если значение - целое число...
int value;
if (int.TryParse(token, out value))
{
// ... положить его на стек.
values.Push(value);
}
else
{
// в противном случае выполнить операцию...
int rhs = values.Pop();
int lhs = values.Pop();

// ... и положить результат обратно.

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));
}
}
}

// Последний элемент на стеке и есть результат.

Console.WriteLine(values.Pop());
}
}
Очередь
Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.
Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД.