STACKS :
General Representation
and Operations
Kiranpal Singh Virk
Assistant Professor, Guru Nanak Khalsa College
Yamuna Nagar
(kiranpal.virk@yahoo.com)
TOPICS
• Introduction
• Representation
– Arrays
– Linked List
• Operations
PUSH operation
POP operation
STACK
• Generally speaking:
– “a neat pile of objects”
– “rectangular or cylindrical pile of hay,
straw etc”
BOOK STACK
FOOD STACK
CD STACK
STACK
• A stack is an ordered collection of items into
which new items may be inserted and from
which items may be deleted at one end,
called the top of the stack
STACK
• A stack is a linear data structure which
satisfies the following properties at any time:
– Allocations and de-allocations are performed in
a last-in-first-out (LIFO) manner.
– i.e. amongst all existing entries at any time, the
last entry to have been allocated is the first
entry to be de-allocated
– only the last entry is accessible
STACK
STACK
Last-in First-Out
IN OUT
3 2 1
STACK
Last-in First-Out
IN OUT
1 2 3
STACK
Last-in First-Out
IN OUT
1 2 3
STACK APPLICATIONS
• Applications of Stacks
– Page-visited history in a Web browser
– Undo sequence in a text editor
– Saving local variables when one function calls
another, and this one calls another, and so on.
REPRESENTATION OF
STACK
• Stack can be represented in computer in the
following two ways:
– Array Representation
– Linked Representation
ARRAY-BASED STACK
• A simple way of implementing the Stack
uses an array
• A variable TOP contains the location of the
top element of the stack
TOP
S …..
ARRAY-BASED STACK
n
n-1
“a stack is an ordered collection of items …..
into which new items may be inserted and …..
from which items may be deleted at one
top D 4
of the stack”
end, called the toptop
C 3
B 2
A B C D
A 1
1 2 3 4 ….. ….. n-1 n
ARRAY-BASED STACK
top H
top G G
top F F F
top E E E E
top D D D D D
C C C C C
B B B B B
A A A A A
(a) (b) (c) (d) (e)
ARRAY-BASED STACK
top H
G top G
F F top F
E E E top E
D D D D top D
C C C C C
B B B B B
A A A A A
(e) (f) (g) (h) (i)
ARRAY-BASED STACK
H
G G G
F F F F F
top E E E E E E E
D D D D D D D D D
C C C C C C C C C
B B B B B B B B B
A A A A A A A A A
(a) (b) (c) (d) (e) (f) (g) (h) (i)
ARRAY-BASED STACK
E
top D
C
B
A
ARRAY-BASED STACK
F
top E
D
C
B
A
ARRAY-BASED STACK
G
top F
E
D
C
B
A
ARRAY-BASED STACK
H
top G
F
E
D
C
B
A
ARRAY-BASED STACK
• A variable MAXSTK which gives the
maximum number of elements that can be
held by the stack
TOP MAXSTK
S …..
ARRAY-BASED STACK
• The condition TOP=0 or TOP=NULL
indicates that the stack is empty.
TOP=NULL
MAXSTK
STACK
1 2 3 4 5 6 7 8
ARRAY-BASED STACK
• The condition TOP=MAXSTK indicates that
stack is full.
TOP MAXSTK
STACK A B C D E F G H
1 2 3 4 5 6 7 8
ARRAY-BASED STACK
• MAXSTK=8
• TOP=4
• 4 more items can be added on the stack
TOP MAXSTK
STACK A B C D
1 2 3 4 5 6 7 8
OPERATIONS ON
STACK
• Two basic operations on stacks
– PUSH is the term used to insert an
element into stack
– POP is the term used to delete an
element from a stack
PUSH OPERATION
• Before executing the PUSH operation, one
must test if there is a room in the stack for
new item or not
• Stack-full condition is called “overflow”
TOP MAXSTK
STACK A B C D
1 2 3 4 5 6 7 8
PUSH OPERATION
PUSH(STACK, TOP, MAXSTK, ITEM)
This procedure pushes an ITEM onto a stack
(1) If TOP = MAXSTR, then: Print: OVERFLOW,
and Return [stack already filled ?]
(2) Set TOP = TOP+1 [increases TOP by 1]
(3) Set STACK[TOP] = ITEM [Inserts ITEM in new
TOP position]
(4) Return
START PUSH OPERATION
IF TOP = YES PRINT
MAXSTR “OVERFLOW”
NO
TOP = TOP + 1
STACK[TOP] = ITEM
STOP
START PUSH OPERATION
IF TOP = YES PRINT
MAXSTR “OVERFLOW”
NO
TOP = TOP + 1
STACK[TOP] = ITEM
STOP
POP OPERATION
• Before executing the POP operation, one
must test whether there is an element in the
stack to be deleted or not
• Empty stack condition is called “underflow”
TOP MAXSTK
STACK A B C D
1 2 3 4 5 6 7 8
POP OPERATION
POP(STACK, TOP, ITEM)
This procedure deletes the top element of stack and
assigns it to the variable ITEM
(1) If TOP = 0, then: Print: UNDERFLOW, and
Return [stack empty ?]
(2) Set ITEM = STACK[TOP] [Assign TOP
element to ITEM]
(3) Set TOP = TOP-1 [Decreases TOP by 1]
(4) Return
START POP OPERATION
YES PRINT
IF TOP = 0
“UNDERFLOW”
NO
ITEM = STACK[TOP]
TOP = TOP - 1
STOP
START POP OPERATION
YES PRINT
IF TOP = 0
“UNDERFLOW”
NO
ITEM = STACK[TOP]
TOP = TOP - 1
STOP
LIMITATIONS OF
ARRAY-BASED STACK
• The maximum size of the stack must be
defined a priori , and cannot be changed
• Trying to push a new element into a full
stack causes an implementation-specific
exception
LINKED LIST BASED
STACK
TOP •
3 2 1
• • X
PUSH OPERATION
LINKED LIST BASED
STACK
TOP •
4 3 2 1
• • • X
PUSH OPERATION
LINKED LIST BASED
STACK
TOP •
4 3 2 1
• • • X
POP OPERATION
LINKED LIST BASED
STACK
TOP •
3 2 1
• • X
POP OPERATION
main( ) FUNCTION
{ CALL STACK
int a = 5, b = 2, c ;
c = add ( a, b ) ;
when call
printf ( "sum = %d", c ) ;
to add() is
} met
add ( int i, int j )
{
int sum ;
sum = i + j ;
return sum ; 5 copy of a
} 2 copy of b
main( ) FUNCTION
{ CALL STACK
int a = 5, b = 2, c ;
c = add ( a, b ) ;
printf ( "sum = %d", c ) ; before
transferring
} control to
add ( int i, int j ) add()
{
int sum ;
sum = i + j ; xxx address of printf()
return sum ; 5 copy of a
} 2 copy of b
main( ) FUNCTION
{ CALL STACK
int a = 5, b = 2, c ;
c = add ( a, b ) ;
after control
printf ( "sum = %d", c ) ;
reaches add()
}
add ( int i, int j )
{
int sum ; 7 copy of sum
sum = i + j ; xxx address of printf()
return sum ; 5 copy of a
} 2 copy of b
main( ) FUNCTION
{ CALL STACK
int a = 5, b = 2, c ;
c = add ( a, b ) ;
printf ( "sum = %d", c ) ; while
returning
} control from
add ( int i, int j ) add()
{
int sum ;
sum = i + j ; xxx address of printf()
return sum ; 5 copy of a
} 2 copy of b
main( ) FUNCTION
{ CALL STACK
int a = 5, b = 2, c ;
c = add ( a, b ) ;
on returning
printf ( "sum = %d", c ) ;
control from
} add()
add ( int i, int j )
{
int sum ;
sum = i + j ;
return sum ;
}
SUGGESTED READING
• BOOKS:
– A.M. Tenenbaum, “Data Structures using C”,
Prentice Hall
– S. Lipschutz, “Theory and Problems of Data
Structures”, McGraw Hill
• ONLINE RESOURCES
– Microsoft MSDN library
Thank You
