Short Notes: Stacks | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


STACKS
> A stack is a linear data structure like array with some restrictions.
> In a stack, insertion and deletion of elements is permitted only at one end. This end is 
called stack TOP.
> Because of this property, stack is also called Last-In-First-Out (LIFO) list.
> Insertion of element is called PUSH operation and deletion is called POP operation.
> A pictorial representation of stack insertion and deletion operation is as follows.
D
F F
T T T
U U U U
A A A A A
D
F F
T T T
U U U U
A A A A A
PUSH OPERATION POP OPERATION
> A stack can be represented using an array or a linked list.
> Since insertion and deletion is done at one end, we don’t need to traverse the entire list for 
these operations. So stack supports insertion and deletion in O(1) time i.e. in constant 
amount of time.
> When stack is empty, if we try to remove an element, it is called “Stack underflow”.
> Similarly, when we add an element to a stack which is full, it is called “Stack overflow”.
> A stack can theoretically grow to an infinite size. But in practice, there is limit. For array 
representation, the limit is array size whereas for linked list representation it is the amount 
of available memory.
Page 2


STACKS
> A stack is a linear data structure like array with some restrictions.
> In a stack, insertion and deletion of elements is permitted only at one end. This end is 
called stack TOP.
> Because of this property, stack is also called Last-In-First-Out (LIFO) list.
> Insertion of element is called PUSH operation and deletion is called POP operation.
> A pictorial representation of stack insertion and deletion operation is as follows.
D
F F
T T T
U U U U
A A A A A
D
F F
T T T
U U U U
A A A A A
PUSH OPERATION POP OPERATION
> A stack can be represented using an array or a linked list.
> Since insertion and deletion is done at one end, we don’t need to traverse the entire list for 
these operations. So stack supports insertion and deletion in O(1) time i.e. in constant 
amount of time.
> When stack is empty, if we try to remove an element, it is called “Stack underflow”.
> Similarly, when we add an element to a stack which is full, it is called “Stack overflow”.
> A stack can theoretically grow to an infinite size. But in practice, there is limit. For array 
representation, the limit is array size whereas for linked list representation it is the amount 
of available memory.
Application of Stack
> A stack is useful for converting an arithmetic expression into Polish and reverse-Polish 
notation.
> In any programming language, each arithmetic operator has a priority. An expression can 
be evaluated based on that priority. But still, it is difficult to evaluate an expression in a 
computer.
> Polish mathematician Jan Lukasiewicz gave two methods of representing an arithmetic 
expression called pre-fix notation (aka Polish notation) and post-fix notation (aka reverse- 
Polish notation). The general arithmetic expression are said to be in in-fix form.
> In pre-fix and post-fix notations, the expressions are represented in such a way that the 
operator appears before or after the operands. As a result, no parenthesis are required to 
find which part is to be evaluated first.
> Consider the expression
a+b*c
This is to be evaluated as 
(a+(b*c))
The pre-fix notation of it is 
+a*bc
And post-fix notation is 
abc*+
> Now, the expressions can be evaluated using a stack.
> For evaluation of pre-fix operation, we scan the expression and push it in a stack one 
element at a time. Whenever we encounter two operands, we pop the two operands and 
the operator just beneath it and evaluate that part with the operator. The result is then 
pushed to the stack. The process continues till stack is not empty.
> Similarly for post-fix operation, we scan the expression and push it in a stack one element 
at a time. Whenever we encounter an operator, we pop the operator and the two operands 
just beneath it and evaluate that part with the operator. The result is then pushed to the 
stack. The process continues till stack is not empty.
> For +a*bc, + is pushed followed by a and then * and then b and then c. When c is pushed, 
we have two operands b and c together. It is evaluated with operator *. Let the result be D. 
When D is pushed, the structure of the stack is +aD. Now a and D are two operands 
together and are evaluated with +. When plus is popped, the process stops as stack is now 
empty. The result a+D is the final result.