Pop Stack

Pop stack sends the data in the node at the top of the stack back to the calling algorithm. It then deletes and recycles the node ¾ that is, returns it to memory. After the count is adjusted by subtracting 1, the algorithm returns to the caller. If the pop was successful, it returns true; if the stack is empty when pop is called, it returns false.

algorithm popStack (ref stack ,

ref dataout )

This algorithm pops the item on the top of the stack and returns it to the user.

Pre stack is metadata structure to a valid stack

dataout is a reference variable to receive the data

post data have been returned to calling algorithm

Return true if successful; false if memory underflow

1 if (stack empty)

1 success = false

2 else

1 dltptr = Stack.top

2 dataout = stack.top->data

3 stack.top = stack.top->next

4 stack.count = stack.count – 1

5 recycle (dltptr)

6 success = true

3 end if

4 return success

end popStack

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

4.0 Stack Algorithms: 4.1 Create Stack

For each stack operation, we give its name, a brief description, and its calling sequence. We then develop algorithms for each one. The operations needed in a program depend on the application.

Create stack initializes the metadata for the stack structure. The pseudocode for create stack is shown in Algorithm 1.

algorithm createStack (ref stack )

Initializes metadata for a stack.

Pre stack is structure for metadata

Post metadata initialized to an empty state

1 stack.top = null;

2 stack.count = 0;

3 return

end createStack

STACK LINKED LIST IMPLEMENTATION

Data Structure

To implement the linked list stack, we need two different structures, a head and a data node. The head structure contains metadata and a pointer to the top of the stack. The data node contains data and a next pointer to the next node in the stack.

Stack Head

Generally the head for a stack requires only two attributes: a top pointer and a count of the number of elements in the stack. These two elements are placed in a head structure. Other stack attributes can be placed here also. For example, it is possible to record the time the stack was created and the total number of items that have ever been placed in the stack. These two metadata items would allow the user to determine the average number of items processed through the stack in given period.

Stack data Node

The rest of the data structure is a typical linked list data node. Although the application determines the data that are stored in the stack, the stack data node looks like any linked list node. In addition to the data, it contains a next pointer to other data nodes, making it a self-referential data structure.

Implementation of Stacks in Memory

We present a linked list method using dynamic memory allocation and pointers. The two structures needed to implement stacks are head structure and data node structure. We name them STACK and NODE, respectively. In C, they are defined as follows.

struct node

{

int data;

struct node *next;

};

struct stack

{

int count;

struct node *top;

}stack1;

These declarations will reserve required memory for the two structures, but no values are assigned to the members of the both structures. The following algorithm will initialize, that is, will assign values, the stack to an empty state, which can further be expanded or shrunk as the need arises.

Stack Top

The third stack operation is stack top. Stack top copies the item at the top of the stack; that is, it returns the data in the top element to the user but does not delete it. You might think of this operation as reading the stack top. Stack top can also result in underflow if the stack is empty.

Figure 5 traces these three operations in an example. We start with an empty stack and push 5 and 10 into the stack. At this point, the stack contains two entries. We then pop 10 from the top of the stack, leaving 5 as the only entry. After pushing 15, the stack again contains two entries. At this point, we retrieve the top entry, 15, using stack top. Note that stack top does not remove 15 from the stack; it is still the top element. We then pop 15, leaving 5 as the only entry. When 5 is popped, the stack is again empty. Note also how this example demonstrates the last In-first out operation of a stack. Although 5 was pushed first, it is the last to be popped.

Pop

When we pop a stack, we remove the item at the top of the stack and return it to the user. Because we have removed the top item, the next item in the stack becomes the top. When the last item in the stack is deleted, the stack must be set to its empty state. If pop is called when the stack is empty, then it is in an underflow state.

BASIC STACK OPERATIONS: Push

The three basic stack operations are push, pop, and stack top. Push is used to insert data into the stack. Pop removes data from a stack and returns the data to the calling module. Stack top returns the data at the top of the stack without deleting the data from the stack.

Push adds an item at the top of the stack. After the push, the new item becomes the top. The only potential problem with this simple operation is that we must ensure that there is room for the new item. If there is not enough room, then the stack is in an overflow state and the item cannot be added. Figure 2 shows the push stack operation.