Stack, queue and linked list

In short: A stack gives back the last added element first (LIFO), a queue gives back the first added first (FIFO), and a linked list keeps each element in a node that points to the next.

Problem

"Undo" undoes the wrong thing

A text editor keeps the actions in a list. Ctrl+Z should undo the last one, but it undoes the first:

List<string> actions = new List<string>();
actions.Add("Typed text");
actions.Add("Made the title bold");
actions.Add("Inserted a photo");

// Ctrl+Z: undo the last action.
string undone = actions[0];
actions.RemoveAt(0);
Console.WriteLine("Undone: " + undone);
Console.WriteLine("Left: " + string.Join(", ", actions));

Output

Undone: Typed text
Left: Made the title bold, Inserted a photo

The fix is actions[^1] and actions.RemoveAt(actions.Count - 1): RemoveAt does not return the removed element, so you read it first. But everyone who touches this code has to remember which end to remove from. And at the store checkout it is the other way around: the first one who came is served first. Is there a collection that knows the end by itself?

The idea

Stack: the last one on top

A stack is like a pile of plates. You put on top and you take from the top. The last thing put in comes out first. This is called LIFO: last in, first out.

The "Back" button in the browser is a stack:

Stack<string> history = new Stack<string>();
history.Push("Home");
history.Push("Laptops");
history.Push("14-inch laptop");
Console.WriteLine("Now: " + history.Peek());

history.Pop();
Console.WriteLine("Back: " + history.Peek());
Console.WriteLine(string.Join(", ", history));

Output

Now: 14-inch laptop
Back: Laptops
Laptops, Home

• Push puts on top, Pop removes and returns the top one, and Peek only looks at the top one.
• Stack<T> is in System.Collections.Generic, like List<T>.
• string.Join goes through the stack from the top down.

More precisely, if you are curious

• Pop and Peek on an empty stack stop the program. TryPeek does not: it returns false if the stack is empty, and gives you the top element through out:

Stack<string> history = new Stack<string>();
if (history.TryPeek(out string page))
{
    Console.WriteLine("Now: " + page);
}
else
{
    Console.WriteLine("There is no previous page.");
}
history.Pop();

Error

Unhandled exception. System.InvalidOperationException: Stack empty.

The program first prints "There is no previous page.", and it stops at Pop. For Pop there is also TryPop.

• C# also has an older Stack class with no angle brackets, in System.Collections. It keeps everything as object. It works, but today you use Stack<T>:

Stack stack = new Stack();
stack.Push("Google");
stack.Push("Apple");
stack.Push("Microsoft");
Console.WriteLine("On top: " + stack.Peek());
while (stack.Count > 0)
{
    Console.WriteLine("Popped: " + stack.Pop());
}

Output

On top: Microsoft
Popped: Microsoft
Popped: Apple
Popped: Google

Try it

What is left to undo?

What will the program print?

Stack<string> undo = new Stack<string>();
undo.Push("font");
undo.Push("color");
undo.Push("size");
undo.Pop();
undo.Push("underline");
while (undo.Count > 0)
{
    Console.WriteLine(undo.Pop());
}

Answer

font
color
size

underline
color
font

underline
size
color
font

font
color
underline

Check

The idea

Queue: first come, first served

A queue is like the line at the checkout. You join at the back, and the first one is served. This is called FIFO: first in, first out.

Print jobs wait in a queue:

Queue<string> printer = new Queue<string>();
printer.Enqueue("invoice.pdf");
printer.Enqueue("contract.docx");
printer.Enqueue("photo.jpg");
Console.WriteLine("Next: " + printer.Peek());

while (printer.Count > 0)
{
    Console.WriteLine("Printing " + printer.Dequeue());
}
Console.WriteLine("Queue: " + printer.Count);

Output

Next: invoice.pdf
Printing invoice.pdf
Printing contract.docx
Printing photo.jpg
Queue: 0

• Enqueue puts at the back, Dequeue removes and returns the first one, and Peek looks at the first one.
• Queue<T> is in System.Collections.Generic. Count says how many are waiting, so the loop asks Count > 0.
• Dequeue and Peek on an empty queue stop the program. TryDequeue and TryPeek return false.

More precisely, if you are curious

• The empty queue:

Queue<string> clients = new Queue<string>();
clients.Enqueue("Customer 1");
Console.WriteLine("Served: " + clients.Dequeue());
if (!clients.TryDequeue(out string next))
{
    Console.WriteLine("Nobody is waiting.");
}
clients.Dequeue();

Error

Unhandled exception. System.InvalidOperationException: Queue empty.

TryDequeue says "Nobody is waiting.", and the last Dequeue stops the program.

• C# has no separate class for a queue with two ends. LinkedList<T> can add and remove at both ends, so older examples use it as a queue:

LinkedList<string> clients = new LinkedList<string>();
clients.AddLast("Customer 1");
clients.AddLast("Customer 2");
clients.AddFirst("Customer with an appointment");
Console.WriteLine("Served: " + clients.First.Value);
clients.RemoveFirst();
Console.WriteLine("Last: " + clients.Last.Value);
Console.WriteLine("Waiting: " + string.Join(", ", clients));

Output

Served: Customer with an appointment
Last: Customer 2
Waiting: Customer 1, Customer 2

• Queue<string> accepts null as an element too. You tell an empty queue by Count or by TryDequeue, not by null:

Queue<string> printer = new Queue<string>();
printer.Enqueue(null);
Console.WriteLine(printer.Count);

Output

1

Try it

Next at the checkout

The cashier calls the next customer. Which method takes them from the queue?

Queue<string> checkout = new Queue<string>();
checkout.Enqueue("Ivan");
checkout.Enqueue("Maria");
string next = checkout.();
Console.WriteLine("Your turn, " + next);

Check

See it

A linked list inside

List<T> keeps the elements next to each other in an array. That is why inserting at the front moves all the others. There is another way: each element is in a separate object that holds the value and an arrow to the next one. An object like this is called a node:

class Node
{
    public string Value;
    public Node Next;

    public Node(string value, Node next)
    {
        Value = value;
        Next = next;
    }
}

A list of nodes is called a linked list. It is enough to keep the first node, head. You find each next one by following the Next arrow. The last one points to null.

Node head = null;
head = new Node("Coffee", head);
head = new Node("Milk", head);
head = new Node("Bread", head);

for (Node n = head; n != null; n = n.Next)
{
    Console.WriteLine(n.Value);
}

Step by step, in words

1. The list is empty: head points to null.
2. A new node: Next is the old head (null), and head moves to the node.
3. The second node points to the first. Nothing moves in memory: only the arrows change.
4. The third node also goes in at the front: the last one added is first.
5. n starts at head and prints each node.
6. n reaches null: the loop stops.

• Inserting at the front: a new node whose Next points to the old first one, and head points to the new one. Two arrows, and you move nothing.
• Looping: you start at head and follow Next until you reach null.
• The cost: nodes have no indexes. You reach the fifth element by going through the first four.

The idea

LinkedList<T>, and which one when

C# has a ready-made linked list: LinkedList<T>. It adds at both ends with AddFirst and AddLast, removes by value with Remove, and gives you the first and the last node through First and Last:

LinkedList<string> route = new LinkedList<string>();
route.AddLast("Plovdiv");
route.AddLast("Stara Zagora");
route.AddFirst("Sofia");
route.AddLast("Burgas");
Console.WriteLine(string.Join(", ", route));

route.Remove("Stara Zagora");
Console.WriteLine("After the change: " + string.Join(", ", route));
Console.WriteLine("From " + route.First.Value + " to " + route.Last.Value);

Output

Sofia, Plovdiv, Stara Zagora, Burgas
After the change: Sofia, Plovdiv, Burgas
From Sofia to Burgas

LinkedList<T> has no indexes at all. You reach an element by number only through the nodes, so the compiler does not allow [ ]:

Console.WriteLine(route[1]);

Compile error

error CS0021: Cannot apply indexing with [] to an expression of type 'LinkedList<string>'

Which one when:

• A list by number: List<T>. This is the usual choice.
• A stack: Stack<T>. A queue: Queue<T>.
• LinkedList<T>: rarely. When you need both ends, or you often insert and remove next to a node you already have.

More precisely, if you are curious

• Why is LinkedList<T> usually slower, even at inserting? Each node is a separate object somewhere in memory, and the processor reads data fastest when it sits side by side. The array behind List<T>, Stack<T> and Queue<T> is exactly that.
• You can see the nodes of a LinkedList<T>: First is a LinkedListNode<string> with Value, Next and Previous. The arrows go both ways, so Last and RemoveLast are fast too:

LinkedList<string> route = new LinkedList<string>();
route.AddLast("Sofia");
route.AddLast("Plovdiv");
route.AddLast("Burgas");
LinkedListNode<string> second = route.First.Next;
Console.WriteLine(second.Value);
Console.WriteLine(second.Previous.Value + " <- " + second.Value + " -> " + second.Next.Value);
Console.WriteLine(route.Last.Next == null);

Output

Plovdiv
Sofia <- Plovdiv -> Burgas
True

• The node from the previous card has only Next. A list like that is called singly linked.

Try it

Find the bug

The method should count the nodes. For the list Bread → Milk → Coffee it returns 2 instead of 3. And for an empty list it stops with NullReferenceException. Which line has the bug?

Pick the line with the bug.

1static int Count(Node head)2{3 int count = 0;4 Node n = head;5 while (n.Next != null)6 {7 count++;8 n = n.Next;9 }10 return count;11}

Check

Exercise

Stacks and queues at work

Solve the tasks in your editor. The collection is a private field of the class.

1. A toy train. A Train class with the methods AddWagon(string wagon) and RemoveWagon(). The train is a stack: the last car coupled is the first one uncoupled. RemoveWagon() returns the uncoupled car, or null if there is none. Add a property Count. Couple three cars and uncouple two.

Output

Uncoupled: Car 3
Uncoupled: Car 2
Cars: 1

2. A bus route. A BusRoute class with a queue of stops and the methods AddStop(string stop) and GetNextStop(), which returns the next stop, or null if the route is over. Add "Central Station", "NDK" and "Studentski Grad", and go through the route.

Output

Next stop: Central Station
Next stop: NDK
Next stop: Studentski Grad
End of the route.

3. A stock ticker. A StockTicker class keeps the last N prices of one stock. The constructor gets the symbol and N. UpdatePrice(double price) adds a price, and if there are more than N prices, it removes the oldest one. Add GetLastPrice() and Average() for the stored prices. For SAP with N = 3, pass the prices 150, 152, 149 and 155. Hint: a Queue<T> sees only its first element, so keep the last price in a separate field. Print the prices with F2.

Output

SAP: last price €155.00
Average of the last 3: €152.00

4. Balanced brackets. A code editor checks whether the brackets (), [] and {} are closed in the right order. Write IsBalanced(string text) with a stack: at an opening bracket you put it on the stack, and at a closing one you remove the top one and check that it is the same kind. At the end the stack must be empty. Read three lines.

Input

(1 + [2 * 3])
(1 + 2]
((5)

Output

(1 + [2 * 3]) -> yes
(1 + 2] -> no
((5) -> no

5. Your own linked list. A MyLinkedList class with the nodes from the lesson and the methods Add(string value) (at the end), Remove(string value), Contains(string value), a property Count and ToString(). In Remove, find the node before the one you are looking for and redirect its Next. Check the case where the first one is removed separately.

Output

[Invoice, Report, Meeting]
Contains Report: True
After removal: [Invoice, Meeting]
Size: 2

More tasks

• Undo and Redo. Keep two stacks: undo and redo. A new action goes into undo and clears redo. "Undo" moves the top one from undo to redo, and "Redo" moves it back.
• Words in reverse. Read a sentence and print it with the words in reverse order, going through a stack: "Today is Friday" becomes "Friday is Today".
• Two checkouts. Customers come one by one and go to the checkout with the shorter line. Print who was served at which checkout.
• Reverse the linked list. Add a Reverse() method to MyLinkedList that turns the arrows around without making new nodes.

Test

Check yourself

1. You put A on a stack, then B, then C. Which comes out first at Pop?

CBA

2. Which one is a job for a queue?

Undoing the last actionThe "Back" button in the browserPrint jobs that are printed in the order they arrive

3. What happens at Dequeue() on an empty Queue<string>?

It returns empty textThe program stops with InvalidOperationExceptionIt returns null

4. Why is inserting at the start of a linked list fast?

Because the list sorts itselfBecause the elements sit next to each other in memoryBecause you make a new node and move two arrows, without touching the other elements

5. What is slow in a linked list?

Adding at the startGetting an element by its number, for example the five hundredthRemoving the first element

Check

Start the lesson over

Related lessons

• Builds on: Polymorphism · Interfaces · Exceptions · Lists
• Continues in: Hash codes and hash functions · Nested classes · Command · Space complexity
• Tasks on this topic: Collections