A stack is a pile of objects placed one atop another (for example, a stack of books, a stack of clothes, or a stack of papers). There are two stacking operations: one for adding items to a stack, and one for removing items from a stack.
The operation used for adding items to a stack is called push, while the operation used for removing items is called as pop. Items are popped in the reverse order to push; that is why this data structure is called last-in first-out (LIFO).
Let's experiment with the stack data structure in Python. We'll be using the list data structure as a stack in Python. We'll use the append() method to push items to the stack and the pop() method to pop them out:
...
stack = []
print "stack", stack
#add items to the stack
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
print "stack", stack
#pop all the items out
while len(stack) > 0:
item = stack.pop()
print item
print "stack", stack
...
As shown in the preceding code, we have created an empty stack and we are printing it out. One by one, we are adding the numbers 1, 2, 3, and 4 to the stack and printing them out. Then, one by one, we are popping the items and printing them out; finally, we are printing the remaining stack.
If we execute the preceding code, Stack.py, we get the following output:
Initially, we have an empty stack, and when items 1, 2, 3, and 4 are pushed to the stack, we have 4 at the top of the stack. Now, when you pop the items out, the first one to come out is 4, then 3, then 2, and then 1; this is the reverse of the order of entry. Then, finally, we have an empty stack.
Now that we are clear on how stacks work, let's use these concepts to actually create a DFS algorithm.
