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

# 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.
•  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
• 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  info = item ;

p  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  next = sp  top ;

sp  top = np

}

}

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

{

if (sp  top = = null)

error (empty stack'') ;

else {

*np = sp  top ;

sp  top = (* np)  next ;

}

}

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

free (np) ;

}

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