Stos implementowany jako lista, jak to rozumieć?

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

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
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.

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?

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

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.

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

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

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.

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