Как эффективно сортировать рекурсивно определенный стек?

Question

Это не вопрос домашней работы. Я просто пытаюсь реализовать рекурсивно определенный стек. Вопрос исключительно из любопытства. Есть ли эффективный метод, помимо копирования элементов из массива Stack в массиве, сортировки и повторного нажатия их на стек?

Пожалуйста, предоставьте алгоритм или код (я знаю C/C++, Java), если у вас есть предложения.

определение стека:

class Stack<E> 
{ 
    E element; 
    Stack<E> topOfSubStack; 
} 

Answer 1

Предполагая, что доступ к стеке не является последовательным (без итераторов доступа), то алгоритм похож на тот, которые используются для сортировки списков, таких как станд :: Список :: сортировать бы Работа. Пример кода C, который использует глобальный статический массив указателей для отображения (он может быть выделен, а затем передан как параметр). Для C++ массив и функции могут быть частью класса.

#define NUMLISTS 32      /* number of lists */ 
typedef unsigned long long UI64; 

typedef struct NODE_{ 
struct NODE_ * next; 
UI64 data; 
}NODE; 

typedef struct LIST_{ 
NODE *first; 
}LIST; 

/*----------------------------------------------------------------------*/ 
/*  data               */ 
/*----------------------------------------------------------------------*/ 
static LIST aList[NUMLISTS];   /* array of lists */ 

/*----------------------------------------------------------------------*/ 
/*  SortList              */ 
/*----------------------------------------------------------------------*/ 
void SortList(LIST *pList) 
{ 
NODE * pNode; 
LIST mList;        /* merged list */ 
int i; 

    if(pList == NULL)     /* check for null ptr */ 
     return; 

    /* merge nodes into aList[] */ 
    while(NULL != (pNode = GetFirstNode(pList))){ 
     MergeNode(pNode); 
    } 

    /* find 1st non empty aList[] */ 
    for(i = 0; (i < NUMLISTS) && (aList[i].first == NULL); i++); 
    if(i >= NUMLISTS){     /* if all empty */ 
     pList->first = NULL;   /* return null list */ 
     return; 
    } 

    pList->first = aList[i].first;  /* plist = aList[i] */ 
    aList[i].first = NULL;    /* clear aList[i] (optional) */ 

    for(i++; i < NUMLISTS; i++){  /* merge remaining aList[] */ 
     if(aList[i].first != NULL){ 
      MergeLists(&mList, &aList[i], pList); 
      pList->first = mList.first; 
     } 
    } 
} 

/*----------------------------------------------------------------------*/ 
/*  MergeNode merge a node into the array of lists    */ 
/*----------------------------------------------------------------------*/ 
void MergeNode(NODE *pNode) 
{ 
LIST sList;        /* source list */ 
LIST mList;        /* merged list */ 
int i; 

    if(pNode == NULL)     /* return if null ptr */ 
     return; 

    sList.first = pNode;    /* src list = node */ 

    /* merge into array */ 
    for(i = 0; (i < NUMLISTS) && (aList[i].first != NULL); i++){ 
     MergeLists(&mList, &aList[i], &sList); 
     sList.first = mList.first; 
    } 
    if(i == NUMLISTS)     /* update array */ 
     i--; 
    aList[i].first = sList.first; 
} 

/*----------------------------------------------------------------------*/ 
/*  MergeLists dst = merge(src1, src2)        */ 
/*----------------------------------------------------------------------*/ 
void MergeLists(LIST *plDst, LIST *plSrc1, LIST *plSrc2) 
{ 
NODE **ppDst, *pSrc1, *pSrc2;   /* node ptrs */ 

    ppDst = &(plDst->first); 
    pSrc1 = GetFirstNode(plSrc1);  /* init ptrs to nodes */ 
    pSrc2 = GetFirstNode(plSrc2); 

    while(1){ 
     if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */ 
      *ppDst = pSrc2; 
      ppDst = &(pSrc2->next); 
      /* if end of src2, dst = rest of src1 */ 
      if(NULL == (pSrc2 = GetFirstNode(plSrc2))){ 
       pSrc1->next = plSrc1->first; 
       *ppDst = pSrc1; 
       plSrc1->first = NULL; 
       break; 
      } 
     } else {      /* src1 <= src2 */ 
      *ppDst = pSrc1; 
      ppDst = &(pSrc1->next); 
      /* if end of src1, dst = rest of src2 */ 
      if(NULL == (pSrc1 = GetFirstNode(plSrc1))){ 
       pSrc2->next = plSrc2->first; 
       *ppDst = pSrc2; 
       plSrc2->first = NULL; 
       break; 
      } 
     } 
    } 
}