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.

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. Situation before execution of algorithm, and after the algorithm is shown in first part of figure 8.

Introduction Stacks

A stack is an ordered dynamic linear list in which all additions of new elements and deletions of existing elements are restricted to one end, called the Top. If a data series is inserted into a stack, and then removed it, the order of the data would be reversed. This reversing attribute due to addition and removal at the top of stack give a special behaviour, called as “Last-in, first-out” (LIFO) structure.

A stack is dynamic because it is constantly changing

objects, it expands and shrinks with passage of time.

The basic Stack operations are Create Stack, Push,

Pop, Stacktop, Emptystack, Full stack, Stack Counts,

And Destroy stacks.

Separate Chaining Resolution Using Linked List

A major disadvantage to open addressing is that each collision resolution increases the probability of future collisions. This disadvantage is eliminated in the second approach to collision resolution known as separate chaining using short linked lists. Separate chaining is an ordered collection of data in which each element contains the location of the next synonymous element. For example, in Figure 12, array element 001, Sarah Trapp, contains a pointer to the next element, Harry Eagle, which in turn contains a pointer to the third element, Chirs Walljasper.

Quadratic Probe

Primary clustering can be eliminated by adding a value other than 1 to the current address. One easily implemented method is to use the quadratic probe. In the quadratic probe, the increment is the collision probe number squared. Thus for the first probe we add 1², for the second collision probe we add 2², for the third collision probe we add 3², and so forth until we either find an empty element or we exhaust the possible elements. To ensure that we don’t run off the end of the address list, we use the modulo of the quadratic sum for the new address. This sequence is shown in Table 1, which for simplicity assumes a collision at location 1 and a list size of 100. From table, we can see quadratic probing causes secondary clustering on a collision resolution path.

Address = H(K)+C i²

Where we take C=1 and i is collision probe number.

Pseudorandom Method

In the pseudorandom method, the key is used as the seed in a pseudorandom number generator and the resulting random number is then scaled into the possible address range using modulo division. A common random number generator is shown below.

y = ax + c

This method is also known as MAD which stands for multiply, add and divide. To use the pseudorandom number generator as a hashing method, we set x to the key, multiply it by the coefficient a, and then add the constant c. The result is then divided by the list size with the remainder (see “Modulo-Division Method,”) being the hashed address. Let’s demonstrate the concept with an example from Figure 6. To keep the calculation reasonable, we use 17 and 7 for factors a and c, respectively. Also, the list size in the example is the prime number 307.

y = ((17 * 121267) + 7)modulo 307

y = (2061539 + 7) modulo 307

y = 2061546 modulo 307

y = 4

We will see this pseudorandom number generator again when we discuss collision resolution.

Midsquare Method

In midsquare hashing, the key is squared and the address selected from the middle of the squared number. The most obvious limitation of this method is the size of the key. Given a key of 6 digits, the product will be 12 digits, which is beyond the maximum integer size of many computers. Because most personal computers can handle a 9-digits integer, let’s demonstrate the concept with keys of 4 digits. Given a key of 9452, the midsquare address calculation is shown below using a 4-digit address (0000 to 9999).

9452 * 9452 = 89340304 : address is 3403

As a variation on the midsquare method, we can select a portion of the key, such as the middle three digits, and then use them rather than the whole key. Doing so allows the method to be used when the key is too large to square. For example, for the keys in Figure 6, we can select the first three digits and then use the midsquare method as shown below. (We select the third, fourth, and fifth digits as the address.)

379452 : 379 * 379 = 143641 ë 364

121267 : 121 * 121 = 014641 ë 464

378845 : 378 * 378 = 142884 ë 288

160252 : 160 * 160 = 025600 ë 560

045128 : 045 * 045 = 002025 ë 202

Note that in the midsquare method, the same digits must be selected from the product. For that reason, we consider the product to have sufficient leading zeros to make it the full six digits.