Как отсортировать стек, используя только Push, Pop, Top, IsEmpty, IsFull?

Question

Учитывая стек S, нужно отсортировать стек, используя только Push, Pop, Top, IsEmpty, IsFull.

Ищем самое простое решение.

Отредактировано: удалено на месте. Невозможно использовать другой стек или очередь.

Answer 1

Для этой проблемы мы можем рассмотреть использование системного стека?Сделайте несколько рекурсивных вызовов.

public static void sort(Stack<Integer> s) {
    if (!s.isEmpty()) {
        Integer t = s.pop();
        sort(s);
        insert(t, s);
    }
}

private static void insert(Integer x, Stack<Integer> s) {
    if (s.isEmpty()) {
        s.push(x);
        return;
    }

    if (x < s.peek()) {
        Integer t = s.pop();
        insert(x, s);
        s.push(t);
    } else {
        s.push(x);
    }
}

Answer 2

Это можно сделать ...

---

ОК: отсортировано, хм, «на месте» только с перечисленными операциями, не нужно Top () или IsFull () или другой стек или структура данных, кроме фреймов вызова (Предположительно, весь смысл проблемы homework заключался в том, чтобы требовать рекурсивного решения.)

рубин

@a = [3, 2, 1, 6, 5, 4]

class Array
  def empty?
    return size == 0
  end
end

def sort e
  if @a.empty?
    @a.push e
    return
  end
  t = @a.pop
  if e > t
    @a.push(t).push(e)
    return
  end
  sort e
  @a.push t
end

def resort
  return if @a.empty?
  t = @a.pop
  resort
  sort t
end

p ['first ', @a]
resort
p ['final ', @a]

Answer 3

Обсуждение techInterview - сортировка по стеку

Больше псевдо, чем что-либо, но есть примеры кода и возможное решение.

Answer 4

Какие временные структуры данных вы можете использовать? С push и pop, и без временного хранилища для n элементов, доступ к данным в нижней части стека был бы невозможен без сохранения остальных - кое-где -.

Если top (эквивалент {x=pop();push(x);return x}) заменить на shift, это будет вполне выполнимо - стек изменится на fifo (shift + push; pop выйдет из употребления), и это позволит простая сортировка пузырьков по доступным в настоящее время элементам.

Answer 5

Это невозможно.

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

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

Если вам действительно нужно делать это только со стеками, просто используйте 1-2 дополнительных временных стека (я думаю, что 2 необходимы, но не уверены на 100%) и сделайте это.

Answer 6

// Java-версия

public static void sort(Stack<Integer> s){
    if(s.size() > 0){
        int tmp = s.pop();
        sort(s);
        sortFromBottom(s, tmp);
    }
}

private static void sortFromBottom(Stack<Integer> s, Integer value){
    if(s.size() == 0){
        s.add(value);
    }else{
        int tmpValue = s.peek();
        if(tmpValue < value){
            s.pop();
            sortFromBottom(s, value);
            s.push(tmpValue);
        }else{
            s.push(value);
        }
    }
}

Answer 7

К несчастью, у вас не может быть двух других стеков, тогда вы могли бы сыграть Ханойские башни в O (n) пространстве.

Answer 8

Вы не можете. Вы не можете изменить порядок содержимого стека, не удаляя элементы по определению. Также push и pop не являются операциями на месте, поэтому в основном вы просите отсортировать стек с помощью Top, IsEmpty и IsFull. IsEmpty =! IsFull. Итак, вы просите отсортировать стек с помощью Top и IsEmpty.

Answer 9

Сортировка стека без лишних пробелов совершенно невозможна. По крайней мере, не приходить мне в голову. Мы, конечно, можем использовать стек рекурсии как дополнительное пространство здесь. Приведенный ниже подход может быть полезным.

Мой подход - O (N ** 2). Здесь я перебираю стек N раз, каждый раз фиксируя i-й элемент в стеке.

Сначала исправили нижний элемент, выдвинув N элементов и нажав min_element и Вторая попытка зафиксировала 2-й элемент снизу, выдвинув N-1 элементов и нажав min_element, за исключением того, что был передан до этого И так далее.

Подробнее см. Код ниже.

    stack<int> stk;
    int sort_util(stack<int> &stk,int n,int mn)
    {
        if(n==0)
        {
            stk.push(mn);
            return mn;
        }

        int vl = stk.top();
        stk.pop();

        int fmin = sort_util(stk,n-1,min(mn,vl));

        if(fmin==vl)
            return INT_MAX;
        else
            stk.push(vl);

        return fmin;
    }

    void sort_stack(stack<int> &stk)
    {
        for(int i=stk.size();i>1;i--)
            sort_util(stk,i,stk.top());
    }

Answer 10

Пузырьковая сортировка и вставка Сортировка в Java https://github.com/BruceZu/sawdust/blob/82ef4729ee9d2de50fdceab2c8976d00f2fd3ba0/dataStructuresAndAlgorithms/src/main/java/stack/SortStack.java

 /**
  * Sort the stack using only Stack API, without using other data structure
  * Ascending from bottom to top
 */
public class SortStack<T extends Comparable<T>> {
 int sorted;

/**
 * Just Bubble Sort.
 */
private void bubble(Stack<T> s, T max) {
    if (s.empty() || s.size() == sorted) {
        s.push(max);
        sorted++;
        return; // note return
    }

    T currentTop = s.pop();
    if (max.compareTo(currentTop) < 0) {
        T tmp = max;
        max = currentTop;
        currentTop = tmp;
    }

    bubble(s, max);
    s.push(currentTop);
}

public Stack<T> sortAscending(Stack<T> s) {
    sorted = 0;
    if (s == null || s.size() <= 1) {
        return s;
    }

    while (sorted != s.size()) {
        bubble(s, s.pop());
    }
    return s;
}

/**
 * Just Insert Sort.
 */
private void insertSort(Stack<T> s) {
    if (s.empty()) {
        return;
    }
    T currentTop = s.pop();
    insertSort(s);
    insert(s, currentTop);
}

private void insert(Stack<T> s, T insert) {
    if (s.isEmpty() || insert.compareTo(s.peek()) <= 0) {
        s.push(insert);
        return;
    }

    T current = s.pop();
    insert(s, insert);
    s.push(current);
}

public Stack<T> sortAscendingByInsertSort(Stack<T> s) {
    if (s == null || s.size() <= 1) {
        return s;
    }
    insertSort(s);
    return s;
 }
}