Stack Implementation Using a List

Hello students, welcome to Kwickprep. When you press undo, why does the last change disappear first, and not the first one? Because undo uses a stack. Today we build a stack with a Python list, with push, pop, peek and isEmpty, and we handle overflow and underflow.

Think of a stack of plates at a wedding buffet. Every washed plate is placed on the top of the pile. When a guest takes a plate, they take the top one first. So the last plate placed is the first plate taken. This rule is called LIFO, which stands for Last In, First Out.

In a stack, adding an item is called push, and removing an item is called pop. We push a red plate, so red is on top. Then we push blue, and blue becomes the top. We push green, and green is now the top. The first pop removes green, the last plate in. The next pop removes blue, leaving only red.

A Python list can act as a stack if we treat its end as the top. Push means adding on top, and append adds at the end. Pop removes the top item, and the list method pop removes the last item. Peek means just looking at the top item without removing it, and index minus one gives the last item. IsEmpty checks if the stack has nothing, so the length is zero.

Let us write each operation as a function, the way exams ask. The list stk is our stack. IsEmpty returns True when the length of stk double equals zero, and False otherwise. Push takes the stack and an item, and append puts the item on top.

Before pop and peek, we must learn two error conditions. Underflow happens when we pop or peek on an empty stack, because there is nothing to take. Overflow happens when we push onto a stack that is already full. A Python list grows by itself, so overflow happens only when we set a size limit. So a good program checks the stack before every pop, peek and push.

Pop first checks for underflow. If the stack is empty, it returns the message Underflow instead of crashing. Otherwise the list method pop removes and returns the top item. Peek does the same check, but returns stk of minus one without removing it. Without this check, popping an empty list gives IndexError.

Here is the plate example in code. We push red, blue and green, one by one. Peeking with index minus one shows green, the top. Two pops remove green first, then blue. Only red is left in the stack. Pause and predict. What would a third and fourth pop give with our safe pop function? Red, and then Underflow.

This is the improved push, and it replaces the simple one we wrote earlier. To show overflow, we give the stack a fixed size of three. The name size, written in capitals, is a constant, a value we do not change. Before appending, push checks if the length already equals size. If it does, the stack is full, so it returns Overflow. Otherwise it appends the item and returns Pushed.

Exams also ask for a display function. A stack is shown from the top down, so we loop backwards. The range starts at the last index and goes down to zero, one step at a time. So the output is green, then blue, then red.

Stacks are used in many places around you. In a text editor, every change is pushed, and undo pops the latest change. A browser pushes each page you open, and the back button pops the latest one. Pushing characters and popping them out reverses a string. Python itself uses a stack to track which function called which.

Here is undo in a document. We type Hi, then make it bold, then make it red. Each step is pushed onto the undo stack. The first undo pops red, the latest change. The second undo pops bold. Typing Hi is still safe at the bottom.

Now let us reverse a string with a stack. We push every character, ch, of the word onto the stack. Then, while the stack is not empty, we pop a character and add it to rev. The last letter comes out first, so the word comes out backwards. Kajal becomes Lajak.

Avoid these four common mistakes. Pop of zero removes the first item, which is the bottom, so that breaks LIFO. Popping without checking gives IndexError on an empty stack. For peek, stk of zero is the bottom, so use stk of minus one. And a pop function should return the item it removed.

Let us revise what we learned today. A stack is Last In, First Out, like a pile of plates. Push uses append, pop uses pop, and peek uses index minus one. IsEmpty checks whether the length is zero. Underflow means the stack is empty, and overflow means a fixed size stack is full. Stacks power undo, the back button and string reversal.