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

Очередь FIFO - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.84
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 19:37     Очередь FIFO #1
Добрый вечер. Задали написать реализацию очереди FIFO. Загвоздка в том, как передать указание на следующий элемент при его добавлении.

Недавно писал FILO, там было так:

C++
1
2
3
4
5
6
7
8
9
10
bool stack::Push(int v){
ST_LIST *item;
item = new ST_LIST;
 
if (item) {
 item->value=v;
 item->next=first;
 first=item;
 return true;
}
а тут как? тут при добавлении нужно чтобы указатель на вершину был постоянен, а список рос с конца. Подскажите)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
domovoi94
-19 / 6 / 1
Регистрация: 09.10.2010
Сообщений: 41
21.05.2012, 19:40     Очередь FIFO #2
это структура типа очередь. Хранишь начало, и конец. Данные забираешь сначала. Записываешь в конец
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 20:55  [ТС]     Очередь FIFO #3
Я в ступоре, как сделать функцию добавления в очередь((

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
int k=1;
bool spis::Push(int v){
    ST_LIST *item;
    item=new ST_LIST;
    
 
    if (k==1){
        if (item){
            item->value=v;
            first=item;
            return true;
            k++;
        }
        else return false;
    }
    else {
        if (item){
            item->value=v;
            item->next=item;
            return true;
            k++;
        }
        else return false;
    }
 
}
Помогите пожалуйста, этот вариант не работает(((

Добавлено через 11 минут
при первой записи я запоминаю first, при второй - end, а потом при добавлении любого элемента end будет указывать на него, а next - на предыдущий?

Или как?

Добавлено через 49 минут
Ребят, помогите пожалуйста, очень надо до завтра...
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 20:56     Очередь FIFO #4
вот топорный вариант:
имея указатель на начало списка вы всегда можете в цикле добраться до его последнего элемента (до тех пор пока item->next не станет равным нулю). вот у вас есть последний итем.

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
item* getPredLastItem() // получение предпоследнего
{
  // тут алгоритм прохода от начала до предпоследнего итема. реализовать не сложно.
  return predLast;
}
 
item* getLastItem()
{
   // список может быть пустым и getPredLastItem() может вернуть 0. нужно проверять.
  return getPredLastItem()->next;
}
 
void push(int value)
{
  Item* newItem = new Item();
  newItem->value = value;
  newItem->next = 0;
   // список может быть пустым и getLastItem() может вернуть 0. нужно проверять.
  Item* lastItem = getLastItem();
  lastItem->next = newItem;
}
 
void pop()
{
   // список может быть пустым и getLastItem() может вернуть 0. нужно проверять.
  Item* predLastItem = getPredLastItem();
  delete predLastItem->next; // дестроим последний итем
  predLastItem->next = 0; // теперь предпоследний помечен как последний.
}
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 21:02  [ТС]     Очередь FIFO #5
DU, я не понимаю(
Чего-то туго очень все... Можно целиком работающий код?
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 21:07     Очередь FIFO #6
вы спрашивайте, не стесняйтесь. что именно вам не понятно?
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 21:13  [ТС]     Очередь FIFO #7
мне не понятна Ваша реализация функций добавления элемента и удаления.

Вот как я понимаю очередь: записываем первый элемент - он first, на следующий, который мы запишем, будет ссылка next от того, который first...и так далее. нет?
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 21:26     Очередь FIFO #8
я привел несколько упрощенный вариант, которые не рассматривает случай, когда список пустой.
предположим в списке десяток объектов. чтобы добавить в конец списка элемент, нужно:
1 создать новый
2 взять текущий последний.
3 к последнему присоединить новый.

т.е.
C++
1
2
3
4
5
6
7
8
9
10
// создаем новый
Item* newItem = new Item();
newItem->value = value;
newItem->next = 0;
 
// Теперь берем последний итем списка
Item* lastItem = getLastItem();
 
// и присоединяем к нему этот новый.
lastItem->next = newItem;
это понятно?

удаление последнего тоже вроде простое
берем предпоследний итем. по нему находим последний. удаляем последний (delete). помечаем предпоследний последним.
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 21:30  [ТС]     Очередь FIFO #9
Да. Это понятно.

А как реализовать, танцуя от того, что изначально очередь пустая? Можете помочь?
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.05.2012, 21:41     Очередь FIFO #10
ну все же просто. если getLastItem вернула 0, значит список пустой. значит у него еще нет головы (первого итема.). значит новый созданный и будет его головой. т.е что-нибудь типа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void push(int value)
{
  Item* newItem = new Item();
  newItem->value = value;
  newItem->next = 0;
 
  Item* lastItem = getLastItem();
  if (lastItem == 0) // если список пустой
  {
     firstItem = newItem;
  }
  else
  {
     lastItem->next = newItem;
  }
}

для удаления последнего элемента из списка действия такие же
если предпоследний элемент не вернулся, значит список или пустой или состоит из одного элемента. проверяем firstItem. если оно нуль - значит список пустой и ничего из него удалить не получится.
если же firstItem не ноль - то он является последним в списке. его нужно задестроить и указатель firstItem приравнять к нулю.
Rabbit13245
28 / 28 / 2
Регистрация: 21.04.2012
Сообщений: 282
21.05.2012, 22:20  [ТС]     Очередь FIFO #11
Хорошо, попробую реализовать. Осталось реализовать вывод на печать...

Добавлено через 13 минут
DU, я не могу реализовать Ваш метод. У Вас не рабочего кода?

Добавлено через 23 минуты
Ребят выручите пожалуйста. Завтра сдавать, а реализовать не могу. Очень нужно
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2012, 19:45     Очередь FIFO
Еще ссылки по теме:

Изменить удаление и добавление элементов в очередь по правилу FIFO. C++
Очередь «первый вошел — первый вышел» (FIFO) C++
Двумерная очередь (FIFO) C++

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

Или воспользуйтесь поиском по форуму:
CRonaldo7
0 / 0 / 0
Регистрация: 19.06.2012
Сообщений: 22
19.06.2012, 19:45     Очередь FIFO #12
вот код посоны
#pragma once;
///////// LIFO
class Lifo
{
int *stack;
int size;
int *p;

public:
Lifo(int size=10):size(size)
{
stack=new int [size];
p=stack;
}
bool isEmpty()
{
return stack==p;
}
bool isFull()
{
return stack+size==p;
}
bool push (int value)
{
if(isFull()) return false;
*p=value;
++p;
return true;
}
int pop ()
{
if(isEmpty()) return 0;
--p;
return *p;
}

~Lifo()
{
delete[]stack;
}

void SetEmpty()
{
p=stack;
}

};
Yandex
Объявления
19.06.2012, 19:45     Очередь FIFO
Ответ Создать тему
Опции темы

Текущее время: 00:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru