sort/search in stack

Question

I have created a stack system in C

It takes the First Name, Last name, and an employee number and the program runs fine.

#include<stdio.h>
#include<conio.h>
#define MAX 20

struct system
{
char first_name[15];
char surname[15];
}employee[20], temp;

int stack[MAX],front=-1,top=-1;
int i;
void push_element();
void pop_element();
void display_stack();
void display_first();

int main()
{
  int option;
  printf("STACK PROGRAM");
  do
  {
   printf("\n\n 1.Push an element");
   printf("\n 2.Pop an element");
   printf("\n 3.Display stack");
   printf("\n 4.Display first");
   printf("\n 5.Display last");
   printf("\n 6.Exit");
   printf("\n Enter your choice: ");
   scanf("%d",&option);
   switch(option)
    {
      case 1: push_element();
          break;
      case 2: pop_element();
         break;
      case 3: display_stack();
         break;
      case 4: display_first();
        break;
      case 5: display_last();
        break;
      case 6: return 0;
   }

  }while(option!=6);
}

void push_element() 
{
  printf("\n Enter the first name: ");
  scanf("%s",employee[i].first_name);

  printf("\n Enter the Last name: ");
  scanf("%s",employee[i].surname);

  int num;
  printf("\n Enter the employee number: ");
  scanf("%d",&num);
    i++;
  if(front==0 && top==MAX-1)
    printf("\n You have entered more than 20. Please delete a current input to make room. ");
  else if(front==-1&&top==-1)
  {
      front=top=0;
      stack[top]=num;

  }
  else if(top==MAX-1 && front!=0)
  {
    top=0;
    stack[top]=num;
  }
  else
  {
      top++;
      stack[top]=num;
  }
}

void pop_element()
{
top--;
    return top;
}

void display_stack()
{
    int i;
    if(front==-1)
      printf("\n No Employees to display");
    else
    {
       printf("\n List of employees:\n\n ");
       printf("  Employee number    First Name    Surname\n\n");
      for(i=front;i<=top;i++)
      {
          printf("   %d \t\t     %s  \t   %s\n", stack[i], employee[i].first_name, employee[i].surname);
      }
    }
}

void display_first()
{
    int i;
    if(front==-1)
      printf("\n No Employees to display");
    else
    {
      printf("\n The first Employee in the stack is:\n\n ");
      printf("  Employee number    First Name    Surname\n\n");
      for(i=front;i<=top;i++)
        break;
      {
          printf("   %d \t\t     %s  \t   %s\n", stack[i], employee[i].first_name, employee[i].surname);
      }
    }
}

void display_last()
{
    int i;
    if(front==-1)
      printf("\n No Employees to display");
    else
    {
      printf("\n The last Employee in the stack is:\n \n");
      printf("  Employee number    First Name    Surname\n\n");
      for(i=top;i<=front;i++)
        break;
      {
          printf("   %d \t\t     %s  \t   %s\n", stack[i], employee[i].first_name, employee[i].surname);
      }
    }
}

I for the life of me cannot figure out how to sort the stack. I have tried other pieces of code and many different things, but none of them have came close to finding it But I am wanting to sort it by alphabetical order. So not by entry time or Employee number, but by the First initial of the Surname

A search function is also required for this, and to be done by Employee number.

I have looked online, and the use of sorting and searching in a stack isn't a common thing, but I required to have it.

I am not good at C and I am fairly new to it. Any tips or things that may help me greatly would be appreciated. Also I apologies for any formatting errors, I'm fairly new to programming altogether and using software.

I think the OP is puzzled by how to sort on a stack. There's no random access! The "cheating" solution may be to copy everything to an array and sort that ... or to a sorted data structure (std::set) right away! (And then back onto the stack.) — Peter - Reinstate Monica, May 10 '14 at 18:28
@PeterSchneider: The stack is implemented as an array; sorting the array will sort the stack. (Using `std::set` won't help in a C program — it becomes a C++ program at that point.) — Jonathan Leffler, May 10 '14 at 18:31
@JonathanLeffler you are right, and you are right! Geez ;-). — Peter - Reinstate Monica, May 10 '14 at 18:32

score 2 · Accepted Answer · edited May 23 '17 at 12:28

Your data structure doesn't directly record an employee number. You have the array stack which records the employee number, and the array employee which records names. You need to preserve the relationship stack[i] contains the employee number for employee[i] which means any sorting of the existing data structure has to sort two arrays in parallel. While it can be done, it is not the best way to fix the problems (and it is harder than it need be, and will require a custom sort function).

You should upgrade the data structure to include the employee number:

struct employee
{
    int  number;
    char first_name[15];
    char surname[15];
} employee[20];

Note that I've retagged the structure as struct employee (instead of struct system) since it seems more relevant to the content of the structure.

You can then use the qsort() function from the standard C library (declared in <stdlib.h>) and the techniques documented in the proposed duplicate (How to sort an array of structs in C?) to sort the data straight-forwardly. It is also easier to write your searching code.

You can also clean up the display code; you can have a single function that is passed an employee structure (or pointer to one). It will contain a single printf() statement that formats the data correctly. This saves you writing the same elaborate printf() code 3 times, making it easier to fix the formatting if (when) you need to do so. You can also avoid using tabs in the output (generally a good idea), leading to:

void print_employee(const struct employee *emp)
{
    printf("%8d   %-15s  %-15s\n", emp->number, emp->first_name, emp->surname);
}

This will produce well aligned output unless your employee number grows to more than 8 digits (in which case, change the 8 to 10 or whatever). You can also generalize one step further if you wish, passing a FILE *fp argument to the function, and using fprintf(fp, "…", …) instead of printf().

You call the function:

print_employee(&employee[i]);

You might also consider a function to print the headings since you have that function call 3 times. Alternatively, you might just have a constant string at file scope that contains the correct headings which you use in 3 places. You could do that with the print_employee() function too; have a constant string at file scope that is the format you use.

Also, in your display_first() and display_last() functions, the loops are curious. You've written:

  for(i=front;i<=top;i++)
    break;
  {
      printf("   %d \t\t     %s  \t   %s\n", stack[i], employee[i].first_name, employee[i].surname);
  }

You should realize (on review) that this is equivalent to:

i = front;
printf("   %d \t\t     %s  \t   %s\n", stack[i], employee[i].first_name, employee[i].surname);

(If front is larger than top, then i = front is the only part of the loop executed; otherwise, the break is executed; either way, after the loop, i == front.)

sort/search in stack

1 Answers1