SME
Data Structures & Algorithms
Lists, stacks and queues
Use this for “After push 3, push 5, push 2, pop, what is on top?”
Explore
Each push goes on top, so 2, pushed last, is on top and 3 is at the bottom.
Assumptions
•
A stack takes from the end it added to; a queue takes from the other end.
•
Each push, pop, enqueue or dequeue is constant time: no other item moves.
•
A circular queue of N slots reuses them: after slot N − 1 comes slot 0.
•
A linked list’s nodes each point to the next; the last points to nothing (∅).
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Circular queue indices
Use this for “A circular queue has 8 slots, its front at slot 6 and 4 items. Where is the last item, and where does the next one go?”
Address of an array element
Use this for “A two-dimensional array of 8-byte numbers starts at address 2000 and has 10 columns. Where is element (3, 4)?”
Cost of a growing array
Use this for “An array starts with 1 slot and doubles when full. How many items are copied while 1000 are pushed?”
Evaluate a postfix expression
Use this for “Evaluate the postfix expression 3 4 + 2 × 7 − with a stack.”