Stos implementowany jako lista, jak to rozumieć?

Odpowiedz Nowy wątek
2019-11-05 15:17
0

Cześć, mam zadanie do wykonania, a nie do końca rozumiem o co chodzi w poleceniu, konkretnie chodzi mi o "stos implementowany jako listę", czy mógłby mi ktoś to wyjaśnić? :)

Zadanie 20
Napisać program odwracający kolejność łańcuchów tekstu podawanych z wejścia. Program ma zapamiętywać wprowadzane
dane wykorzystując stos implementowany jako listę. Po wprowadzeniu łańcucha pustego ma zostać wyświetlona
odpowiedź. Obsłużyć wyjątki.
Do przechowywania danych na liście należy wykorzystać strukturę:

class Element
{
string Klucz;
public Element next;
public Element(string Klucz)
{
this.Klucz = Klucz;
}
}

Hej! Twój post prawdopodobnie zawiera niesformatowany kod. Użyj znaczników ``` aby oznaczyć, co jest kodem, będzie łatwiej czytać. (jestem botem, ta akcja została wykonana automatycznie, prawdopodobieństwo 0.9981076) - Tasmanian Devil 2019-11-05 15:28

Pozostało 580 znaków

2019-11-05 15:21
2

Stos ma co najmniej trzy metody push, pop, i top.
Tu masz pseudokod z wikipedii z artykułu Stos

Class Element_stosu
    poprzednik       // Wskaźnik na poprzedni element stosu 
    wartosc          // Wartość przechowywana w danym elemencie stosu

Class Stos
    Top = NULL       // Wierzchołek stosu 

    Push(Wartosc)    // dodanie elementu 
       nowy = new element stosu 
       nowy.wartosc = Wartosc
       nowy.poprzednik = Top
       Top = nowy 
    Pop()            // ściągnięcie elementu
       wartosc = Top.wartosc 
       pomocnik = Top
       Top = Top.poprzednik
       usun(pomocnik) // usunięcie ściągniętego wierzchołka
       return wartosc

Pozostało 580 znaków

2019-11-05 15:53
1

Masz stworzyć interface stosu (domyślam się, że pisząc "stos" bez dodatkowych wyjaśnień, chodzi Ci o LIFO), jak powyżej, a, strukturą działająca "under the hood" (do której/z której Będziesz Dodawał/Ściągał elementy) ma być Linked List.


Pozostało 580 znaków

2019-11-05 15:57
0

@Kamil Żabiński: @lion137

Dzięki, za wyjaśnienie :)
Pytanie tylko, po co wspomniano o tej liście w poleceniu, nie rozumiem jej znaczenia w kontekście tego polecenia?

Pozostało 580 znaków

2019-11-05 16:00
1

Czemu na liście?
Jakbyś @Darek554 spojrzał w artykuł to byś zobaczył że są dwa implementacje, na statycznej tablicy i na liście właśnie


Dzięki :) - Darek554 2019-11-05 16:03

Pozostało 580 znaków

2019-11-05 16:03
1

Dlatego, że Masz napisać Abstract Data Type (w linku jest nawet wspomniany stos), czyli interfejs stosu, a wewnętrznie operujący na liście, można też uzyć tablicy dynamicznej, stałej, cyklicznej, drzewa, sterty (a czemu nie)).
PS Rozpędziłem się za bardzo:); wszystkie struktury mające push, pop i isEmpty gorsze niż ~const sa bez sensu.


edytowany 1x, ostatnio: lion137, 2019-11-05 17:06

Pozostało 580 znaków

2019-11-05 18:53
0

@lion137: @Kamil Żabiński

Miałbym prośbę, czy moglibyście mi napisać, czy dobrze naskrobałem kod, tzn. czy napisałem go zgodnie z założeniami zadania? :-)

using System;
using System.Collections.Generic;
using System.Text;

namespace Zad._20
{
    class Element
    {
        public String wartosc;
        public Element poprzedni;

        public Element(String klucz) {
            this.wartosc = klucz;
        }
    }
}
using System;
using System.Collections.Generic;
using System.Text;

namespace Zad._20
{
    class Stos
    {
        private Element wierzcholek;

        public Stos()  {
            wierzcholek = null;
        }

        public void Push(Element e)  {
            e.poprzedni = wierzcholek;
            wierzcholek = e;
        }

        public void Pop()  {
            Element tmp = wierzcholek;
            wierzcholek = wierzcholek.poprzedni;
        }

        public void Print()    {
            while(wierzcholek != null) {
                Console.WriteLine(wierzcholek.wartosc);
                wierzcholek = wierzcholek.poprzedni;
            }  
        }
    }
}

Pozostało 580 znaków

2019-11-05 19:23
0

Czy to się w ogóle kompiluje?:) Nie tak, Twoje class Element, to ma być Linked Lista ze swoimi metodami: pushi pop, a stos, używając jej, jako struktury do przechowywania znaków, ma implementować swój interfejs, tez składający się z tych metod + isEmpty.

EDIT: @Darek554 Zignoruj ten post:) element nie musi mieć swoich metod, tak jak Zrobiłeś może być, choć nie wiem czy jest poprawnie.


edytowany 5x, ostatnio: lion137, 2019-11-06 12:31

Pozostało 580 znaków

2019-11-05 20:42
0

@lion137:
Kompiluje sie i dziala ;)

Moglbys mi napisac pare przykladowych linijek jakby to mialo wygladac?
Niestety nie widze tego.
Mam w klasie Element stworzyc kolekcje List<element> itd.?
Serio juz nie mysle dzisiaj xd

Jak to nie myślę dzisiaj, my[programiści] zawsze myślimy, chyba, że jesteśmy martwi:-) - lion137 2019-11-05 21:07

Pozostało 580 znaków

2019-11-06 13:01
1

@Darek554:

czy dobrze naskrobałem kod, tzn. czy napisałem go zgodnie z założeniami zadania?

Można odpowiedzieć, że Idziesz w dobrą stronę, ale stos to jeszcze nie jest:).
push jest źle zaimplementowana: bierze jako argument obiekt klasy Element (!?!), przecież użytkownik będzie chciał sobie wrzucać i ściągać ze stosu stringi;
pop nie zwraca elementu, nie Masz też innego sposobu dostania się do szczytu stosu, więc jak user ma użyć tych stringów, które sobie tam wrzucił? Brakuje metody sprawdzającej czy stos jest pusty, isEmpty, która jest niezbędna do używania strukturki: ściągaj ze stosu dopóki nie pusty, jesli pusty to coś tam, etc... Mozna też dołożyć metodę peek, która nie zrzuca ze stosu, tylko "podgląda" pierwszy element. Acha, cały świat nazywa wskaźnik do następnego elementu listy next, a u Ciebie poprzedni WTF? Przeanalizuj sobie taki przykładowy kod stosu:

using System;
class LinkedListStack{

  internal Element head;

  internal class Element {
    internal string key;
    public Element next;
    public Element(string e) {
      this.key = e;
    }
  }

  public LinkedListStack() {
    head = null;
  }

  public void push(string e) {
    Element head_old = head;
    head = new Element(e);
    head.next = head_old;
  }

  public string peek() {
    // exception if empty!
    return head.key;
  }

  public string pop() {
    // exception if empty!
    string e = head.key;
    head = head.next;
    return e;
  }

  public bool isEmpty() {
    return head == null;
  }

  public override string ToString() {
    if (this.isEmpty()) return "()";
    string s = "";
    Element tmp = this.head;
    while (tmp != null) {
      s += tmp.key + " ";
      tmp = tmp.next;
    }
    return s;
  }
}

class MainClass {
  public static void Main (string[] args) {
    LinkedListStack s = new LinkedListStack();
    s.push("A");
    s.push("B");
    Console.WriteLine (s.isEmpty());
    Console.WriteLine (s);
    s.pop();
    s.pop();
    Console.WriteLine (s.isEmpty());
    Console.WriteLine (s);
    s.push("B");
    s.push("A");
    Console.WriteLine (s.isEmpty());
    Console.WriteLine (s);
    Console.WriteLine (s.peek());
    }
} 

EDIT: Drobna zmiana, nadpisane ToString, zamiast printStack.


edytowany 1x, ostatnio: lion137, 2019-11-06 20:11

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0