Scribd
Upload
12 views12 pages

Understanding Stack Data Structure

A stack is a linear data structure that allows insertion (PUSH) and deletion (POP) of elements at one end, following a Last-In-First-Out (LIFO) order. The document outlines the representation of a stack using a TOP pointer to track the top element, along with algorithms for inserting, deleting, peeping, and changing values in the stack. Additionally, it mentions applications of stacks such as reversing strings, checking palindromes, converting decimal to binary, recursion, and expression evaluation.

Uploaded by

henilbhadani94267
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views12 pages

Understanding Stack Data Structure

A stack is a linear data structure that allows insertion (PUSH) and deletion (POP) of elements at one end, following a Last-In-First-Out (LIFO) order. The document outlines the representation of a stack using a TOP pointer to track the top element, along with algorithms for inserting, deleting, peeping, and changing values in the stack. Additionally, it mentions applications of stacks such as reversing strings, checking palindromes, converting decimal to binary, recursion, and expression evaluation.

Uploaded by

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

Linear Data structures

-Stack
Prof. Vasundhara Uchhula
Stack
It permits insertion and deletion of an element to occur at
only one end.
Insertion operation is called PUSH
Deletion operation is called POP
Since insertion and deletion operations are performed at one
end of stack, the elements can be only removed in the
opposite order from that in which they were added to the
Stack
Such a linear list is called as LIFO List (Last-In-First-Out)
Ex: Piles of trays in a cafeteria
Stack Representation
TOP Pointer
TOP is a pointer that keeps track of the
top element of the stack.
When stack is empty TOP=0
When there is one element TOP=1 and
so on
When element is removed from stack,
TOP is decremented by one
N: Size of stack
Example
Algorithm for inserting element in a
stack
Procedure PUSH( S, TOP, X)
S Stack
TOP pointer to the top of the stack
X is element to insert
1. [ Check for stack overflow ]
If TOP >= N
then Write(‘ Stack Overflow’)
Return
2. [Increment TOP]
TOP ← TOP + 1
3. [ Insert Element]
S[TOP] ← X
4. [Finished]
Return
Algorithm for deleting element from a
stack
Function POP( S, TOP)
S Stack
TOP pointer to the top of the stack
1. [ Check for stack underflow ]
If TOP = 0
then Write(‘ Stack Underflow’)
Exit
2. [Decrement TOP pointer]

TOP ← TOP - 1
3. [Return former top element of stack]
Return S[TOP +1]
4. [Finished]
Return
Algorithm for PEEPING into a stack
– Returns Ith value from TOP of the stack

Function PEEP( S, TOP, I)

1. [ Check for stack underflow ]


If TOP-I+1 <= 0
then Write(‘ Stack Underflow on PEEP’)
Exit
2. [Return Ith element from top of stack]
Return (S[TOP-I +1])
Algorithm for Changing value in a stack
This procedure changes the value of the Ith element from the top of the stack to
the value X

Procedure CHANGE( S, TOP, X, I)


[ Check for stack underflow ]
If TOP-I+1 <= 0
then Write(‘ Stack Underflow on CHANGE)
Exit
1. [Change Ith element from top of stack]
S[TOP-I +1] ← X
2. [Finished]
Return
APPLICATIONS of STACK
Let us consider a simple examples of
1) reversing a string
2) Palindrome
3) Convert a decimal number to binary
representation
4) Recursion
5) Expressions

You might also like