nextupprevious
Next:2.4 QueuesUp:2. ListsPrevious:2.2.3 Doubly Linked List Implementation

2.3 Stacks




typedef struct node-tag {

                        item-type info ;

                        struct node-tag * next ;

                    } node-type ;

typedef struct stack-tag {

                        node-type * top ;

                    } stack-type ;

stack-type stack ; /* define a stack */

stack-type * sp = & stack ; /* pointer to stack */

node-type *np ; /* pointer to a node */
 

/* makenode allocates enough space for a new node and initializes it */

node-type * makenode (item-type item)

{

            node-type *p ;

                if ((p = (node-type *) malloc (sizeof

                (node-type))) = = null)

                error (``exhausted memory'') ;

                    else {

                p $ \rightarrow$ info = item ;

                p $ \rightarrow$ next = null ;

        }

        return (p) ;

}



 

/* pushnode pushes a node onto the top of the linked stack */

    void pushnode (node-type *np, stack-type *sp)

{

        if (np = = null)

            error (``attempt to push a nonexistent node'')

        else {

                np $ \rightarrow$ next = sp $ \rightarrow$ top ;

                sp $ \rightarrow$ top = np

            }

}

void popnode (node-type * *np ; stack-type *sp)

        {

                if (sp $ \rightarrow$ top = = null)

                    error (``empty stack'') ;

                else {

                *np = sp $ \rightarrow$ top ;

                        sp $ \rightarrow$ top = (* np) $ \rightarrow$ next ;

                }

            }


Figure 2.7: Push operation in a linked stack
\begin{figure}\centerline{\psfig{figure=figures/Fpushstack.ps}}\end{figure}

 
 
 

Figure 2.8: Pop operation on a linked stack
\begin{figure}\centerline{\psfig{figure=figures/Fpopstack.ps}}\end{figure}



/* push-make a new node with item and push it onto stack */

            void push (item-type item ; stack-type *sp)

            {

                pushnode (makenode (item), sp) ;

            }

/* pop-pop a node from the stack and return its item */

            void pop (item-type * item, stack-type *sp)

            {

                node-type * np ;

                popnode (& np, sp) ;

            * item = np $ \rightarrow$ info ;

                free (np) ;

            }


nextupprevious
Next:2.4 QueuesUp:2. ListsPrevious:2.2.3 Doubly Linked List Implementation
eEL,CSA_Dept,IISc,Bangalore