Data Structures


Data Structures

Queues, Stack, Linked List 

Queues

Definition: A queue is simply a linear list of information that is accessed in first-in, first-out order, which is sometimes called FIFO. That is, the first item placed on the queue is the first item retrieved, the second item put in is the second item retrieved, and so on. This is the only means of storage and retrieval in a queue; random access of any specific item is not allowed.

Keep in mind that a retrieval operation removes an item from the queue and destroys it if it is not
stored elsewhere. Therefore, a queue will be empty after all items have been removed.

To see an example of a queue in action:

we will use a simple appointment-scheduler program. This program allows you to enter a number of appointments; then, as each appointment is met, it is taken off the list. For the sake of simplicity, each appointment description will be limited to 255 characters, and the number of appointments is arbitrarily limited to 100.




First, the functions qstore( ) and qretrieve( ) shown here are needed for the simple scheduling program. They will store pointers to the strings that describe the appointments.

Notice that these functions require two global variables: spos (which holds the index of the next free storage location) and rpos (which holds the index of the next item to retrieve). You can use these functions to maintain a queue of other data types by simply changing the base type of the array that they operate on.

The function qstore( ) places pointers to new appointments on the end of the list and checks to see if the list is full. The function qretrieve( ) takes appointments off the queue while there are events to perform. With each new appointment scheduled, spos is incremented, and with each appointment completed, rpos is incremented. In essence, rpos chases spos through the queue. If rpos and spos are equal, there are no events left in the schedule. Even though the information stored in the queue is not actually destroyed by qretrieve( ), it is effectively destroyed because it can never be accessed again.


The entire program for this simple appointment scheduler is listed here. You may want to enhance this program for your own use.


/* Mini Appointment-Scheduler */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#define MAX 100

char *p[MAX], *qretrieve(void);
int spos = 0;
int rpos = 0;
void enter(void), qstore(char *q), review(void), delete_ap(void);

int main(void)
{
char s[80];
register int t;
for(t=0; t < MAX; ++t) p[t] = NULL; /* init array to nulls */
for(;;) {
printf("Enter, List, Remove, Quit: ");
gets(s);
*s = toupper(*s);
switch(*s) {
case 'E':
enter();
break;
case 'L':
review();
break;
case 'R':
delete_ap();
break;
case 'Q':
exit(0);
}
}
return 0;
}

/* Enter appointments in queue. */
void enter(void)
{
char s[256], *p;
do {
printf("Enter appointment %d: ", spos+1);
gets(s);
if(*s==0) break; /* no entry */
p = (char *) malloc(strlen(s)+1);
if(!p) {
printf("Out of memory.\n");
return;
}
strcpy(p, s);
if(*s) qstore(p);
} while(*s);
}


/* See what's in the queue. */
void review(void)
{
register int t;
for(t=rpos; t < spos; ++t)
printf("%d. %s\n", t+1, p[t]);

}


/* Delete an appointment from the queue. */
void delete_ap(void)
{
char *p;
if((p=qretrieve()) ==NULL) return;
printf("%s\n", p);
}


/* Store an appointment. */
void qstore(char *q)
{
if(spos==MAX) {
printf ("List Full\n");
return;
}
p[spos] = q;
spos++;
}


/* Retrieve an appointment. */
char *qretrieve(void)
{
if(rpos==spos) {
printf("No more appointments.\n");
return NULL;
}
rpos++;
return p[rpos-1];
}

Output Screen:


Stacks

A stack is the opposite of a queue because it uses last-in, first-out accessing, which is sometimes called LIFO. To visualize a stack, just imagine a stack of plates. The first plate on the table is the last to be used, and the last plate placed on the stack is the first to be used. Stacks are used frequently in system software, including compilers and interpreters.

When working with stacks, the two basic operations— store and retrieve— are traditionally called push and pop, respectively.
Therefore, to implement a stack you need two functions: push( ), which places a value on the stack, and pop( ), which retrieves a value from the stack. You also need a region of memory to use as the stack. You can use an array for this purpose or allocate a region of memory using C's dynamic allocation functions. As with the queue, the retrieval function takes a value off the list and destroys it if it is not stored elsewhere. The general forms of push( ) and pop( ) that use an integer array follow. You can maintain stacks of other data types by changing the base type of the array on which push( ) and pop( ) operate.

A simple format of Stack:


int stack[MAX];
int tos=0; /* top of stack */
/* Put an element on the stack. */
void push(int i)
{
if(t.os >= MAX) {
printf (''Stack Full\n");
return;
}
stack[tos] = i;
tos++;
}
/* Retrieve the top element from the stack. */
int pop (void)
{
tos--;
if(tos < 0) {
printf("Stack Underflow\n");
return 0;
}
return stack[tos];
}



The following example demonstrates a stack by implementing a postfix calculator for integer
expressions. To begin, the push( ) and pop( ) functions must be modified, as shown here. They also will use dynamically allocated memory (instead of a fixed-size array) for the stack.

Although the use of dynamically allocated memory is not necessary for this simple example, it illustrates how dynamically allocated memory can be used to support a stack.

/* A simple four-function calculator. */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int *p; /* will point to a region of free memory */
int *tos; /* points to top of stack */
int *bos; /* points to bottom of stack */

void push(int i);
int pop(void);

int main(void)
{
int a, b;
char s[80];
p = (int *) malloc(MAX*sizeof(int)); /* get stack memory */
if(!p)
{
printf("Allocation Failure\n");
exit(1);
}
tos = p;
bos = p + MAX-1;
printf("Four Function Calculator\n");
printf("Enter 'q' to quit\n");
do {
printf(": ");
gets(s);
switch(*s) {
case '+':
a = pop();
b = pop();
printf("%d\n", a+b);
push(a+b);
break;
case '-':
a = pop();
b = pop();
printf("%d\n", b-a);
push(b-a);
break;
case '*':
a = pop();
b = pop();
printf("%d\n", b*a);
push(b*a);
break;
case '/':
a = pop();
b = pop();
if(a==0) {
printf("Divide by 0.\n");
break;
}
printf("%d\n", b/a);
push(b/a);
break;
case '.': /* show contents of top of stack */
a = pop();
push(a);
printf("Current value on top of stack: %d\n", a);
break;
default:
push(atoi(s));
}
} while(*s != 'q');
return 0;
}
/* Put an element on the stack. */
void push(int i)
{
if(p > bos) {
printf("Stack Full\n");
return;
}
*p = i;
p++;
}
/* Retrieve the top element from the stack. */
int pop(void)
{
p--;
if(p < tos) {
printf("Stack Underflow\n");
return 0;
}
return *p;
}

Output Screen:


linked list

Concept of a linked list revisited


Static arrays are structures whose size is fixed at compile time and therefore cannot be extended or reduced to fit the data set. A dynamic array can be extended by doubling the size but there is overhead associated with the operation of copying old data and freeing the memory associated with the old data structure. One potential problem of using arrays for storing data is that arrays require a contiguous block of memory which may not be available, if the requested contiguous block is too large. However the advantages of using arrays are that each element in the array can be accessed very efficiently using an index.

However, for applications that can be better managed without using contiguous memory we define a concept called "linked lists".

 A linked list is a collection of objects linked together by references from one object to another object. By convention these objects are named as nodes. So the basic linked list is collection of nodes where each node contains one or more data fields AND a reference to the next node. The last node points to a NULL reference to indicate the end of the list.

The entry point into a linked list is always the first or head of the list. It should be noted that head is NOT a separate node, but a reference to the first Node in the list. If the list is empty, then the head has the value NULL. Unlike Arrays, nodes cannot be accessed by an index since memory allocated for each individual node may not be contiguous. We must begin from the head of the list and traverse the list sequentially to access the nodes in the list. Insertions of new nodes and deletion of existing nodes are fairly easy to handle and will be discussed in the next lesson. Recall that array insertions or deletions may require adjustment of the array (overhead), but insertions and deletions in linked lists can be performed very efficiently.





A Simple C Program Using Single Linked List


/* The program will stores the emp id, name, designation, upto reached to MAX and displays, delete  
etc using single linked list*/ 

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#define MAX 30
struct EMP
{
int  empno;
char empName[MAX];
    char designation[MAX];
    struct EMP *next;
};
/*********************************************************************/
/* Function to insert a node at the front of the linked list.        */
/* front: front pointer, id: employee ID, name: employee name        */
/* desg: Employee designation     */
/* Returns the new front pointer.                                    */
/*********************************************************************/
struct EMP* insert(struct EMP *front, int id, char name[], char desg[])
{
    struct EMP *newnode;
    newnode = (struct EMP*) malloc(sizeof(struct EMP));
    if (newnode == NULL)
    {
 printf("\nAllocation failed\n");
        exit(2);
    }
    newnode->empno = id;
    strcpy(newnode->empName, name);
     strcpy(newnode->designation, desg);
    newnode->next = front;
    front = newnode;
    return(front);
}                             /*End of insert() */
/* Function to display a node in a linked list */
void printNode(struct EMP *p)
{
printf("\nEmployee Details...\n");
printf("\nEmp No  : %d", p->empno);
printf("\nName           : %s", p->empName);
printf("\nDesignation    : %s\n", p->designation);
printf("-------------------------------------\n");
}                               /*End of printNode() */
/* ********************************************************/
/* Function to deleteNode a node based on employee number     */
/* front: front pointer, id: Key value                    */
/* Returns: the modified list.                            */
/* ********************************************************/
struct EMP* deleteNode(struct EMP *front, int id)
{
    struct EMP *ptr;
    struct EMP *bptr;    /* bptr is pointing to the node behind ptr */
    if (front->empno == id) 
    {
ptr = front;
printf("\nNode deleted:");
        printNode(front);
        front = front->next;
free(ptr);
        return(front);
    }
    for(ptr=front->next, bptr=front; ptr!=NULL; ptr=ptr->next, bptr=bptr->next)
    {
if (ptr->empno == id)
{
                printf("\nNode deleted:");
printNode(ptr);
bptr->next = ptr->next;
free(ptr);
return(front);
        }
    }
    printf("\nEmployee Number %d not found ", id);
    return(front);
}                             /*End of deleteNode() */
/*****************************************************************/
/* Function to search the nodes in a linear fashion based emp ID */
/* front: front pointer, key: key ID.                             */
/*****************************************************************/
void search(struct EMP *front, int key)
{
struct EMP *ptr;
for (ptr = front; ptr != NULL; ptr = ptr -> next)
{
 if (ptr->empno == key)
 {
            printf("\nKey found:");
printNode(ptr);
            return;
        }
    }
printf("\nEmployee Number %d not found ", key);
}                           /*End of search() */
/* Function to display the linked list */
void display(struct EMP *front)
{
struct EMP *ptr;
for (ptr = front; ptr != NULL; ptr = ptr->next)
{
 printNode(ptr);
}
}                         /*End of display() */
/* Function to display the menu of operations on a linked list */
void menu()
{
printf("---------------------------------------------\n");
printf("Press 1 to INSERT a node into the list       \n");
printf("Press 2 to DELETE a node from the list       \n");
printf("Press 3 to DISPLAY the list                  \n");
printf("Press 4 to SEARCH the list                   \n");
printf("Press 5 to EXIT                              \n");
printf("---------------------------------------------\n");
}                     /*End of menu() */
/* Function to select the option */
char option()
{
char choice;
printf("\n\n>> Enter your choice: ");
switch(choice=getche())
{
 case '1':
 case '2':
         case '3':
         case '4':
 case '5':   return(choice);
         default :    printf("\nInvalid choice.");
}
return choice;
}       /*End of option() */
/* The main() program begins */
int main()
{
    struct EMP *linkList;
    char name[21], desig[51];
    char choice;
    int eno;
    linkList = NULL;
    printf("\nWelcome to demonstration of singly linked list\n");
    menu();     /*Function call */
    do {
 choice = option();          /*to choose oeration to be performed */
 switch(choice)
 {
case '1': printf("\nEnter the Employee Number      : ");
scanf("%d", &eno);
printf("Enter the Employee name        : ");
fflush(stdin);
gets(name);
printf("Enter the Employee Designation : ");
gets(desig);
linkList = insert(linkList, eno, name, desig);
break;
case '2': printf("\n\nEnter the employee number to be deleted: ");
scanf("%d", &eno);
linkList = deleteNode(linkList, eno);
break;
case '3': if (linkList == NULL)
{
printf("\nList empty.");
break;
}
display(linkList);
break;
case '4': printf("\n\nEnter the employee number to be searched: ");
scanf("%d", &eno);
search(linkList, eno);
break;
case '5': break;
        }
} while (choice != '5');
}

Output of this program: 



No comments:

Post a Comment

Subscribe to: Posts (Atom)