Comment trier une pile en utilisant seulement Push, Pop, Top, IsEmpty, IsFull?

Donné une pile S, besoin de trier la pile en utilisant seulement Push, Pop, Top, IsEmpty, IsFull.

La recherche de solution plus simple.

Édité: Retiré à la place de la condition. Ne pouvez pas utiliser une autre pile ou file d'attente.

Simple. Pop tout dans un vecteur, de tri, de pousser tout le dos. La Version 2 de se débarrasser de la pile parce que c'est la mauvaise structure de données. Faire toute autre manière est seulement intéressante pour les devoirs à la maison.
Cela sonne comme un bien commun devoirs problème. Quel type de société ou de codage pratique vous empêcher de vous servir de stockage supplémentaire? En ne changeant pas de la principale structure de données, assurez-vous (la partie de quelqu'un d'autre de l'interface), mais ne pas être en mesure de créer de stockage secondaire? La droite. Certes, la présentation devoirs est résoluble, tandis que le vôtre ne l'est pas. Si ce n'est pas de devoirs, pourquoi êtes-vous placer ces sévères restrictions sur vous-même?
c'est juste une absurdité totale. La pile est sans aucun doute mis en œuvre à l'aide d'un tableau, trier les frikkin tableau. Je ne crois pas une minute, ce n'est pas des devoirs à faire à la question, le vote pour la fermer.
Wow il y a beaucoup de critiques de gens là-bas. Qui se soucie si c'est les devoirs, entretien, travail réel, ou juste someong s'ennuie de son esprit de se décider à écrire du code que d'aller sur une date? La question est posée. Si vous ne pensez pas qu'il vaut la peine de votre temps précieux, alors ne pas répondre, mais ne perdez pas la même précieux temps de pleurnicher et de se plaindre que vous avez dû prendre un temps précieux de votre journée pour lire au sujet d'un problème que vous ne parvenaient pas à résoudre il y a quelques années.
Eh. Mon point est. Qui donne un rip? Une question est une question. Avez-vous vraiment besoin de savoir pourquoi afin d'y répondre? Je vois une tonne de questions que pourrait être répondu simplement si la personne tapé dans Google. Ce que je ne fais pas (en général, mais ce cas semble être l'exception) est perdre du temps wonking à ce sujet. Je viens d'ignorer la question et d'avancer.

OriginalL'auteur AJ. | 2010-01-30

algorithm c data-structures

8

Il peut être fait...

Ok: triés, ahem, "sur place" avec seulement la liste ops, n'a pas besoin de Haut() ou IsFull() ou un autre de la pile ou de la structure de données autres que l'appel des cadres. (Sans doute le point de l'ensemble de l' ~~devoirs~~ problème requiert une solution récursive.)

Ruby
```
@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]
```
Ce qui fonctionne en définissant les deux fonctions de tri: resort qui ne suppose pas que la pile est déjà trié et sort qui ne. Les deux fonctionnent de manière récursive par éclater un élément off jusqu'à ce que leur but est atteint. Dans le cas de haut-niveau resort, le but est de tout supprimer et de le construire à sauvegarder en appelant sort, et sort œuvres par recursing juste assez loin pour pousser un seul élément. Je dois réfléchir à une solution, comme cela a été le point de l'exercice.
Vous êtes à l'aide de la mémoire supplémentaire; sûrement pas explicitement organisé comme une pile (plutôt caché dans la pile d'appel), mais je suis curieux de savoir si l'OP est satisfait.
Bien sûr, mais je pense que c'était prévu. Peut-être que cette solution serait évident pour certains, mais j'ai dû réfléchir un peu pour obtenir ce. C'est un plaisir de problème et je soupçonne qu'il a été conçu pour nécessiter assez bien cette solution.

OriginalL'auteur DigitalRoss

Pour ce problème, peut-on envisager d'utiliser le système de pile? Faire plusieurs appels récursifs.

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);
    }
}

OriginalL'auteur SiLent SoNG

4

techInterview Discussion - Tri sur la Pile

Plus pseudo que quoi que ce soit, mais il y a des exemples de code et des solutions possibles.

Je ne vois pas comment c'est sur place. En place signifie que vous ne créez pas de mémoire supplémentaire, sauf un petit nombre de variables en O(1) de l'espace.
L'OP a supprimé le en place à condition
Les gens ont vraiment besoin de prendre l'ensemble de l'interprétation des conditions, dans la mesure nécessaire pour résoudre le problème. Évidemment, dans ce cas, en place signifiait qu'un autre de même taille globale a été de ne pas être utilisé, forçant ainsi une solution récursive avec un temporaire de variable locale ou deux dans une image exemple. Rien n'est gagné en prenant un littéral ou trop pédant vue sur le problème de l'évidence-involontaire à l'extrême permettant pas de solution.
Si la question voulait un appel récursif à répondre, puis de l'OMI, il est plus logique de le dire, plutôt que d'imposer le très déroutant condition "doit mettre en œuvre ce d'une manière qui, dans un langage impératif, est presque garanti d'être pire dans tous seul moyen que d'utiliser une deuxième structure de données". Bien sûr, c'est une plainte concernant l'interview casse-têtes en général, plutôt que de cette question en particulier 🙂

OriginalL'auteur Anthony Forloney
3

Ce n'est pas possible.

Que cela arrive parce que vous ne pouvez pas parcourir la pile, car il doit être en place (vous pouvez, si vous utilisez la mémoire supplémentaire). Donc, si vous ne pouvez pas parcourir la pile tu ne peux même pas comparer deux éléments de la pile. Une sorte, sans la comparer aurait besoin de plus de mémoire, de sorte que ne peut pas être utilisé.

Aussi im sûr que c'est pas des devoirs, car je ne pense pas qu'un enseignant ne devrait vous donner un problème qui ne peut pas être résolu.

Si vous avez vraiment le faire uniquement avec des piles, il suffit d'utiliser 1-2 supplémentaire temporaire des piles (je pense que les 2 sont nécessaires, mais pas sûr à 100%) et de le faire.

Sauf, je l'ai fait. Sans doute une solution récursive était le but de la solution, même si cela nécessite certainement une sorte de derrière-le-scènes de la structure de données. Je pense qu'il est préférable de gérer ce genre de problème par venir avec une solution qui répond aux critères. Je doute que le prof va être trop impressionné par "c'est impossible".
Comme vous l'avez dit, vous êtes à l'aide d'un "behind-the-scenes" structure de données, qui est la pile d'appel. Je devrais peut-être mieux dire, il n'est pas possible à l'itération, mais possible avec la récursivité 🙂 . Edit: ma réponse quand il voulait une solution (maintenant, il a changé le sujet), ce qui n'est pas l'un avec la récursivité, parce que, pour être sur place à l'espace utilisé doit être une constante (ce n'est pas parce que vous êtes en utilisant tout l'espace de pile que vous voulez).

OriginalL'auteur George
3

Ce que les structures de données pouvez-vous utiliser?
Avec push et pop, et pas de stockage temporaire pour n éléments, l'accès aux données près du bas de la pile serait impossible sans stocker le reste -quelque part-.

Si top (equiv à {x=pop();push(x);return x}) a été remplacé par shift, il serait tout à fait faisable - la pile de changement en fifo (maj+push, pop tomberait en désuétude) et il devrait permettre un facile bubblesort sur les éléments disponibles.

OriginalL'auteur SF.
2

Vous ne pouvez pas. Vous ne pouvez pas réorganiser le contenu d'une pile sans la suppression d'éléments, par définition. Aussi push et pop ne sont pas en place, donc, fondamentalement, vous demandez à trier une pile avec le Haut, IsEmpty et IsFull. ~~IsEmpty = !IsFull. Si vous demandez à trier une pile de Haut et IsEmpty.~~

Err, votre déclaration sur IsEmpty et IsFull est faux (pour la plupart des piles). Si la pile n'est pas vide, il n'est pas nécessairement complète (sauf si c'est un élément de la pile). 🙂
Pourquoi ne pas push et pop en place des opérations?
ainsi, pour avoir accès à la nième élément que vous avez besoin de la pop n-1 éléments. le n dépend de la taille de saisie il n'est donc pas constante la taille de l'allocation de la mémoire n'est donc pas en place.
Je pense que c'est possible de le faire "en place", pour une définition. Voir mon posté réponse et mon commentaire sur George de la réponse.

OriginalL'auteur Chris H
2

Si mal que vous ne pouvait pas avoir les deux autres piles, vous pourriez avoir joué le Tours de Hanoï en O(n) de l'espace.

OriginalL'auteur Albin Sunnanbo

//Une version de 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);
        }
    }
}

OriginalL'auteur Jiaji Li

De Tri à bulles et d'Insérer de Tri en 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;
}
}

OriginalL'auteur Bruce Zu

0

Tri d'une pile sans espace supplémentaire est tout à fait pas une possibilité .
Au moins pas de venir à mon esprit sain .
Nous pouvons sûrement utiliser la récursivité de la pile comme un espace supplémentaire ici .
Ci-dessous l'approche pourrait être utile .

Mon approche est O(N**2) . Ici je suis une itération sur la pile N fois, à chaque fois que la fixation de la iième élément dans la pile .

Tout d'abord fixe le fond de l'élément de popping out de N éléments et en poussant min_element et dans
Deuxième essai fixe le 2ème élément de bas en sautant N-1 éléments et en poussant min_element à l'exception de l'une poussée avant cette
Et ainsi de suite .

Consulter le code ci-dessous pour plus de détails .
```
    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());
}
```
OriginalL'auteur dhruvsharma

Vous devez vous connecter pour publier un commentaire.

Il peut être fait...

Ruby