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