|
|
. |
|
C
For Swimmers : Mastering C step-by-step |
|
|
|
About
Stacks
|
|
Definition :
Lists permit the insertion or deletion of an element to occur only at one
end. A linear list belonging to this subclass is called a
stack. They are also referred to as
pushdown lists.
The insertion operation is referred to as
PUSH and the deletion operation as
POP. The most accessible element in a stack is known as the
TOP of the stack.
Since insertion and deletion operations are performed at one end of stack, the elements can only be removed in the opposite order from that in which they were added to the stack. Such a linear list is frequently referred to as a
LIFO ( Last-In First-Out ) LIST.
An example of stack is the in tray of a busy executive. The files pile up in the tray and whenever the executive has time to clear the files, he/she takes it off from the top. That is, files are added at the top and removed from the top. Therefore stacks are sometimes referred to as
LIFO structure.
A pointer TOP
A pointer TOP keeps track of the top element in the
stack. Initially when the stack is empty, TOP has a value of 1 and when the stack contains a single element, TOP has a value of 0 ( Zero ) and so on. Each time a new element is inserted in the stack, the pointer is incremented by 1. The pointer decrements by 1 each time a deletion is made from the stack.
STACK STRUCTURE
D = { d , F , A }
Where,
d : Array or a node (structure)
d = { a , TOP }
Here, a : Simple array or structure
TOP : Index or Pointer
F : PUSH, POP, DISPLAY, MODIFY
A : EMPTY, OVERFLOW, UNDERFLOW
 Click
Here: Pictorial view of Stack Operations like Push &
Pop
|
ALGORITHM : STACK
Procedure PUSH(S,TOP,X) : This procedure inserts an element X to the top of the stack which is represented by a vector S consisting MAX elements with a pointer TOP denoting the top element in the stack.
STEP 1 : [Check for stack underflow]
If (TOP>=max-1)
then write(stack overflow)
Return
STEP 2 : [Increment TOP]
TOP <-- TOP+1
STEP 3 : [Insert element]
S[TOP] <-- X
STEP 4 : [Finished]
Return
The first step of this algorithm checks for an overflow
condition. If such a condition exists, then the insertion can't be performed and an appropriate error message results.
Procedure POP(S,TOP,X) : This procedure removes top element from the stack.
STEP 1 : [Check for the underflow on stack]
If (TOP<0)
then write(stack underflow)
Return
STEP 2 : [Hold the former top element of stack into X]
X <-- S[TOP]
STEP 3 : [Decrement the TOP pointer or index by 1]
TOP <-- TOP-1
STEP 4 : [finished-Return the popped item from the stack]
Return(X)
As Underflow condition is checked for in the first step of the algorithm. If such a condition exists, then the deletion cannot be performed and an appropriate error message results.
Procedure Display(S,TOP) : This procedure displays the contents of the stack i.e., vector S.
STEP 1 : [check for empty on stack]
if (TOP==-1)
then write('stack empty')
Return
STEP 2 : [Repeat through STEP 3 from i=TOP to 0]
Repeat through STEP 3 for i=TOP to 0 STEP-1]
STEP 3 : [Display the stack content]
write (S[i])
STEP 4 : [Finished]
Return
The first step of this algorithm checks for an empty condition. If such a condition exists, then the contents of the stack cannot be displayed and an appropriate error message results.
|
|
Click
Here: Complete Source code of Stack written in
C.
|
|
|
You are
Visitor No. 
Sign
my Guestbook 
View
my Guestbook
Thanks for using C For Swimmers.
Regarding this material, you can send Bug Reports,
Suggestions, Comments, etc. to
nandakishorkn@rediffmail.com
|
|
|
Note: All
logos or trademarks are related to their respective owners.
Although every
precaution has been taken, the designer(s) owe no responsibility
for malicious errors.
No liability assumed
for damages resulting from the use of the available information.
|
