Can I access the middle element of a stack or queue?

No. By definition, these data structures only allow access to one end (the top of the stack, or the front of the queue). To reach a middle element, you must remove the elements blocking it.

What happens if I try to remove an item from an empty stack or queue?

This results in a specific type of error called an 'underflow'. In most programming languages, you should check if the stack or queue is empty before trying to remove an item.

Are stacks and queues just arrays?

They are abstract concepts (Abstract Data Types), not specific physical implementations. You can build a stack or a queue using an array, but you can also build them using a linked list.

What is a stack versus a queue?

A stack and a queue are both linear data structures used to store collections of items, but they differ completely in the order items are added and removed. In a stack, the last item you add is the first one you take out. In a queue, the first item you add is the first one you take out.

Think of a stack like a pile of plates in a cafeteria: you add plates to the top and take them off the top. Think of a queue like a line of people waiting at a checkout: the first person to get in line is the first person served.

The Stack: Last-In, First-Out (LIFO)

A stack operates on the LIFO principle. The most recently added item is the first one removed. The two main operations are 'push' (adding an item to the top) and 'pop' (removing the item from the top). A great real-world example in computer science is the 'Undo' button in your word processor. The last action you took is the first one undone when you press Ctrl+Z.

The Queue: First-In, First-Out (FIFO)

A queue operates on the FIFO principle. The oldest item in the collection is the first one removed. Its main operations are 'enqueue' (adding an item to the back) and 'dequeue' (removing an item from the front). A common computer science example is a printer queue. If three people send documents to a printer, the printer prints the first document received before moving to the second.

Where students slip up

Students often forget that stacks and queues strictly restrict access. Unlike a standard array or list where you can grab an item from the middle at any time, a stack only lets you see or remove the very top item. A queue only lets you see or remove the very front item. If you need to search for a specific item in the middle of a stack or queue, you have to remove all the items in front of it first.

Worked through

Imagine you have an empty stack and an empty queue. You add the numbers 1, 2, and 3 to both data structures in that exact order. If you perform one removal operation on both, what number do you get from the stack, and what number do you get from the queue?

For the stack: You 'push' 1, then 2, then 3. The number 3 is now at the top of the stack. When you 'pop' one item, you get the number 3.

For the queue: You 'enqueue' 1, then 2, then 3. The number 1 is at the front of the line. When you 'dequeue' one item, you get the number 1.

Questions students ask

Ask about this topic

Explain at

Where this comes from: Introduction to Algorithms by Thomas H. Cormen et al. · Khan Academy: Computer Science Algorithms · OpenStax: Introduction to Python Programming