STACKS & Queue
A Stack is linear data structure. A stack is a list of elements in which an element may be inserted or deleted only at one end, called the top of the stack. Stack principle is LIFO (last in, first out). Which element inserted last on to the stack that element deleted first from the stack.
As the items can be added or removed only from the top i.e. the last item to be added to a stack is the first item to be removed.
Operations on stack:
The two basic operations associated with stacks are: 1. Push 2. Pop
While performing push and pop operations the following test must be conducted on the stack.
a) Stack is empty or not
b) stack is full or not
1. Push: Push operation is used to add new elements in to the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow".
2. Pop: Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".
All insertions and deletions take place at the same end, so the last element added to the stack will be the first element removed from the stack. When a stack is created, the stack base remains fixed while the stack top changes as elements are added and removed. The most accessible element is the top and the least accessible element is the bottom of the stack.
Representation of Stack (or) Implementation of stack:
The stack should be represented in two ways:
1. Stack using array 2. Stack using linked list
1. Stack using array: Let us consider a stack with 6 elements capacity. This is called as the size of the stack. The number of elements to be added should not exceed the maximum size of the stack. If we attempt to add new element beyond the maximum size, we will encounter a stack overflow condition. Similarly, you cannot remove elements beyond the base of the stack. If such is the case, we will reach a stack underflow condition.
1.push():When an element is added to a stack, the operation is performed by push(). Below Figure shows the creation of a stack and addition of elements using push()
Initially top=-1, we can insert an element in to the stack, increment the top value i.e top=top+1. We can insert an element in to the stack first check the condition is stack is full or not. i.e top>=size-1. Otherwise add the element in to the stack.
2.Pop(): When an element is taken off from the stack, the operation is performed by pop(). Below figure shows a stack initially with three elements and shows the deletion of elements using pop().
We can insert an element from the stack, decrement the top value i.e top=top-1. We can delete an element from the stack first check the condition is stack is empty or not. i.e top==-1. Otherwise remove the element from the stack.
3.display(): This operation performed display the elements in the stack. We display the element in the stack check the condition is stack is empty or not i.e top==-1.Otherwise display the list of elements in the stack.
2. Stack using Linked List: We can represent a stack as a linked list. In a stack push and pop operations are performed at one end called top. We can perform similar operations at one end of list using top pointer. The linked stack looks as shown in figure.
Applications of stack:
1. Stack is used by compilers to check for balancing of parentheses, brackets and braces.
2. Stack is used to evaluate a postfix expression.
3. Stack is used to convert an infix expression into postfix/prefix form.
4. In recursion, all intermediate arguments and return values are stored on the processor’s stack.
5. During a function call the return address and arguments are pushed onto a stack and on return they are popped off.
Converting and evaluating Algebraic expressions: An algebraic expression is a legal combination of operators and operands. Operand is the quantity on which a mathematical operation is performed. Operand may be a variable like x, y, z or a constant like 5, 4, 6 etc. Operator is a symbol which signifies a mathematical or logical operation between the operands.
Examples of familiar operators include +, -, *, /, ^ etc. 13 An algebraic expression can be represented using three different notations.
They are infix, postfix and prefix notations:
Infix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator in between the two operands.
Example: A + B
Prefix: It is the form of an arithmetic notation in which we fix (place) the arithmetic operator before (pre) its two operands. The prefix notation is called as polish notation.
Example: + A B
Postfix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator after (post) its two operands. The postfix notation is called as suffix notation and is also referred to reverse polish notation.
Example: A B +
Conversion from infix to postfix: Procedure to convert from infix expression to postfix expression is as follows:
1. Scan the infix expression from left to right.
2. a) If the scanned symbol is left parenthesis, push it onto the stack.
b) If the scanned symbol is an operand, then place directly in the postfix expression (output).
c) If the symbol scanned is a right parenthesis, then go on popping all the items from the stack and place them in the postfix expression till we get the matching left parenthesis.
d) If the scanned symbol is an operator, then go on removing all the operators from the stack and place them in the postfix expression, if and only if the precedence of the operator which is on the top of the stack is greater than (or greater than or equal) to the precedence of the scanned operator and push the scanned operator onto the stack otherwise, push the scanned operator onto the stack.
The three important features of postfix expression are:
1. The operands maintain the same order as in the equivalent infix expression.
2. The parentheses are not needed to designate the expression unambiguously.
3. While evaluating the postfix expression the priority of the operators is no longer relevant.
We consider five binary operations: +, -, *, / and $ or ↑ (exponentiation). For these binary operations, the following in the order of precedence (highest to lowest)
Download PDF Notes