A Stack in Python

A stack is an ordered collection which offers two operations: ‘push,’ adding an item to the stack, and ‘pop,’ to remove and return an item. ‘Pop’ will return the most-recently-pushed item which has not been previously popped. The physical analog is a stack of plates like the one you might find in your kitchen cabinets: supposing you are only strong enough to handle one plate at a time, you’ll always add (‘push’) a plate onto the top of the stack, or remove (‘pop’) the last plate you pushed.

stack

Those are the only two operations you get. It can be counterintuitive, but limiting what you’re able to do with the collection like this is pretty useful. Your web browser two stacks for your ‘back’ and ‘forward’ buttons, popping a page or URL from the from the ‘back’ stack and pushing the current page onto the ‘forward’ stack when you hit the ‘back’ button (or vice-versa). Your computer’s memory contains a ‘call stack’ for every application, which keeps track of the subroutine that application is currently executing. This allows us to call subroutines from other subroutines and return to the point where we left off.

Internally, stacks are usually built on top of lists, either array lists or linked lists. In fact, my linked list from the original post is already a stack, but with the ‘push’ and ‘pop’ operations named ‘insert’ and ‘delete.’ The difference is that a full-featured linked list would probably have some functionality to insert and delete at the tail or perhaps at an arbitrary position in the list, whereas a stack shouldn’t (if it does, it’s not a stack any more).

Since we’ve already implemented a linked list, I’ll take Python’s built-in list structure for granted, and just implement the stack on top of it:

This gives the expected output:

Now, even the casual observer will note that I made this a little more difficult than it could’ve been. Python’s lists already define a “pop,” but using that would’ve been silly.

In a real setting, we’d probably want to implement a ‘peek’ method, which would allow us to get the item atop the stack without popping it. With this toy example, we’d have to pop the item, use it, and push it back onto the stack. We might also want an isEmpty method, or a more graceful behavior when we try to pop from an empty stack (right now, we get a “list index out of range” error).