Stacks
Stack ?!
Here's our first data structure , which is called a stack . The most
important property of a stack , which makes it different from a
queue is that it's is "LIFO : Last input
first output " , this looks like placing some copybooks on your desk ,
and then when you want one of them (assume that they are all simillar )
you've to take the one on the top first which is the last one was placed.
Notes.
* Write an element in stack ... Push.
* Move an element from stack ... Pop.
* Read an element from stack without deleting ... Top.
* IsEmpty and IsFull functions are never used when
dynamically allocated stack "Linked Stack".
* The main difference between the stacks and arrays is
that arrays have direct access to any element in it.
Syntax.
< stack.h >
#include < iostream.h >
#include < stdlib.h >
#include < assert.h >
/* To use assertion in the programme */
const int MaxStackSize=100 ;
typedef int StackElemType ;
/* Define a new variable type called StackElemType */
class Stack {
Public :
Stack( ) ;
void
Push(StackElemType) ;
StackElemType
Pop( ) ;
StackElemType
Top( ) ;
int
IsEmpty( ) ;
int
IsFull( ) ;
Private :
StackElemType StackArray[MaxStackSize] ;
int TopIndex ;
};
Stack::Stack( ) {
TopIndex = -1 ;
}
/* Constructor : done when the class is called in the main */
/* Back to the class */
void Stack::Push(StackElemType elem) {
if (TopIndex < MaxStackSize-1) {
StackArray[++TopIndex] = elem ;
}
}
/* We may use : assert(TopIndex < MaxStackSize-1) in stead
of the if condition , where the programme will continue if it's true
, and it will terminate otherwise */
/* We can do the "StackArray[++TopIndex] = elem ; " on two steps :
step one : "++TopIndex ; " note the position of the "++".
step two : "StackArray[TopIndex] = elem ; " */
/* Back to the class */
StackElemType Stack::Pop( ) {
if (TopIndex > -1) {
--TopIndex ;
return StackArray[TopIndex+1] ;
}
}
/* Also "asset(TopIndex > -1 )" can be used instead of the if */
/* Back to the class */
StackElemType Stack::Top( ) {
if (TopIndex > -1)
return StackArray[TopIndex] ;
}
/* Back to the class */
int Stack::IsEmpty( ) {
return TopIndex == -1 ;
}
/* Back to the class */
int Stack::IsFull( ) {
return TopIndex == MaxStackSize - 1 ;
}
/* Back to the class */
Applications :
(1)Reversing ... When you want to reverse a queue you've to use a
stack as one of them it "FIFO:Queue"
and the other is "LIFO:Stack"
(2)System control stack.
(
Prev
) (
Table of contents
) (
Next
)
Copyright (C) 2000 Tarek Amr Abdullah. All rights reserved. My Home Page