TECHY360
Everything You Need To Know About Tech

Stacks and Queues: Algorithms and data structures for beginners

0 24

In the previous parts, we considered the basic data structures, which, in fact, were add-ons over an array. In this article, we will add simple operations to the collections and see how this affects their capabilities.

Stack

A stack is a collection whose elements are obtained according to the principle “last entered, first released” (Last-In-First-Out or LIFO) . This means that we will have access only to the last element added.

Unlike lists, we cannot access an arbitrary stack element. We can only add or remove items using special methods. The stack does not have a method Containslike lists. In addition, the stack does not have an iterator. In order to understand why such restrictions are imposed on the stack, let’s look at how it works and how it is used.

The most common analogy for explaining a stack is a stack of plates. Regardless of how many plates in the stack, we can always remove the top. Clean plates are placed on the top of the stack in the same way, and we will always be the first to take the plate that was put last.

If we put, for example, a red plate, then a blue, and then a green plate, then we must first remove the green plate, then the blue plate, and finally the red one. The main thing to remember is that the plates are always placed on the top of the stack. When someone takes a plate, he also removes it from above. It turns out that the plates are sorted out in the order opposite to the one in which they were placed.

Now that we understand how the stack works, we introduce a few terms. The operation of adding an element to the stack is called “push”, deleting is “pop”. The last item added is called the top of the stack, or “top,” and can be viewed using peek. Let’s now look at the preparation of the class that implements the stack.

Class stack

The class Stackdefines the methods PushPopPeekto access the elements and the field Count. In the implementation, we will use LinkedList<T>to store items.

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

Push method

  • Behavior: Adds an item to the top of the stack.
  • Difficulty: O (1).

Since we use a linked list to store items, we can simply add a new one to the end of the list.

public void Push (T value)
{
    _items.AddLast (value);
}

Pop method

  • Behavior: Removes an item from the top of the stack and returns it. If the stack is empty, rolls InvalidOperationException.
  • Difficulty: O (1).

Pushadds items to the end of the list, so it will also pick them up from the end. In case the list is empty, an exception will be thrown.

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

    T result = _items.Tail.Value;

    _items.RemoveLast ();

    return result;
}

Peek method

  • Behavior: Returns the top item in the stack, but does not remove it. If the stack is empty, rolls InvalidOperationException.
  • Difficulty: O (1).
public T Peek ()
{
    if (_items.Count == 0)
    {
        throw new InvalidOperationException ("The stack is empty");
    }

    return _items.Tail.Value;
}

Count method

  • Behavior: Returns the number of items in the stack.
  • Difficulty: O (1).

Why do we need to know how many items are on the stack if we still don’t have access to them? Using this field we can check if there are any items on the stack or if it is empty. This is very useful, given that the method Popthrows an exception.

public int Count
{
    get
    {
        return _items.Count;
    }
}

Example: a calculator in the reverse polish record.

A classic example of using a stack is a calculator in reverse Polish, or postfix, writing. In it, the operator is written after its operands. That is, we write:

<operand> <operand> <operator>

instead of the traditional:

<operand> <operator> <operand>

In other words, instead of “4 + 2” we will write “4 2 +”. If you are interested in the origin of the reverse Polish record and its name, you can find out about it on Wikipedia or in a search engine.

The way the reverse Polish entry is calculated and why the stack is so useful when using it can be clearly seen from the following algorithm:

for each input value
    if the value is an integer
        push the value of the stack
    else if the value is an operator
        pop the stack
        evaluate the operator
        push the result
pop answer from stack.

That is, for the expression “4 2 +” actions will be as follows:

push (4)
push (2)
push (pop () + pop ())

At the end of the stack will be one value – 6.

The following is the complete code for a simple calculator that reads an expression (for example 4 2 +) from the console, splits the input data by spaces ( ["4", "2", "+"]), and executes the calculation algorithm. The calculation continues until the word is met quit.

void RpnLoop ()
{
    while (true)
    {
        Console.Write (">");
        string input = Console.ReadLine ();
        if (input.Trim (). ToLower () == "quit")
        {
            break;
        }
        // Stack of not yet processed values.
        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))
            {
                // ... put it on the stack.
                values.Push (value);
            }
            else
            {
                // otherwise perform the operation ...
                int rhs = values.Pop ();
                int lhs = values.Pop ();

                // ... and put the result back.
                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:
                        // If the operation is not +, -, * or /
                        throw new ArgumentException (
                            string.Format ("Unrecognized token: {0}", token));
                }
            }
        }

        // The last element on the stack is the result.
        Console.WriteLine (values.Pop ());
    }
}

Turn

The lines are very similar to stacks. They also do not give access to an arbitrary element, but, unlike the stack, elements are put (enqueue) and taken (dequeue) from different ends. This method is called “first in, first out” (First-In-First-Out or FIFO) . That is, we will pick up items from the queue in the same order as they were putting. Like a real line or conveyor.

Queues are often used in programs to implement a buffer in which you can put an element for subsequent processing, keeping the order of receipt. For example, if the database supports only one connection, you can use a queue of threads that will, oddly enough, wait for their turn to access the database.

Class queue

The class Queue, like the stack, will be implemented using a linked list. It will provide methods Enqueuefor adding an item, Dequeuefor deleting, Peekand Count. Like the class Stack, it will not implement the interface ICollection<T>, since these are special-purpose collections.

Related Posts
1 of 7
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;
    }
}

Enqueue method

  • Behavior: Adds an item to the queue.
  • Difficulty: O (1).

New elements of the queue can be added to the top of the list or to the end. It is only important that the elements reach from the opposite edge. In this implementation, we will add new items to the beginning of the internal list.

Public void Enqueue (T value)
{
    _items.AddFirst (value);
}

Dequeue method

  • Behavior: Removes the first item placed from the queue and returns it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).

As we insert elements at the top of the list, we’ll remove them from the end. If the list is empty, an exception is thrown.

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

    T last = _items.Tail.Value;

    _items.RemoveLast ();

    return last;
}

Peek method

  • Behavior: Returns the element that will return the next method call Dequeue. The queue remains unchanged. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
public T Peek ()
{
    if (_items.Count == 0)
    {
        throw new InvalidOperationException ("The queue is empty");
    }

    return _items.Tail.Value;
}

Count method

  • Behavior: Returns the number of items in the queue, or 0 if the queue is empty.
  • Difficulty: O (1).
public int Count
{
    get
    {
        return _items.Count;
    }
}

Two-way queue

Deque (Double Room-Ended queue) , or December (Deque) , extends the queue behavior. In December, you can add or remove items from both the beginning and the end of the queue. This behavior is useful in many tasks, such as scheduling thread execution or the implementation of other data structures. Later we will look at the stack implementation option using a two-way queue.

Class dequeue

The class is Dequeeasiest to implement using a doubly linked list. It allows you to view, delete and add items to the beginning and to the end of the list. The main difference from the usual two-way line – methods EnqueueDequeueand Peekare divided into pairs to work with both the list ends.

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 method

  • Behavior: Adds an item to the front of the queue. This item will be taken from the queue as follows when the method is called DequeueFirst.
  • Difficulty: O (1).
public void EnqueueFirst (T value)
{
    _items.AddFirst (value);
}

EnqueueLast method

  • Behavior: Adds an item to the end of the queue. This item will be taken from the queue as follows when the method is called DequeueLast.
  • Difficulty: O (1).
public void EnqueueLast (T value)
{
    _items.AddLast (value);
}

DequeueFirst method

  • Behavior: Removes an item from the front of the queue and returns it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
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 method

  • Behavior: Removes an item from the end of the queue and returns it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
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 method

  • Behavior: Returns an item from the front of the queue without changing it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
public T PeekFirst ()
{
    if (_items.Count == 0)
    {
        throw new InvalidOperationException ("PeekFirst called when deque is empty");
    }

    return _items.Head.Value;
}

PeekLast method

  • Behavior: Returns an item from the end of the queue without changing it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
public T PeekLast ()
{
    if (_items.Count == 0)
    {
        throw new InvalidOperationException ("PeekLast called when deque is empty");
    }

    return _items.Tail.Value;
}

Count method

  • Behavior: Returns the number of items in the queue, or 0 if the queue is empty.
  • Difficulty: O (1).
public int Count
{
    get
    {
        return _items.Count;
    }
}

Example: Stack Implementation

A two-way queue is often used to implement other data structures. Let’s look at an example of the implementation of the stack with its help.

You may have a question, why implement a stack based on a queue instead of a linked list. There are two reasons: performance and code reuse. A coherent list has the overhead of creating nodes and there is no guarantee that data is local: elements can be located anywhere in memory, which causes a large number of misses and a drop in performance at the processor level. A more productive implementation of a two-way queue requires an array to store the elements.

Nevertheless, implementing a stack or queue using an array is not an easy task, but implementing a two-way queue and using it as a basis for other data structures will give us a serious plus to performance and allow us to reuse code. This reduces the cost of support.

Later we will look at the variant of the queue using an array, but first let’s take a look at the stack class using the two-way queue:

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

Notice that all error handling now lies with the class Deque, and, in addition, any queue optimization will also affect the stack. Implementing a normal two-way queue is so simple that we leave it to the reader as an exercise.

Storage of elements in an array

As already mentioned, the implementation of the queue using an array has its advantages. It looks simple, but in fact there are a number of nuances that need to be taken into account.

Let’s look at the problems that may arise and their solution. In addition, we will need information on increasing the internal array from the previous article on dynamic arrays.

When creating a queue, an array of zero length is created inside it. The red letters “h” and “t” mean pointers _headand _tailrespectively.

Deque deq = new Deque ();
deq.EnqueueFirst (1);
Add an item to the beginning
Add an item to the beginning
deq.EnqueueLast (2);
Add item to end
deq.EnqueueFirst (0);
Add one more item to the beginning.

Note: the index of the head of the queue jumped to the top of the list. Now the first element that will be returned when the method DequeueFirstis called is 0 (index 3).

deq.EnqueueLast (3);
And one more to the end

The array is full, so when you add an item, the following will occur:

  • Algorithm growth will determine the size of the new array.
  • Elements are copied to the new array from the head to the tail.
  • A new item will be added.
deq.EnqueueLast (4);
Add a value to the end of the extended array

Now let’s see what happens when an item is deleted:

deq.DequeueFirst ();
Remove item from start
deq.DequeueLast ();
Remove item from end

The key point: regardless of the capacity or fullness of the internal array, logically, the contents of the queue are elements from the “head” to the “tail”, taking into account the “looping”. This behavior is also called a “ring buffer.”

Now let’s look at the implementation.

Dequeue class (using an array)

The array-based queue interface is the same as in the case of implementation via a linked list. We will not repeat it. However, since the list was replaced with an array, we added new fields — the array itself, its size, and pointers to the tail and head of the queue.

public class Deque
{
    T [] _items = new T [0];

    // The number of items in the queue.
    int _size = 0;

    // Index of the first (oldest) item.
    int _head = 0;

    // Index of the last (newest) item.
    int _tail = -1;
...
}

Growth algorithm

When the free space in the internal array ends, it is necessary to increase it, copy the elements and update the pointers to the “tail” and “head”. This operation is performed when necessary while adding an item. The parameter is startingIndexused to show how many fields at the beginning must be left empty (if added to the beginning).

Pay attention to how the data is extracted when you have to go to the beginning of the array when you pass from the “head” to the “tail”.

private void allocateNewArray (int startingIndex)
{
    int newLength = (_size == 0)? 4: _size * 2;

    T [] newArray = new T [newLength];

    if (_size> 0)
    {
        int targetIndex = startingIndex;

        // Copy the content ...
        // If the array is not looped, simply copy the elements.
        // Otherwise, copies from head to end, and then from the beginning of the array to tail.

        // If tail is smaller than head, go to the beginning.
        if (_tail <_head)
        {
            // Copy _items [head] .._ items [end] into newArray [0] .. newArray [N].
            for (int index = _head; index <_items.Length; index ++)
            {
                newArray [targetIndex] = _items [index];
                targetIndex ++;
            }

            // Copy _items [0] .._ items [tail] into newArray [N + 1] ..
            for (int index = 0; index <= _tail; index ++)
            {
                newArray [targetIndex] = _items [index];
                targetIndex ++;
            }
        }
        else
        {
            // Copy _items [head] .._ items [tail] into newArray [0] .. newArray [N]
            for (int index = _head; index <= _tail; index ++)
            {
                newArray [targetIndex] = _items [index];
                targetIndex ++;
            }
        }


        _head = startingIndex;
        _tail = targetIndex - 1;
    }
    else
    {
        // The array is empty.
        _head = 0;
        _tail = -1;
    }

    _items = newArray;
}

EnqueueFirst method

  • Behavior: Adds an item to the front of the queue. This item will be taken from the queue as follows when the method is called DequeueFirst.
  • Difficulty: O (1) in most cases; O (n), when you need to expand the array.
public void EnqueueFirst (T item)
{
    // Check if array expansion is necessary:
    if (_items.Length == _size)
    {
        allocateNewArray (1);
    }

    // Since the array is empty and _head is greater than 0,
    // we know that there is a place at the beginning of the array.
    if (_head> 0)
    {
        _head--;
    }
    else
    {
        // Otherwise, we must loop.
        _head = _items.Length - 1;
    }

    _items [_head] = item;


    _size ++;

    if (_size == 1)
    {
        // If we added the first element to empty
        // turn, it will also be the last, therefore
        // need to update and _tail.
        _tail = _head;
    }
}

EnqueueLast method

  • Behavior: Adds an item to the end of the queue. This item will be taken from the queue as follows when the method is called DequeueLast.
  • Difficulty: O (1) in most cases; O (n), when you need to expand the array.

public void EnqueueLast (T item)
{
    // Check if array expansion is necessary:
    if (_items.Length == _size)
    {
        allocateNewArray (0);
    }

    // Now that we have the appropriate array
    // if _tail is at the end of the array, we need to go to the beginning.
    if (_tail == _items.Length - 1)
    {
        _tail = 0;
    }
    else
    {
        _tail ++;
    }

    _items [_tail] = item;
    _size ++;

    if (_size == 1)
    {
        // If we added the last element to empty
        // turn, it will be the first, therefore
        // need to update and _head.
        _head = _tail;
    }
}

DequeueFirst method

  • Behavior: Removes an item from the beginning of the queue and returns it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
public T DequeueFirst ()
{
    if (_size == 0)
    {
        throw new InvalidOperationException ("The deque is empty");
    }

    T value = _items [_head];

    if (_head == _items.Length - 1)
    {
        // If head is set on the last index, go to the beginning of the array.
        _head = 0;
    }
    else
    {
        // Go to the next element.
        _head ++;
    }

    _size--;

    return value;
}

DequeueLast method

  • Behavior: Removes an item from the end of the queue and returns it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).

public T DequeueLast ()
{
    if (_size == 0)
    {
        throw new InvalidOperationException ("The deque is empty");
    }

    T value = _items [_tail];

    if (_tail == 0)
    {
        // If tail is set to the beginning of the array, go to the end.
        _tail = _items.Length - 1;
    }
    else
    {
        // Go to the previous item.
        _tail--;
    }

    _size--;

    return value;
}

PeekFirst method

  • Behavior: Returns an item from the beginning of the queue without changing it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
public T PeekFirst ()
{
    if (_size == 0)
    {
        throw new InvalidOperationException ("The deque is empty");
    }

    return _items [_head];
}

PeekLast method

  • Behavior: Returns an item from the end of the queue without changing it. If the queue is empty, throws InvalidOperationException.
  • Difficulty: O (1).
public T PeekLast ()
{
    if (_size == 0)
    {
        throw new InvalidOperationException ("The deque is empty");
    }

    return _items [_tail];
}

Count method

  • Behavior: Returns the number of items in the queue, or 0 if the queue is empty.
  • Difficulty: O (1).
public int Count
{
    get
    {
        return _size;
    }
}

To be continued

So we have completed the fourth part of our series of articles. In it, we looked at stacks and queues. Next time we will go to the binary search trees.

Get real time updates directly on you device, subscribe now.

Comments
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More