Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.81/42: Рейтинг темы: голосов - 42, средняя оценка - 4.81
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
1

Реализация стека FIFO и LIFO

27.06.2011, 00:20. Просмотров 7904. Ответов 10
Метки нет (Все метки)

Собственно, если у кого-нить будет время посмотреть мои реализации FIFO и LIFO стеков, и высказать замечания, буду очень признателен =)
Обычный FIFO стек, универсальный вроде как, вроде правильно с шаблонами разобрался:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
template <class T>
class Stack
{
private:
    struct StackEl;
    StackEl *top;
public:
    Stack();
    Stack(T el);
    ~Stack();
    void Push(const T& el);
    T Pop();
};
 
template <class T> struct Stack<T>::StackEl
{
    T data;
    StackEl *prev;
};
 
template <class T> Stack<T>::Stack():top(NULL)
{
}
 
template <class T> Stack<T>::Stack(T el)
{
    StackEl * temp = new StackEl;
    temp->data = el;
    temp->prev = NULL;
    top = temp;
}
 
template <class T> Stack<T>::~Stack()
{
    if(top!=NULL)
    {
    while(top->prev!=NULL)
    {
        StackEl *t = new StackEl;
        t = top;
        top = top->prev;
        delete t;
    }
    delete top;
    }
}
 
template <class T> void Stack<T>::Push(const T& el)
{
    StackEl *t = new StackEl;
    t->data = el;
    t->prev = top;
    top = t;
}
 
template <class T> T Stack<T>::Pop()
{
    if(top==NULL)
        return NULL;
    StackEl *t = new StackEl;
    t = top;
    top = top->prev;
    return t->data;
}
LIFO стек, добавления нового элемента происходит в один его конец, а извлечение из противоположного

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
struct QueueElement
{
    char *el;
    QueueElement *next;
};
 
class PacketQueue
{
private:
    QueueElement *bottom;
    QueueElement *top;
 
public:
    PacketQueue();
    PacketQueue(QueueElement *first);
    int GetBottom(char*);
    int AddToQueue(char *newEl);
};
 
PacketQueue::PacketQueue():count(0), top(NULL), bottom(NULL)
{
}
 
PacketQueue::PacketQueue(QueueElement *first):count(0), top(NULL), bottom(NULL)
{
    AddToQueue(first->el);
}
 
int PacketQueue::GetBottom(char * ch)
{
    if(count<1)
            return -1;
    if(ch)
        delete[] ch;
    char *c= bottom->el;
    ch = new char[strlen(c)];
    if(!ch)
        return -1;
    strcpy(ch, c);
    printf("************ %s\n", ch);
    delete [] c;
 
    count = count - 1;
    if(count>0)
        bottom = bottom->next;
    else
    {
        top = NULL;
        bottom = NULL;
    }
    return 1;
}
 
int PacketQueue::AddToQueue(char *newEl)
{
    if(!newEl)
        return -1;
    QueueElement *temp = new QueueElement;
    if(!bottom)
    {
        bottom = temp;
    }
    else
        top->next = temp;
 
    temp->el = new char[strlen(newEl)];
    strcpy(temp->el, newEl);
    top = temp;
    top->next = NULL;
    count = count + 1;
    return 1;
}
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.06.2011, 00:20
Ответы с готовыми решениями:

Множество, LIFO, FIFO
Добрый день. Дали список задач для курсача, но не могу понять что требуется в некоторых из них......

Список FIFO и LIFO
#include &lt;cstdlib&gt; #include &lt;iostream&gt; using namespace std; struct struc{ char a; ...

Вывод списка, LIFO и FIFO
Программа создает два списка: один с числами, второй эти числа делит на четные и нечетные. Но при...

Посчитать прибыль от сделок используя FIFO и LIFO
Здравствуйте, Нужно написать небольшую програмку для подсчета прибыли после проведения...

1) сделать сортировку (любой) 2) защита по вводу символа 3) вывод LIFO, FIFO 4) лимит отображаемых симв.)
За основу брать этот пример . Не получается у меня(( #include &lt;iostream&gt; #include &lt;stdio.h&gt; ...

10
xAtom
922 / 747 / 299
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
27.06.2011, 00:48 2
По поводу наименований стэк представляет порядок LIFO последним зашёл - первым вышел, очередь.(queue) наоборот FIFO первым зашёл - первым вышел.
0
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
27.06.2011, 01:00  [ТС] 3
Ой, перепутал
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1309 / 1224 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
27.06.2011, 06:36 4
Цитата Сообщение от Alecs12 Посмотреть сообщение
Ой, перепутал
Не перепутал, а НЕ правильно назвал. Нельзя называть очередь универсальным стеком.
0
27.06.2011, 06:36
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
27.06.2011, 10:18  [ТС] 5
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не перепутал, а НЕ правильно назвал. Нельзя называть очередь универсальным стеком.

Єм, ну универсальным я назвал в плане что он принимает любой тип, так как я использовал шаблоны. И вроде то все же таки стек, только он не FIFO, а LIFO, тутя перепутал. Ну или я чего-то глобально недопонимаю..
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1309 / 1224 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
27.06.2011, 10:35 6
Я к тому, что даже если ты перепутал первый со вторым, это ничего не меняет. Стэк по определению может быть только LIFO. И то, что ты назвал FIFO стеком является очередью. Но тебе уже об этом сказали.)
0
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
27.06.2011, 23:55  [ТС] 7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Я к тому, что даже если ты перепутал первый со вторым, это ничего не меняет. Стэк по определению может быть только LIFO. И то, что ты назвал FIFO стеком является очередью. Но тебе уже об этом сказали.)
Да, я понял. Меня запутали, теперь меня так больше не запутают =)
А по коду кто-нибудь что-нибудь скажет? :-)
0
OstapBender
587 / 525 / 76
Регистрация: 22.03.2011
Сообщений: 1,585
28.06.2011, 00:03 8
Цитата Сообщение от Alecs12 Посмотреть сообщение
template <class T> struct Stack<T>::StackEl { T data; StackEl *prev; };
можно сделать вложенным (определить прямо в классе) для наглядности
Цитата Сообщение от Alecs12 Посмотреть сообщение
template <class T> Stack<T>::Stack():top(NULL) { }
зачем?) почему не определить сразу в классе.

имена функций и методов обычно пишут с маленькой буквы.

pop-ы можно сделать константными.

(всё написанное выше разумеется дело стиля)

Цитата Сообщение от Alecs12 Посмотреть сообщение
template <class T> T Stack<T>::Pop() { if(top==NULL) return NULL;
NULL в С++ это аналог нуля. может лучше выбросить исключение?
0
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
29.06.2011, 22:57  [ТС] 9
Спасибо большое за комментарии! =)

Цитата Сообщение от OstapBender Посмотреть сообщение
можно сделать вложенным (определить прямо в классе) для наглядности

зачем?) почему не определить сразу в классе.
Ну компилятор же все-равно подставит код так, как будто бы я написал реализация прямо в классе. так как кода очень мало?

Цитата Сообщение от OstapBender Посмотреть сообщение
pop-ы можно сделать константными.
Почему? Я же меняю указатель, т.е. модифицирую поле класса, такой метод разве может быть константным?

Цитата Сообщение от OstapBender Посмотреть сообщение
NULL в С++ это аналог нуля. может лучше выбросить исключение?
Про это не подумал, да, спасибо =)
0
pito211
186 / 173 / 18
Регистрация: 22.03.2010
Сообщений: 612
30.06.2011, 06:30 10
вобще обычно делают пару функций
top - делает то что у тебя делает pop и он должен быть константным(одна из версий)
pop - снимает элемент с верхушки, константным быть не может

проще было бы сделать адаптер к какому-нибудь существующему контейнеру.
C++
1
2
3
4
5
6
7
template <class T, class C = vector<T> > class stack
{
private:
     C c;
public:
     //методы
}
0
boov
0 / 0 / 0
Регистрация: 20.09.2011
Сообщений: 1
24.09.2011, 10:16 11
1) реализовать к-р копирования и оператор присваивания или запретить их (из-за top могут быть проблемы)
2) добавить методы size and empty
3) при попытке читать из пустого стека кидать исключение
4) часто требуется лишь посмотреть верхний элемент стека, не извлекая его => добвить соответствующий метод, как правило он называется Top
5) по извлечению, метод реализован неправильно (лишний new, утечка памяти):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T> T Stack<T>::Pop()
{
       //проверить на пусто и выкинуть исключение, если так
       // if(top==NULL)
       ///         return NULL;
        
        //tackEl *t = new StackEl;
        T data(top->data); //у T должен быть копирующий к-р
        //t = top;
        delete top;
        top = top->prev;
        //не забыть уменьшить размер стека
        return data;
}
6) в конструкторе вместо temp использовать top, иначе опять утечка, да и зачем лишнее присваивание.

PS:
a)путаница с понятиями стек-очередь LIFO-FIFO
b)посмотреть в сторону использования очереди из stl и реализовать класс стека как обертку над ней
c)реализацию класса очереди не стал смотреть
0
24.09.2011, 10:16
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2011, 10:16

Реализовать пользовательские классы - дек, стек (LIFO), очередь (FIFO) на базе класса list библиотеки STL
Создать пользовательские классы - дек, стек (LIFO), очередь (FIFO) на базе класса list библиотеки...

Создать класс, для хранения стека чисел – списка, организованного по принципу LIFO
Создать класс, для хранения стека чисел – списка, организованного по принципу LIFO (последним...

Реализация Fifo с разными типами данных
Доброго времени суток! Задача следующая: Есть абстрактный класс CData, от него наследуются...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru