2.3 Stacks

• Stack is a special kind of list in which all insertions and deletions occur at one end, called the top.
• Stack ADT is a special case of the List ADT. It is also called as a LIFO list or a pushdown list.
• Typical Stack ADT Operations:

1.	makenull (S)	creates an empty stack
2.	top (S)	returns the element at the top of the stack.
		Same as retrieve (first (S), S)
3.	pop (S)	deletes the top element of the stack
		Same as deletes (first (S), S)
4.	push (x, S)	Insert element x at the top of stack S.
		Same as Inserts (x, first (S), S)
5.	empty (S)	returns true if S is empty and false otherwise

• Stack is a natural data structure to implement subroutine or procedure calls and recursion.
• Stack Implementation : Arrays, Pointers can be used. See Figures 2.5 and 2.6

Figure 2.5: An array implementation for the stack ADT



Figure 2.6: A linked list implementation of the stack ADT 


• Pointer Implementation of Stacks: The following code provides functions for implementation of stack operations using pointers. See Figures 2.7 and 2.8 for an illustration of push and pop operations on a linked stack.

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

 
 
 

Figure 2.8: Pop operation on a linked stack

/* 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) ;

            }