Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 43, средняя оценка - 4.93
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
#1

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

27.06.2011, 00:20. Просмотров 5729. Ответов 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xAtom
914 / 739 / 60
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
27.06.2011, 00:48     Реализация стека FIFO и LIFO #2
По поводу наименований стэк представляет порядок LIFO последним зашёл - первым вышел, очередь.(queue) наоборот FIFO первым зашёл - первым вышел.
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
27.06.2011, 01:00  [ТС]     Реализация стека FIFO и LIFO #3
Ой, перепутал
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
27.06.2011, 06:36     Реализация стека FIFO и LIFO #4
Цитата Сообщение от Alecs12 Посмотреть сообщение
Ой, перепутал
Не перепутал, а НЕ правильно назвал. Нельзя называть очередь универсальным стеком.
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
27.06.2011, 10:18  [ТС]     Реализация стека FIFO и LIFO #5
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не перепутал, а НЕ правильно назвал. Нельзя называть очередь универсальным стеком.

Єм, ну универсальным я назвал в плане что он принимает любой тип, так как я использовал шаблоны. И вроде то все же таки стек, только он не FIFO, а LIFO, тутя перепутал. Ну или я чего-то глобально недопонимаю..
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
27.06.2011, 10:35     Реализация стека FIFO и LIFO #6
Я к тому, что даже если ты перепутал первый со вторым, это ничего не меняет. Стэк по определению может быть только LIFO. И то, что ты назвал FIFO стеком является очередью. Но тебе уже об этом сказали.)
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
27.06.2011, 23:55  [ТС]     Реализация стека FIFO и LIFO #7
Цитата Сообщение от Deviaphan Посмотреть сообщение
Я к тому, что даже если ты перепутал первый со вторым, это ничего не меняет. Стэк по определению может быть только LIFO. И то, что ты назвал FIFO стеком является очередью. Но тебе уже об этом сказали.)
Да, я понял. Меня запутали, теперь меня так больше не запутают =)
А по коду кто-нибудь что-нибудь скажет? :-)
OstapBender
583 / 521 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
28.06.2011, 00:03     Реализация стека FIFO и LIFO #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 в С++ это аналог нуля. может лучше выбросить исключение?
Alecs12
1 / 1 / 0
Регистрация: 21.03.2011
Сообщений: 23
29.06.2011, 22:57  [ТС]     Реализация стека FIFO и LIFO #9
Спасибо большое за комментарии! =)

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

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

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

Цитата Сообщение от OstapBender Посмотреть сообщение
NULL в С++ это аналог нуля. может лучше выбросить исключение?
Про это не подумал, да, спасибо =)
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
30.06.2011, 06:30     Реализация стека FIFO и LIFO #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:
     //методы
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2011, 10:16     Реализация стека FIFO и LIFO
Еще ссылки по теме:
C++ Реализация стека
Реализация стека C++
реализация стека C++
C++ Реализация стека
Реализация стека C++

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

Или воспользуйтесь поиском по форуму:
boov
Сообщений: n/a
24.09.2011, 10:16     Реализация стека FIFO и LIFO #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)реализацию класса очереди не стал смотреть
Yandex
Объявления
24.09.2011, 10:16     Реализация стека FIFO и LIFO
Ответ Создать тему
Опции темы

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