A stack in Python is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure – elements can be added and removed from the stack only at the top. Here is a structural definition of a Stack: a stack is either empty or it consists of a top and the rest which is a Stack.
Creating a Stack class with a List Object
Using a list object you can create a fully functional generic Stack with helper methods such as peeking and checking if the stack is Empty. Check out the official python docs for using list as Stack here.
define a stack class
class Stack:
def init(self):
self.items = []
method to check the stack is empty or not
def isEmpty(self):
return self.items == []
method for pushing an item
def push(self, item):
self.items.append(item)
method for popping an item
def pop(self):
return self.items.pop()
check what item is on top of the stack without removing it def peek(self):
return self.items[-1]
method to get the size
def size(self):
return len(self.items)
to view the entire stack
def fullStack(self):
return self.items
An example run:
stack = Stack()
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
print('Pushing integer 1')
stack.push(1)
print('Pushing string "Told you, I am generic stack!"')
stack.push('Told you, I am generic stack!')
print('Pushing integer 3')
stack.push(3)
print('Current stack:', stack.fullStack())
print('Popped item:', stack.pop())
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
Output:
Current stack: []
Stack empty?: True
Pushing integer 1
Pushing string "Told you, I am generic stack!"
Pushing integer 3
Current stack: [1, 'Told you, I am generic stack!', 3]
Popped item: 3
Current stack: [1, 'Told you, I am generic stack!']
Stack empty?: False
Stack in Python: Parsing Parentheses
Stacks are often used for parsing. A simple parsing task is to check whether a string of parentheses are matching.
For example, the string ([]) is matching, because the outer and inner brackets form pairs. ()<>) is not matching, because the last ) has no partner. ([)] is also not matching, because pairs must be either entirely inside or outside other pairs.
def checkParenth(str):
stack = Stack()
pushChars, popChars = "<({[", ">)}]"
for c in str:
if c in pushChars:
stack.push(c)
elif c in popChars:
if stack.isEmpty():
return False
else:
stackTop = stack.pop()
Checks to see whether the opening bracket matches the closing one balancingBracket = pushChars[popChars.index(c)]
if stackTop != balancingBracket: return False
else:
return False
return not stack.isEmpty()