An implementation of the fundamental functions are demonstrated below.
First I'll show you how to declare a stack data structure using an array and its top pointer. These will be global variables in your program as long as you decide to use them specifically in some procedure or function.
Const
STACK_SIZE = 100;
Var
myStack : Array[1..STACK_SIZE] of DataItem;
topPointer : Integer;
|
The initialisation is to be called before any stack operation.
Procedure InitStack;
Begin
topPointer := 0;
End; |
We now implemement the IsEmpty() and IsFull() functions.
Function IsEmpty : Boolean;
Begin
IsEmpty := false;
If (topPointer = 0) then
IsEmpty := true;
End; |
Function IsFull : Boolean;
Begin
IsFull := false;
If ((topPointer + 1) = STACK_SIZE) then
IsFull := true;
End; |
Here are the implementations of the Pop() and Push() functions and making use of the functions that we have just implemented.
Function Pop : DataItem;
Begin
Pop := nil;
If not IsEmpty then
Begin
Pop := myStack[topPointer];
topPointer := topPointer - 1;
End;
End;
|
Procedure Push(item : DataItem);
Begin
If not IsFull then
Begin
myStack[topPointer+1] := item;
topPointer := topPointer + 1;
End;
End; |
Finally, we implement the utility function GetSize(). Although one can access the current size of the stack using the global variable topPointer, it is of good practice to make use of functions instead of global variables.
Function GetSize : Integer;
Begin
GetSize := topPointer;
End; |
That's the story of implementing a Stack Data Structure. It is a very useful utility that is not provided ready made with a programming language. A stack has wide range of uses such as in parsing a command line calculator - matching brackets. The stack is also used inevitably by your operating system in executing programs. When a function is called, the location in memory of the embedding function is pushed onto the stack for later reference, so that the operating system 'remembers' where it has broken execution of the previous function. When the function continues execution, it is poped off the stack.
|
