A stack adds and removes elements at one end. Its last-in, first-out (LIFO) rule means the most recently added element comes out first: add 3, 4, 6, then 8, and 8 is removed first. section 1.4.3
The top of the stack is the only place to work:
- Push adds an element. section 1.4.3
- Pop removes and returns the top element. section 1.4.3
- Peek checks the top element without removing it. section 1.4.3
- Push and pop take O(1) time; storing N elements takes O(N) space. section 1.4.3
This restriction fits function calls: each call places its parameters and local variables on the stack; when it finishes, it is removed and control returns to its caller. Recursion can keep adding calls, leading to stack overflow. Undo and redo are other uses. section 1.4.3
Figure 1.6 The stack data structure is Last In First Out(LIFO). Illustration of a stack with three numbers. The number 8 was inserted last and it will be popped first. The number 4 was inserted first, it will be popped only when all the numbers above the stack are popped first.
Trace how adding 3, 4, and 8 makes 8 the first element removed, while 4 stays beneath the others. section 1.4.3
Listing 1.3 Code implementation of a stack
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Pop from empty stack")
return self.items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Peek from empty stack")
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
See a Python implementation using a list, with empty-stack checks for pop and peek. section 1.4.3
















