Стек и операции с очередями в одном массиве

Question

Я думал о логике программы, но не могу сделать вывод о своей проблеме.

Здесь я реализовал операции стека и очереди для фиксированного массива.

int A[1000];
int size=1000;

int top;

int front;
int rear;

bool StackIsEmpty()
{
    return (top==0);
}

bool StackPush( int x )
{
    if ( top >= size ) return false;
    A[top++] = x;
    return true;
}

int StackTop( )
{
    return A[top-1];
}

bool StackPop()
{
    if ( top <= 0 ) return false;
    A[--top] = 0;
    return true;
}

bool QueueIsEmpty()
{
    return (front==rear);
}

bool QueuePush( int x )
{
    if ( rear >= size ) return false;
    A[rear++] = x;
    return true;
}

int QueueFront( )
{
    return A[front];
}

bool QueuePop()
{
    if ( front >= rear ) return false;
    A[front++] = 0;
    return true;
}

Предполагается (или очевидно), что нижняя часть стека и фронт очереди указывают на одно и то же место, и наоборот (верхняя часть стека указывает на то же место, что и задняя часть очереди). *

Например, целые числа 1 и 2 находятся внутри массива в порядке записи. И если я вызову StackPop (), будет выдано целое число 2, а если я вызову QueuePop (), будет выдано целое число 1.

Моя проблема в том, что я не знаю, что произойдет, если я выполняю операции стека и очереди в одном массиве. Вышеприведенный пример легко разобрать, потому что задействованы только два значения. Но что, если задействовано более двух значений?

Например, если я позвоню

StackPush(1);
QueuePush(2);
QueuePush(4);
StackPop();
StackPush(5);
QueuePop();

какие значения будут возвращены в порядке нижнего (переднего) из окончательного массива?

Я знаю, что если я закодирую программу, я получу быстрый ответ. Но я спрашиваю об этом потому, что хочу услышать логические объяснения от человека, а не от компьютера.

ДОБАВЛЕНО: Для второго примера у меня есть 4 кандидата. 25 12 24 45 или вообще никакого ответа.

Answer 1

Почему вы реализуете их в одном массиве? Элементы одной структуры могут перезаписать элементы другой, если вы сделаете это следующим образом.

Тем не менее, у вас есть (что-то похожее) deque , но вам трудно запустить вашу программу вручную, потому что у вас есть разные указатели для двух структур данных, но только один массив для них обоих. 1005 *

Предполагается (или очевидно), что нижняя часть стека и передняя часть очереди указывают на одно и то же место, и наоборот (верхняя часть стека указывает на то же место, что и задняя часть очереди).

Хорошо, хорошо в этом случае, но вы должны просто использовать Deque, который не работает в этом предположении. Или используйте разные векторы для очереди и стека.

Обычно человек делает это так, как это делает компьютер. Просто попросите вашу программу печатать содержимое A после каждой операции, и это должно быть достаточно логичным.

Answer 2

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

StackPush(1);   // place 1 at position 0; increase top of stack to 1
QueuePush(2);   // place 2 at position 0; increase rear of queue to 1
QueuePush(4);   // place 4 at position 1; increase rear of queue to 2
StackPop();     // get value(2) from position 0; decrease top of stack to 0
StackPush(5);   // place 5 at position 0; increase top of stack to 1
QueuePop();     // get value(5) from position 0; increase front of queue to 1

---

Если вы вместо этого написали код, чтобы в стеке использовалось rear вместо top, вы увидите эти результаты.

StackPush(1);   // place 1 at position 0; increase rear to 1
QueuePush(2);   // place 2 at position 1; increase rear to 2
QueuePush(4);   // place 4 at position 2; increase rear to 3
StackPop();     // get value(4) from position 2; decrease rear to 2
StackPush(5);   // place 5 at position 2; increase rear to 3
QueuePop();     // get value(1) from position 0; increase front to 1

Answer 3

Я не уверен, какую именно проблему вы пытаетесь решить, но это очень похоже на двустороннюю очередь . В зависимости от проблемы, которую вы пытаетесь решить, круговой буфер может стоить изучить.

Взгляните на эти проверенные структуры данных, чтобы хотя бы дать себе больше контекста для реализации собственной структуры данных, и, надеюсь, одна из них - то, что вам нужно.

Answer 4

результат будет 4 и 1, потому что массив имеет 1 2 4, и когда вы говорите, что pop pop, он получает недавно добавленный элемент, который равен 4. И когда после нажатия стека 5 массив будет 1 2 5, а затем когда вы выскочите из очереди, вы получите 1, поскольку поп-очередь получает первый добавленный элемент.