Sunday, October 18, 2009

Push Stack

Push stack inserts an element into the stack. The first thing we need to do when we push data into a stack is find memory for the node. We must therefore allocate memory from dynamic memory. Once the memory is allocated, we simply assign the data to the Stack node and then set the next pointer to point to the node currently indicated as the stack top. We also need to update the stack top pointer and add 1 to the stack count field. Figure 9 traces a push stack operation in which a new pointer (newptr)is used to identify the data to be inserted into the stack.

To develop the insertion algorithm, we need to analyze three different stack conditions: (1) insertion into an empty stack, (2) insertion into a stack with data, and (3) insertion into a stack when the available memory is exhausted. The first two of these operations are shown in Figure 8. When we inset into a stack that contains data, the new node’s next pointer is set to point to the node currently at the top, and the stack’s top pointer is set to point to the new node. When we insert into an empty stack, the new node’s next pointer is set to null and the stack’s top pointer is set to point to the new node. However, because the stack’s top pointer is null, we can use it to set the new node’s next pointer to null. Thus the logic for inserting into a Stack with data and the logic for inserting into an empty stack are identical. The logic for the third case, stack overflow, depends on the application.

algorithm pushStack (ref stack ,

val datain )

Insert (push) one item into the stack.

Pre stack is metadata structure to a valid stack

datain contains data to be pushed into stack

post data have been pushed in stack

Return true if successful; false if memory overflow

1 if (stack full)

1 success = false

2 else

1 allocate (newptr)

2 newptr->data = datain

3 newptr->next = stack.top

4 stack.top = newptr

5 stack.count = stack.count + 1

6 success = true

3 end if

4 return success

end pushStack

No comments:

Post a Comment