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.

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.

We shall also study the following application of stacks, reversing data (convert decimal to

binary) parsing data (matching of parentheses in source programs), postponing data usage (Infix, Postfix, Prefix and evaluation of Postfix expressions.) Stack frames concept is studied in a separate chapter on recursion.

Doubly Linked List Deletion

Deleting from a doubly linked list requires that the deleted node’s predecessor, if any, be pointed to the deleted node’s successor and that the successor, if any, be set to point to the predecessor. This rather straight forward logic is shown in Figure 21. Once we locate the node to be deleted, we simply change its predecessor’s and successor’s pointers and recycle the node.

The pseudocode is shown in Algorithm 13.

Algorithm – 13 Double linked list delete

algorithm deleteDbl (ref list ,

val pDlt ,

ref dataout )

The algorithm deletes a node from a doubly linked list.

Pre list is metadata structure to a valid list

pDlt is a pointer to the node to be deleted

Post node deleted

1 dataout = pDlt->data

Check if not first node

2 if (pDlt->back not null)

Point predecessor to successor

1 pPred = pDlt->back

2 pPred->fore = pDlt->fore

3 else (First node)

Update head pointer

1 list.head = pDlt->fore

4 end if

Check if not last node

5 if (pDlt->fore not null)

Point successor to predecessor

1 pSucc = pDlt->fore

2 pSucc->back = pDlt->back

6 else (Last node)

Point rear to predecessor

1 list.rear = pDlt->back

7 end if

8 recycle (pDlt)

9 list.count = list.count - 1

10 return

end deleteDbl

Other Linked List Variations

We introduce two other useful linked list variations – the circularly linked list and the doubly linked list.

Circularly linked list

In the circularly linked list, the last node’s link points to the first node of the list, as shown in Figure 18. Circularly linked list are primarily used in structures that allow access to nodes in the middle of the list without starting at the beginning. In circular list, nodes form a ring: The list is finite and each node has a successor.

Insertion and deletion into a circularly linked list follow the same logic used in singly linked list except that the last node points to the first node. Therefore, when inserting and deleting the last node, in addition to updating the rear pointer in the header, we must also point the head field to the first node.

Given that we can directly access a node in the middle of the list through its data structure, we are then faced with a problem when searching the list. If the search target lies before the current node, how do we find it? In a singly linked list, when we arrive at the end of the list the search is complete. In a circular list, however we automatically continue the search from the beginning of list.

The ability to continue the search presents another problem. What if the target does not exist? In the singly linked list, if we did not find the data we are looking for, we stopped when we hit the end of list. With a circular list, we save the starting node’s address and stop when we have circled around to it, as shown code below.

Loop (key not equal to pLoc->node.data

AND pLoc->link not equal to startAddress)

Circular list, in which the last node is followed by the first node, is usually preferable to non-circular one, for two reasons:

• They provide easy access to both ends of a list: notice that we do not need the first pointer in the header, because we can easily reach the first node with rear -> link -> data
• the code for processing a circular list is often simpler than the code for processing a non-circular list - mainly because you don't have to constantly check if the next node is defined - it is always defined.

At the implementation level, however, circularity does create one very tricky case that is a very common source of bugs, and that is singleton lists. When there is only one node in a circular list, it points to itself as the next node.

Doubly Linked or Two-way Linked Lists

One of the most powerful variations of linked lists is the doubly linked list. A doubly linked list is a linked list structure in which each node has a pointer to both its successor and its predecessor. Figure 19 is a representation of a doubly linked list.

There are three pieces of metadata in the head structure: a count, a head pointer, and a rear pointer. Although a rear pointer is not required in all doubly linked lists, it makes some of the list algorithms, such as insert and search, more efficient.

Each node contains two pointers, a backward pointer to its predecessor and a forward pointer to its successor. In Figure 19 these pointers are designated B and F, respectively.

Another variation on the doubly linked list is the doubly linked circularly linked list. In this variation, the last forward pointer points to the first node of the list and the backward pointer of the first node points to the last node. If there is only one node in the list, both the forward and backward pointers point to the node itself.

Doubly Linked List Insertion

Inserting a node into a doubly linked list follows the basic pattern of inserting a node into a singly linked list, but we also need to connect both the forward and backward pointers.

A null doubly linked list’s head and rear pointers are null. To insert a node into a null list, we simply set the head and rear pointers to point to the new node and set the forward and backward pointers of the new node to null. The results of inserting a node into a null list are shown in Figure 20(a).

Figure 20(b) shows the case for inserting between two nodes. The new node needs to be set to point to both its predecessor and its successor, and they need to be set to point to the new node. Because the insert is in the middle of the list, the head structure is unchanged except for adding to the count.

Inserting at the end of the list requires that the new node’s back pointer be set to point to its predecessor. Because there is no successor, the forward pointer is set to null. The rear pointer in the head structure must also be set to point to the new rear node.

Algorithm 22 contains the code to insert a node into a doubly linked list.

Algorithm – 12 Doubly linked list insert

algorithm insertDbl (ref list ,

pPre ,

pSucc ,

val dataIn )

This algorithm inserts data into a doubly linked list.

Pre list is metadata structure to a valid list

PPre is pointer variable for predecessor

PSucc is pointer variable for successor

dataIn contains the data to be inserted

Post The data have been inserted in sequence

Return 0 : failed—dynamic memory overflow

1 : successful

1 if (full list)

1 return 0

2 end if

3 allocate (pNew)

4 pNew->data = dataIn

Locate insertion point in list

5 if (pPre is null)

Inserting before first node or into empty list

1 pNew->back = null

2 pNew->fore = list.head

3 list.head = pNew

6 else

Inserting into middle or end of list

1 pNew->back = pPre

2 pNew->fore = pPre->fore

3 pPre->fore = pNew

7 end if

Test for insert at end of list and also check not empty list

8 if (pPre->fore null and pPre not null)

Inserting at end of list –set rear pointer

1 list.rear = pNew

9 else

Inserting in middle of list — point successor to new

1 if (pSucc not null) check not empty list

1 pSucc->back = pNew

10 end if

11 list.count = list.count + 1

12 return(1)

end insertDbl

Operation 13 – Print List:

One of the more common uses of link list traversals is to print the entire contents of a list. If the user selects the print list option from the menu, we traverse the list and print all of the key fields. In this program, we simply print a sequential number and the data from the node Within a loop, we continue until all of the data have been printed. The code is shown in Algorithm 11.

Algorithm 13: Print Linked List

algorithm printList (val list )

This algorithm traverses a linked list and prints the data in node.

Pre list is metadata structure to a valid list

Post All data have been printed in sequence

1 if (list.head null)

1 Print (No data in list.)

2 else

1 print (**** Begin Data Print ****)

2 sno = 0

1 dataptr = list.head

2 loop (dataptr-> link not null)

1 sno = sno + 1

2 print (sno, dataPtr->data)

3 dataptr = dataptr-> link

5 end loop

6 print (**** End Data Print ****)

3 end if

4 retrun

end printList

Operation 12 – Destroy List:

When a list is no longer needed but the application is not done, the list should be destroyed. Destroy list deletes any nodes still in the list and recycles their memory. It then sets the metadata to a null list condition. The code for destroy list is shown in Algorithm 10.

Algorithm – 10 Destroy linked list

algorithm destroyList (ref list )

Deletes all data in list

Pre list is metadata structure to a valid list

Post All data deleted

1 loop (list.count not zero)

1 dltPtr = list.head

2 list.head = dltPtr->link

3 list.count= list.count – 1

4 recycle (dltPtr)

2 end loop

No data left in list. Reset metadata.

3 list.head = null

4 return

end destroyList

Operation 9 – Traverse List :

Algorithm that traverse a list start at the first node and examine each node in succession until the last node has been processed. Traversal logic is used by several different types of algorithms, such as changing a value in each node, printing the list, summing a field in the list, or calculating the average of a field. Any application that requires that the entire list be processed uses a traversal.

To traverse the list we need a walking pointer, a pointer that moves from node to node as each element is processed. Assuming a linked list with a head structure, the following pseudocode uses a walking pointer to traverse the list. Each loop modifies the pointer to move to the next node in sequence as we traverse the list.

pos = list.head

loop (pos not null)

process (pos->data)

pos = pos->link

We begin by setting the walking pointer to the first node in the list. Then, using a loop, we continue until all of the data have been processed. Each loop calls a process module and passes it the data and then advances the walking pointer to the next node. When the last node has been processed, the walking pointer becomes null and the loop terminates.

Because we need to remember where we are in the list from one call to the next, we need to add a current position pointer to the head structure. It keeps track of the node processed after the last call. The head structure is shown in Figure 17. The figure also shows how the position pointer is modified to move from one node to the next as the traversal algorithm is called.

Each call also needs to know whether we are starting from the beginning of the list or continuing from the last node processed. This information is communicated through the parameter list. The basic logic to traverse a list is

shown in Algorithm 9. We name it getNext because it is called to get the next node in the traversal.

Algorithm – 9 Traverse linked list

algorithm getNext (ref list ,

val fromWhere ,

ref dataOut )

Traverses a linked list. Each call returns the location of an element in the list.

Pre list is metadata structure to a valid list

fromWhere is 0 to start at the first element

fromWhere is 1 to continue from current position

dataOut is variable to receive data

Post dataOut contains data and true returned

-or- if end of list, returns false

Return true if next element located, false if end of list

1 if (fromWhere is 0)

Start from first

1 if (list.count is zero)

1 success = false

2 else

1 list.pos = list.head

2 dataOut = list.pos->data

3 success = true

3 end if

2 else

Continue from pos

1 if (list.pos->link equal null)

End of List

1 success = false

2 else

1 list.pos = list.pos->link

2 dataOut = list.pos->data

3 success = true

3 end if

3 end if

4 return success

end getNext