Stack

Definition

Stack: Abstract data type with the following

operations:

Push(key): adds key to collection

Key Top(): returns most recently added key

Key Pop() : removes and returns most recently-added key

Boolean Empty(): are there any elements

Balanced Bracket

Input: A string str consisting of ‘(’,‘)’, ’[‘,’]’ characters

Output: Return whether or not the string’s parentheses and square brackets are balanced

IsBalanced(str)
    Stack stack
    for char in str:
	if char in ['(','[']:
		stack.Push(char)
    else:
        if stack.Empty():return false
        top <- stack.Pop()
        if(top = '[' and char != ']' )or (top = '(' and char != ')'):
			return false;
return stack.Empty()

          

Summary:

• Stacks can be implenmented with either an array or a linked list
• Each stack operation is O(1): Push, Pop, Top, Empty
• Stacks are occasionally known as LIFO queues