Привет, народ.

Вот написал простейший стэк, но есть один баг :
при декрементировании указателя все работает OK, но если этого не сделать, то после вызова pop()
первый элемент выводится ноль, а дальше — вывод стэка сдвинут.

Я начинающий, но хочу во всем разобраться по-человечески....

Заранее благодарю!

Вот мой код (баг с указателем прокомментирован):
Возможно, есть другие ошибки... прошу прокомментировать )

 
#include<iostream>
#include<conio.h>
#include<stdlib.h>

using namespace std;




#define ARRSIZE 6

int *sp = NULL;

int tos = 5;
int array[5] = {1,2,3,4,5};


void push(int *array);
void pop();

int main()
{
    sp = array;

    for(int i = 0; i < 5; i++)
        push(  &array[i] );
    
    pop();
    getch();
    return 1;
}


    
void push( int arr[] ) 
{
    if( (*sp) == ARRSIZE )
    
    {
        cout << "Stack overflow" << "\n";
        getch();
        exit(0);
    }

   
    sp = arr;
    cout << (*sp);
    sp++;
    ++tos;

}

void pop()
{
    --sp; // БАГ!!!!!!!!если убрать эту инструкцию, то все сдвигается на 1элемент == 0 !!!!!!
    cout << "\n";
    for(int i = 0; i < 5; i++ )
       
    if (*sp == tos )
    {
    cout << "Stack is empty!";
    getch();
    exit(0);
    }
        else
        {
            cout << *sp;
            --sp;
        }
}

Здравствуйте, frenchman, Вы писали:

F>Вот написал простейший стэк, но есть один баг :
F>при декрементировании указателя все работает OK, но если этого не сделать, то после вызова pop()
F>первый элемент выводится ноль, а дальше — вывод стэка сдвинут.

F>Я начинающий, но хочу во всем разобраться по-человечески....

Да-да-да! Надо разобраться по-человечески.
То, что ты написал — на "простейший стек" не тянет. И вообще непонятно, что же оно должно делать.

Начнём с того, что интерфейс стека должен быть примерно такой

void push(T elem); // T - тип элемента
void pop();
T top();

А у тебя — push(T* arr). Почему? Зачем? Фактически, твой push просто присваивает указателю sp адрес подмассива.

Здравствуйте, Кодт, Вы писали:

К>Начнём с того, что интерфейс стека должен быть примерно такой
К>

К>void push(T elem); // T - тип элемента
К>void pop();
К>T top();
К>

К>А у тебя — push(T* arr). Почему? Зачем? Фактически, твой push просто присваивает указателю sp адрес подмассива.

Ну что ж вы сразу человека к глобальным переменным-то приучаете ?

void push(stack_t *stack, T elem); // T - тип элемента
void pop(stack_t *stack);
T top(const stack_t *const stack);

Здравствуйте, Нахлобуч, Вы писали:

Н>Здравствуйте, Кодт, Вы писали:

К>>Начнём с того, что интерфейс стека должен быть примерно такой
К>>

К>>void push(T elem); // T - тип элемента
К>>void pop();
К>>T top();
К>>

К>>А у тебя — push(T* arr). Почему? Зачем? Фактически, твой push просто присваивает указателю sp адрес подмассива.

Н>Ну что ж вы сразу человека к глобальным переменным-то приучаете ?

Н>

Н>void push(stack_t *stack, T elem); // T - тип элемента
Н>void pop(stack_t *stack);
Н>T top(const stack_t *const stack);
Н>

То есть есть стандартный интерфейс, которого надо придерживаться?
Шилдт тоже делает стэк, как Вы посоветовали. )
Или это все ИМХО?
Или с работой с динамическими структурами данных НУЖНО придерживаться ИМЕННО этого интерфейса?

Как улучшить свою алгоритмическую базу?Как видите, она у меня страдает ....

Здравствуйте, frenchman, Вы писали:

F>То есть есть стандартный интерфейс, которого надо придерживаться?

Есть стандартная функциональность, которую если воплощаешь по-нормальному, то непонятно, как сделать иначе.

F>Шилдт тоже делает стэк, как Вы посоветовали.
F>Или это все ИМХО?
F>Или с работой с динамическими структурами данных НУЖНО придерживаться ИМЕННО этого интерфейса?

Необязательно ТОЧНО такого. Но он в любом случае должен быть осмысленным.

F>Как улучшить свою алгоритмическую базу? Как видите, она у меня страдает ....

Читать Кормена, Седжвика, Бентли. http://www.rsdn.ru/summary/1495.xml

Здравствуйте, frenchman

Кратенько на предмет улучшения базы.

1. Интерфейс стека.
Стек — это объект, над которым определены операции push, pop, top — а также empty (проверка — пуст ли стек) и, возможно, size (размер стека).
Кроме того, нам понадобятся операции создания и уничтожения стека.

На С++ операции могут быть функциями-членами класса. На Си — только внешними функциями, которые принимают указатель на объект в качестве одного из параметров.

Функции создания-убиения — на С++ эту роль выполняют конструктор и деструктор. На Си — всё ручками.

2. Реализация стека.
На массиве — самое простое. Пусть у нас есть массив data[MaxSize] и количество элементов в стеке count.
Тогда
— empty() — count==0
— top() — data[count-1] (в С/С++ нумерация с нуля); когда count==0, т.е. нет ничего, то операция top неприменима
— push(v) — data[++count]=v — т.е. сперва резервируем место под элемент (увеличиваем размер), а затем кладём туда значение
— pop() — --count

Минусы очевидны: при переполнении мы или получаем ошибку, или вынуждены переразместить массив на куче.

Другие решения:
— список (достаточно односвязного списка) — больший расход памяти и времени
— список массивов (дек) — компромисс между массивом и списком: неограниченный размер, экономия памяти в пересчёте на один элемент