Scribd
Upload
7 views

Week3 - Data Structure (Stack)

Uploaded by

Krishanu Ghosh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
7 views

Week3 - Data Structure (Stack)

Uploaded by

Krishanu Ghosh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 15

Data Structure (Stack)

Dr. Rajendrani Mukherjee


Abstract Data Type (ADT)
 Stack is an abstract data type.

 ADT (Abstract Data Type) is a mathematical


model for data types.

 An ADT may be defined as - class of objects


whose logical behavior is defined by a set of
values and a set of operations.
Stack History
 The idea of Stack was first proposed by
Samelson and Bauer in 1955.

 A stack can easily be implemented using an


array or linked list.

 Some languages (Python, Ruby etc.) have


available push, pop operations.
Stack
 Stack is an ADT . It is a collection of elements
with two main operations –

 Push (for adding elements)


 Pop (for removing the recently added element)

 Stack follows LIFO (Last In First Out).

 Stack is a linear data structure.


LIFO
Stack Top
 Stack is a linear data structure.

 Push and pop occur only at one end of the


Stack. This is referred as top of the stack.

 The Pop operation removes an item from the


top of the stack.
Stack Pointer
 A stack pointer points to the most recently
accessed location on the stack.

 The stack pointer points to the origin of the


stack when the stack has a size of zero.
Stack Overflow and Underflow
 When the stack is full, then it is said to be an
Overflow condition.

 When the stack is empty, then it is said to be


an Underflow condition.

 isFull() − check if stack is full.


 isEmpty() − check if stack is empty.
Push Operation
 The process of putting a new element into
stack is called Push Operation.
 First it is checked whether the stack is full or

not.
 If the stack is full then exit.
 If the stack is not full, the stack top is

incremented to point to the next empty


space.
 The data element gets added to the stack

location where top is pointing.


Pop Operation
 First it is checked whether the stack is empty
or not.
 If the stack is empty, exit.
 If the stack is not empty, then the data

element at which stack top is pointing is


accessed.
 The stack top value is decreased by 1.
Push and Pop Operation
Applications of Stack

 Expression Parsing ( Infix to Postfix/Prefix


Conversion)
 Stack based memory allocation
 String Reversal
 Tower of Hanoi Algorithm
Expression Parsing

Notations are named as how they use operator


in expression.

 Infix Notation
 Prefix Notation
 Postfix Notation
Infix

Operators are used in-between operands.


 a+b
 (a + b) ∗ c
 (a + b) ∗ (c + d)

Prefix
 Operator is prefixed to operands ( operator is written

before operands).

 +ab
 ∗+abc
 ∗+ab+cd
Postfix

The operator is postfixed to the operands (the


operator is written after the operands).

 ab+c∗
 ab+cd+∗

You might also like