Как отсортировать стек, используя только операции со стеком?

Question

Я нашел этот вопрос в Интернете.

Учитывая стек S, напишите программу на C для сортировки стека (в порядке возрастания).Нам не разрешается делать какие-либо предположения о том, как реализован стек.Используются только следующие функции:

Push
Pop
Top
IsEmpty
IsFull

Я думаю, мы можем построить кучу и отсортировать ее.Какое оптимальное решение для этого?

Answer 1

Если предположить, что единственная структура данных, разрешенная здесь, это стек, то вы можете использовать 2 стека.

Итерируйте, пока исходный стек не станет пустым, и на каждой итерации извлекайте элемент из исходного стека, в то время как верхний элемент во втором стеке больше, чем удаленный элемент, извлекайте второй стек и помещайте его в исходный стек. Теперь вы можете переместить элемент, который вы изначально извлекли из исходного стека, во второй стек.

Временная сложность этого подхода составляет O (N ^ 2).

C-код для реализации этого алгоритма будет (извините мои ржавые C-навыки):

void SortStack(struct Stack * orig_stack)
{
  struct Stack helper_stack;
  while (!IsEmpty(orig_stack))
  {
    int element = Pop(orig_stack);
    while (!IsEmpty(&helper_stack) && Top(&helper_stack) < element)
    {
      Push(orig_stack, Pop(&helper_stack));
    }
    Push(&helper_stack, element);
  }
  while (!IsEmpty(&helper_stack))
  {
    Push(orig_stack, Pop(&helper_stack));
  }
}

Answer 2

Учитывая эти операции стека, вы можете написать рекурсивную вставку сортировки.

void sort(stack s) {
    if (!IsEmpty(s)) {
        int x = Pop(s);
        sort(s);
        insert(s, x);
    }
}

void insert(stack s, int x) {
    if (!IsEmpty(s)) {  
        int y = Top(s);
        if (x < y) {
            Pop(s);
            insert(s, x);
            Push(s, y);
        } else {
            Push(s, x);
        }
    } else {
        Push(s, x); 
    }
}

Answer 3

Это можно сделать рекурсивно, используя тот же стек. O (N ^ 2) Я кодировал его в C ++, но преобразование в C тривиально. Мне просто нравятся шаблоны, а вы пометили свой вопрос как C ++

template<typename T>
void Insert(const T& element, Stack<T>& stack)
{
  if(element > stack.Top())
  {
    T top = stack.Pop();
    Insert(element, stack);
    stack.Push(top);
  }
  else
  {
    stack.Push(element);
  }
}

template<typename T>
void StackSort(Stack<T>& stack)
{
  if(!stack.IsEmpty())
  {
    T top = stack.Pop();
    StackSort(stack);
    Insert(top, stack);    
  }    
}

Отредактировано, чтобы вернуть мой голос! :))

Answer 4

Сортировка блинов - еще один интересный способ сделать это: http://en.wikipedia.org/wiki/Pancake_sorting#cite_note-4.

Answer 5

Модифицированный код из Ответ T33C
(переданный Сванте исправил языковой тег с c ++ до c ):
stack.top() canпроверяется только если !stack.empty()

void insert(int element, stack<int> &stack) {
    if (!stack.empty() && element > stack.top()) {
        int top = stack.top();
        stack.pop();
        insert(element, stack);
        stack.push(top);
    }
    else {
        stack.push(element);
    } 
}

void sortStack(stack<int> & stack) {
    if (!stack.empty()) {
        int top = stack.top();
        stack.pop();
        sortStack(stack);
        insert(top, stack);
    }
}

Answer 6

3 стека сортировки с использованием многофазной сортировки слиянием

Это должен быть самый быстрый способ реализовать сортировку в 3 стека. Цель состоит в том, чтобы получить последовательность в порядке возрастания, когда элементы извлекаются из отсортированного стека.

Статья Wiki для многофазной сортировки слиянием (с использованием массивов):

http://en.wikipedia.org/wiki/Polyphase_merge_sort

Пример кода C ++ для трехфазной сортировки стека, с использованием указателей, указателя в качестве указателя стека для каждого стека и указателя на конец каждого прогона и конец каждого стека. Указатель размера серии используется для отслеживания того, когда размер серии увеличивается или уменьшается в середине стека. Флаг нисходящей последовательности используется для отслеживания, являются ли последовательности нисходящими или восходящими при передаче данных между стеками. Он инициализируется в начале и затем чередуется после объединения каждой пары прогонов.

typedef unsigned int uint32_t;

static size_t fibtbl[48] =
    {        0,         1,         1,         2,         3,         5,
             8,        13,        21,        34,        55,        89,
           144,       233,       377,       610,       987,      1597,
          2584,      4181,      6765,     10946,     17711,     28657,
         46368,     75025,    121393,    196418,    317811,    514229,
        832040,   1346269,   2178309,   3524578,   5702887,   9227465,
      14930352,  24157817,  39088169,  63245986, 102334155, 165580141,
     267914296, 433494437, 701408733,1134903170,1836311903,2971215073};

// binary search: return index of largest fib() <= n
size_t flfib(size_t n)
{
size_t lo = 0;
size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
    while((hi - lo) > 1){
        size_t i = (lo + hi)/2;
        if(n < fibtbl[i]){
            hi = i;
            continue;
        }
        if(n > fibtbl[i]){
            lo = i;
            continue;
        }
        return i;
    }
    return lo;
}

// poly phase merge sort array using 3 arrays as stacks, a is source
uint32_t * ppmrg3s(uint32_t a[], uint32_t b[], uint32_t c[], size_t n)
{
    if(n < 2)
        return a+n;
    uint32_t *asp = a;                  // a stack ptr
    uint32_t *aer;                      // a end run
    uint32_t *aes = a + n;              // a end
    uint32_t *bsp = b + n;              // b stack ptr
    uint32_t *ber;                      // b end run
    uint32_t *bes = b + n;              // b end
    uint32_t *csp = c + n;              // c stack ptr
    uint32_t *ces = c + n;              // c end
    uint32_t *rsp = 0;                  // run size change stack ptr
    size_t ars = 1;                     // run sizes
    size_t brs = 1;
    size_t scv = 0-1;                   // size change increment / decrement
    bool dsf;                           // == 1 if descending sequence
    {                                   // block for local variable scope
        size_t f = flfib(n);            // fibtbl[f+1] > n >= fibtbl[f]
        dsf = ((f%3) == 0);             // init compare flag
        if(fibtbl[f] == n){             // if exact fibonacci size, move to b
            for(size_t i = 0; i < fibtbl[f-1]; i++)
                *(--bsp) = *(asp++);
        } else {                        // else move to b, c
            // update compare flag
            dsf ^= (n - fibtbl[f]) & 1;
            // move excess elements to b
            aer = a + n - fibtbl[f];
            while (asp < aer)
                *(--bsp) = *(asp++);
            // move dummy count elements to c
            aer = a + fibtbl[f - 1];
            while (asp < aer)
                *(--csp) = *(asp++);
            rsp = csp;                  // set run size change ptr
        }
    }                                   // end local variable block
    while(1){                           // setup to merge pair of runs
        if(asp == rsp){                 // check for size count change
            ars += scv;                 //   (due to dummy run size == 0)
            scv = 0-scv;
            rsp = csp;
        }
        if(bsp == rsp){
            brs += scv;
            scv = 0-scv;
            rsp = csp;
        }
        aer = asp + ars;                // init end run ptrs
        ber = bsp + brs;
        while(1){                       // merging pair of runs
            if(dsf ^ (*asp <= *bsp)){   // if a <= b
                *(--csp) = *(asp++);    //   move a to c
                if(asp != aer)          //   if not end a run
                    continue;           //     continue back to compare
                do                      //   else move rest of b run to c
                    *(--csp) = *(bsp++);
                while (bsp < ber);
                break;                  //     and break
            } else {                    // else a > b
                *(--csp) = *(bsp++);    //   move b to c
                if(bsp != ber)          //   if not end b run
                    continue;           //     continue back to compare
                do                      //   else move rest of a run to c
                    *(--csp) = *(asp++);
                while (asp < aer);
                break;                  //     and break
            }
        }                               // end merging pair of runs
        dsf ^= 1;                       // toggle compare flag
        if(bsp == bes){                 // if b empty
            if(asp == aes)              //   if a empty, done
                break;
            std::swap(bsp, csp);        //   swap b, c
            std::swap(bes, ces);
            brs += ars;                 //   update run size
        } else {                        // else b not empty
            if(asp != aes)              //   if a not empty
                continue;               //     continue back to setup next merge
            std::swap(asp, csp);        //   swap a, c
            std::swap(aes, ces);
            ars += brs;                 //   update run size
        }
    }
    return csp;                          // return ptr to sorted array
}

Пример кода Java для сортировки с использованием пользовательского стекового класса (xstack), который включает в себя функцию подкачки.

static final int[] FIBTBL =
{        0,         1,         1,         2,         3,         5,
         8,        13,        21,        34,        55,        89,
       144,       233,       377,       610,       987,      1597,
      2584,      4181,      6765,     10946,     17711,     28657,
     46368,     75025,    121393,    196418,    317811,    514229,
    832040,   1346269,   2178309,   3524578,   5702887,   9227465,
  14930352,  24157817,  39088169,  63245986, 102334155, 165580141,
 267914296, 433494437, 701408733,1134903170,1836311903};

// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
    while((hi - lo) > 1){
        int i = (lo + hi)/2;
        if(n < FIBTBL[i]){
            hi = i;
            continue;
        }
        if(n > FIBTBL[i]){
            lo = i;
            continue;
        }
        return i;
    }
    return lo;
}

// poly phase merge sort using 3 stacks
static void ppmrg3s(xstack a, xstack b, xstack c)
{
    if(a.size() < 2)
        return;
    int ars = 1;                        // init run sizes
    int brs = 1;
    int asc = 0;                        // no size change
    int bsc = 0;
    int csc = 0;
    int scv = 0-1;                      // size change value
    boolean dsf;                        // == 1 if descending sequence
    {                                   // block for local variable scope
        int f = flfib(a.size());        // FIBTBL[f+1] > size >= FIBTBL[f]
        dsf = ((f%3) == 0);             // init compare flag
        if(FIBTBL[f] == a.size()){      // if exact fibonacci size,
            for (int i = 0; i < FIBTBL[f - 1]; i++) { //  move to b
                b.push(a.pop());
            }
        } else {                        // else move to b, c
            // update compare flag
            dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
            // i = excess run count
            int i = a.size() - FIBTBL[f];
            // j = dummy run count
            int j = FIBTBL[f + 1] - a.size();
            // move excess elements to b
            do{
                b.push(a.pop());
            }while(0 != --i);
            // move dummy count elements to c
            do{
                c.push(a.pop());
            }while(0 != --j);
            csc = c.size();
        }
    }                                   // end block
    while(true){                        // setup to merge pair of runs
        if(asc == a.size()){            // check for size count change
            ars += scv;                 //   (due to dummy run size == 0)
            scv = 0-scv;
            asc = 0;
            csc = c.size();
        }
        if(bsc == b.size()){
            brs += scv;
            scv = 0-scv;
            bsc = 0;
            csc = c.size();
        }
        int arc = ars;                  // init run counters
        int brc = brs;
        while(true){                    // merging pair of runs
            if(dsf ^ (a.peek() <= b.peek())){
                c.push(a.pop());        // move a to c
                if(--arc != 0)          // if not end a
                    continue;           //   continue back to compare
                do{                     // else move rest of b run to c
                    c.push(b.pop());
                }while(0 != --brc);
                break;                  //   and break
            } else {
                c.push(b.pop());        // move b to c
                if(0 != --brc)          // if not end b
                    continue;           //   continue back to compare
                do{                     // else move rest of a run to c
                    c.push(a.pop());
                }while(0 != --arc);
                break;                  //   and break
            }
        }                               // end merging pair of runs
        dsf ^= true;                    // toggle compare flag
        if(b.empty()){                  // if end b
            if(a.empty())               //   if end a, done
                break;
            b.swap(c);                  //   swap b, c
            brs += ars;
            if (0 == asc)
                bsc = csc;
        } else {                        // else not end b
            if(!a.empty())              //   if not end a
                continue;               //     continue back to setup next merge
            a.swap(c);                  //   swap a, c
            ars += brs;
            if (0 == bsc)
                asc = csc;
        }
    }
    a.swap(c);                          // return sorted stack in a
}

Answer 7

Поскольку ничего не сказано о том, сколько дополнительных стеков можно использовать, я предполагаю, что любое количество стеков можно использовать для максимально эффективного решения проблемы сортировки.Теперь предположим, что это была нормальная проблема сортировки.Тогда как вы можете решить это?(Подсказка: сортировка слиянием)

Выполните обычную сортировку слиянием в стеке, используя вспомогательные стеки.Временная сложность - N * log (n).

Answer 8

class Program
{
    static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(8);
        stack.Push(5);
        stack.Push(3);
        stack.Push(4);
        stack.Push(7);
        stack.Push(9);
        stack.Push(5);
        stack.Push(6);
        Stack<int> tempStack = new Stack<int>();
        while (stack.Count > 0)
        {
            int temp = stack.Pop();
            while(tempStack.Count>0 && tempStack.Peek() > temp)
            {
                stack.Push(tempStack.Pop());
            }
            tempStack.Push(temp);
        }
        while (tempStack.Count > 0)
        {
            Console.Write(tempStack.Pop() + " ");
        }
        Console.ReadLine();
    }
}

Answer 9

Я думаю, что сортировка пузырьков может работать в стеке с рекурсией.

   void sortStack(stack<int>& st){
        bool flag = true;
        int n = st.size();
        for(int i = 1; i <= n - 1 && flag; i++){
            flag = false;
            bubbleSortStack(st, flag, i);
        }
    }
    void bubbleSortStack(stack<int>& st, bool& flag, int endSize){
        if(st.size() == endSize)
            return;
        int val = st.top();
        st.pop();
        if(val > st.top()){
            flag = true;
            int tmp = st.top();
            st.push(val);
            val = tmp;
        }
        bubbleSortStack(st, flag);
        st.push(val);
    }

Answer 10

Игра из трех стеков

С тремя стеками S (исходный стек, стек с несортированными элементами), A, B вы можете начать играть в игру, подобную сортировке слиянием.

Я думаюясно, что если вы упорядочили элементы на A и B (в одном и том же направлении, оба восходящие или оба нисходящие), вы можете использовать S для объединения сортировки A и B, а затем переместить результат, например, в B.

Тот факт, что у вас есть элементы на A, B или S, не лишает вас возможности использовать A, B или S для слияния (если у вас есть маркер текущего размера A,B и S, чтобы вы не промахнулись).Если ваша процедура переносит упорядоченные элементы на S, то нет смысла использовать A и B для удаления отсортированной части в A или B в любом понравившемся вам направлении: вы можете поместить ее в обратном порядке непосредственно в A или B или, например,поместите все элементы в A и затем снова поверните в B.

Предположим, что у вас есть 4 отсортированных элемента на A, 16 на B и несколько несортированных элементов на S.

A.push (S.pop) и теперь создайте отсортированное по 2 элементам слияние.Снова B.push (S.pop) и создайте еще одно 2-элементное сортированное слияние.Если слияния не разделены и / или не находятся в одном и том же направлении, вы можете манипулировать элементами так, как вам нравится, пока вы не достигнете 4-элементного сортированного слияния на B (или даже S).Теперь выполняйте слияние исходного сортированного слияния из 4 элементов из A и той части на B, пока не достигните сортированного слияния из 8 элементов.

Вы повторяете все, пока не создадите еще одно сортированное слияние из 8 элементов.Вы размещаете его в правильном порядке на B (или S) и объединяетесь, чтобы получить сортировку с 16 элементами.Теперь вы помещаете его в A (или S) и объединяете с 16-элементным слиянием, которое у нас было все время на B.

Оптимизированная реализация сложна, так как вам нужно уменьшить перемещение (возврат) отсортированного слияния изодин стек в другой.Однако, если вы исправите и решите, для чего собираетесь использовать A, B и S, и, например, заставите: A содержать меньшую и B большую объединенную часть в порядке убывания, тогда алгоритм будет проще.

Фактто, что вам нужно переместить некоторые верхние элементы из одного стека в другой, добавляет постоянный коэффициент сложности, но он никогда не превышает 2. Кроме того, сложность равна n * log (n) (вы достигнете слияния, отсортированного по 2n элементамобъединяя отсортированные по n-элементам слияния, и объединение требует не более 2n шагов.)

Реализация на C # (другие подобные языки очевидны)

    void Stacking(Stack<int> sourceStack, Stack<int> mainStack, Stack<int> childStack, int n)
    {
        if (n == 0) return;

        if (n == 1)
        {
            mainStack.Push(sourceStack.Pop());
            return;
        }

        int mainSize = n/2;
        int childSize = n - n/2;

        Stacking(sourceStack, mainStack, childStack, mainSize);
        Stacking(sourceStack, childStack, mainStack, childSize);

        while (true)
        {
            while (mainSize > 0 && mainStack.Peek() >= childStack.Peek())
            {
                sourceStack.Push(mainStack.Pop());
                mainSize--;
            }

            if (mainSize == 0) break;

            while (childSize > 0 && childStack.Peek() >= mainStack.Peek())
            {
                sourceStack.Push(childStack.Pop());
                childSize--;
            }

            if (childSize == 0) break;
        }

        while (mainSize > 0)
        {
            sourceStack.Push(mainStack.Pop());
            mainSize--;
        }

        while (childSize > 0)
        {
            sourceStack.Push(childStack.Pop());
            childSize--;
        }

        for (int i = 0; i < n; i++)
            mainStack.Push(sourceStack.Pop());
    }

    void SortStack(Stack<int> sourceStack)
    {
        int n = sourceStack.Count();

        // possible optimization: if (n < 2) return;

        Stack<int> mainStack = new Stack<int>();
        Stack<int> childStack = new Stack<int>();

        Stacking(sourceStack, mainStack, childStack, n);

        for (int i = 0; i < n; i++)
            sourceStack.Push(mainStack.Pop());
    }

Игра журнала (n) stacks

Вышеуказанная процедура может быть упрощена, если вам разрешено использовать не более log (n) стеков.Это количество стеков не означает, что вы когда-либо будете использовать дополнительное пространство, большее, чем порядок n.Вы просто отмечаете стеки, которые будут использоваться для объединения 1, 2, 4 ... элементов.В этом случае вы не заботитесь о порядке, так как объединяющиеся части 2 ^ n всегда будут отсортированы в одном направлении.Однако это решение позволяет обойти только тот факт, что вы ограничены в использовании операций push и pop;кроме этого это эквивалентно сортировке слиянием во всех аспектах.По сути, если количество стеков не ограничено, вы также можете легко эмулировать быструю сортировку.