| FAQ | Newsboard |
|---|
Defining a Stack as an Abstract Data Type
A stack is an example of a linear data structure. Linear datastructures are collections of components arranged in a straightline. When we add or remove components of linear data structures, theygrow and shrink. If we restrict the growth of a linear data structureso that new components can only be added or removed only at one end,we have a stack.Stacks are useful data structures and are used in a variety of ways incomputer science. You already know that stacks are used to implementfunctions and you have seen that each running program has a stack andhow a program's stack grows and shrinksduring calls to functions/procedures. This is especially important inunderstanding how recursion works.
In general, stacks are useful for processing nested structures or forfunctions which call other functions (or themselves). A nestedstructure is one that can contain instances of itself embedded withinitself. For example, algebraic expressions can be nested because asubexpression of an algebraic expression can be another algebraicexpression. Stacks are used to implement functions, parsers,expression evaluation, and backtracking algorithms.
A pile of books, a stack of dinner plates, a box of pringles potatochips can all be thought of examples of stacks. The basic operatingprinciple is that last item you put in is first item you can takeout. That is, that a stack is a Last In First Out (LIFO) structure.
As an abstract entity, a stack is defined by the operations of addingitems to the stack, push(), and the operation of removing itemsfrom the stack, pop(). There are a couple of other incidentals,that we need to take care of such as not push()ing an itemonto a full stack and not trying to pop() items froman empty stack. This Abstract Data Type definition of a stackdoes not define how a stack is implemented in a computer program, itonly defines the operations on a stack. In general, an AbstractData Type (ADT) consists of a collection of data structurestogether with a set of operations defined on those data structures. Weare already familiar with the structuring methods that C provides,like arrays, structs, and strings. To define an ADT, inaddition to defining the basic data structures, we need to define aset of permissible operations on those data structures. In the case ofstacks we need to define a structure (probably usingstruct)) to hold the data, as well as functions formanipulating the data, namely push(), pop() and two functionsto check whether a stack is full() or empty().
An ADT for a stack may therefore look like:
A stack, S of type T is a sequence of itemsof type T on which the following operations are defined:
- Initialize the stack S to be the empty stack
- Determine whether or not the stack S is empty()
- Determine whether or not the stack S is full()
- push() a new item of type T onto the topof the stack, S
- If S in not empty, pop() an item from the topof the stack, S.
Implementing a Stack
Many things need to be kept in mind when implementing an abstract datatype, or more generally, when implementing something that will be usedby many people. There are two points of view to cater to. We usuallywant to keep the implementation hidden from the user so that if we (asimplementers) think of a better, more efficient design we canimplement this better design without the user's knowledge. From theuser's point of view, I don't care how you've implemented a stack, all Icare about is that I can easily use your implementation of a stack.
The two points of view, ease of use, ease of implementation, generality, androbustness are some of the criteria that led to the followingimplemenation of the Stack ADT.
From the implementer's point of view we need to implement thefollowing functions.
- Stack * initstack(void) which "creates" and initializesstack, S of type Stack and returns a pointer to S. If it is not possible to create a stack, it returns a pointer to NULL.
- int empty(Stack *S) which returns true if the stack,S, is empty and false otherwise.
- int full(Stack *S) which returns true if the stack,S, is full and false otherwise.
- int push(ItemType X, Stack *S) which pushes X on thestack, only if S is not full. Success or failure isindicated by the integer return value. A return value of 1 indicatessucess, a return value of 0 indicates failure.
- int pop(Stack *S, ItemType *X) which returns the itempopped off the stack in X, only if S is not empty. A return value of 1 indicates sucess, a return value of 0 indicatesfailure.
- void stackprint(Stack *S, char *format) which prints thecurrent contents of the stack from the top of the stack to thebottom using the format string that is passed in and which isappropriate for ItemType. It should indicate which is theitem at the top of the stack.
We will try and make these functions as general as possible. To do solet us leave the the typedefs for Stack andItemType in #include files namedStackTypes.h to be created by a user, and stacks.hto be created by the implementer.
We thus expect StackTypes.h (created by the user) willcontain typedefs for ItemType to be defined by theuser and it will also contain a #define to define themaximum number of items that a stack can hold.
Similarly, stacks.h (created by the implementer) willcontain typedefs for Stack, function prototypeddeclarations for the stack functions above, and#defines having to do with the implementation.
Suppose a user is only going to deal with characters, that will bepushed and popped from a stack. The user also realizes that no morethan a 100 items will ever be put on the stack. The user has been toldthat MAXSIZE needs to be the maximum size of the stack andthat ItemType must be typedef'd to be the type ofthe items on a stack. This user can thencreate a StackTypes.h that looks like:
#define MAXSIZE 100typedef char ItemType;Now, to create and use stacks, all the user needs to do is to create aprogram file that includes StackTypes.h, stacks.h in that order andshe/he will be able to invoke the stack functions in this program file.
The implementer's job is now to
- Design a data structure for a stack and associated data anddeclare the stack function prototypes in stacks.h andthen
- Declare variables and define the functions that deal with thestack in stack.c
/* must include StackTypes.h before including this file */#define NSTACKS 10#ifndef TRUE#define TRUE (1 == 1)#endif#ifndef FALSE#define FALSE (0 == 1)#endif/* typedef for Stack */typedef struct { ItemType items[MAXSIZE]; int top;} Stack;/* Prototype declarations */int empty(Stack *S), full(Stack *S);Stack * InitStack(void);int push(ItemType X, Stack *S);int pop(Stack *S, ItemType *X);void PrintStack(Stack *S, char *format);NSTACKS is our (implementer's) upper limit on the number ofstacks available. If TRUE and FALSE have not beenpreviously defined we define them. Then comes the typedef forStack. Note that a Stack contains two members:- An array of type ItemType (size MAXSIZE)
- An integer top, that will be used to "point" to the top ofthis stack.
It is now time to declare the variables we will be using and definethe stack functions. We will put these variables and functions in afile called stack.c whose first few lines look like:
#include <stdio.h>#include "StackTypes.h"#include "stacks.h" /* must be included AFTER StackTypes.h */static int inuse = 0;static Stack stacks[NSTACKS];We include stdio.h then StackTypes.h andstacks.h in that order. StackTypes.h must beincluded before stacks.h because it typedefsItemType and #defines MAXSIZE which areused in stacks.h
The last two lines declare static global variables. inuse counts the number of stacks currently in use (maximumis NSTACKS). stacks is an array of structures of typeStack and the size of this array is NSTACKS.The array declares NSTACK stacks that can be usd to holditems of type ItemType. These static variables cannot beaccessed outside this file.
With these declarations ready, we can think about definingInitStack(). This function returns a pointer to a newlycreated stack, if one is available. Otherwise it returns theNULL pointer. The idea behind implementingInitStack() is to take a pointer to one of the unusedNSTACK stacks, and return it to the invoking function aftersetting the variable top to 0. If all NSTACK stacksare in use, return NULL.
Stack * InitStack(void){ if (inuse < NSTACKS) { stacks[inuse].top = 0; inuse++; return &(stacks[inuse - 1]); } else { return NULL; }}Note that we have to return &(stacks[inuse - 1]). This isbecause we have already incremented inuse to reflect thenew number of stacks in use. The functions empty() and full() are fairlysimple. Given a pointer to a stack structure, check if the membertop is 0 or MAXSIZE
int empty(Stack *S){ if (S->top <= 0) return TRUE; else return FALSE;}int full(Stack *S){ if (S->top >= MAXSIZE) return TRUE; else return FALSE;} Push() and pop() are also fairly simple. We havemade both robust by checking whether a stack is full or empty beforewe push or pop an item. If we cannot push or pop an item, thesefunctions return the error value of 0, otherwise they do their job andreturn 1 to indicate success. Since the return value is used toindicate success or failure, pop() must use a pointer to avariable of type ItemType to "return" the item popped of thestack.
int push(ItemType X, Stack *S){ if (full(S)) { return 0; } else { S->items[S->top++] = X; return 1; }}int pop (Stack *S, ItemType *X){ if(empty(S)) { return 0; } else { *X = S->items[--(S->top)]; return 1; }}The post-increment and pre-decrement operators ensure that the rightstack top pointer is incremented correctly after pushing anitem on the stack, and decremented correctly before popping anitem from the stack. One last function StackPrint() remains to be defined. In ourquest for generality, we will try to make StackPrint() workno matter what ItemType item we print. This is accomplishedby making StackPrint() take two arguments: the stack to beprinted and a format string that corresponds toItemType.
void StackPrint(Stack *S, char *format){ int i; printf("top-> "); for(i = S->top - 1; i >= 0; i--) printf(format, S->items[i]); printf(" <-bot\n");}That is it. As implementers we have done our job! Let's now switchjobs and become a user. To use stacks, we only need to provide a type definition forItemType and figure out what we think the maximum number ofitems we would store on a stack (put this in StackTypes.h).Then to use the stack functions we would need to includeStackTypes.h and stacks.h and we would be able toinvoke the stack functions. Here's an example:
#include <stdio.h>#include "StackTypes.h"#include "stacks.h".....int main(int argc, char * argv[]){ .... ItemType foo; Stack *S1, *S2; .... S1 = InitStack(); if (S1 == NULL) { printf("Could not create a stack\n"); exit(1); } ..... if (push(foo, S) != 1) { printf("cannot push on full stack...\n); take appropriate error action } .... if (pop(S, &foo) != 0) { printf("cannot pop from empty stack...\n); take appropriate error action } ..... PrintStack(S, "%c "); /* assuming typedef char ItemType */ .....} 