Question

in C++

For this program, you are going to implement a stack using an array and dynamic memory allocation.

A stack is a special type of data structure that takes in values (in our case integers) one at a time and processes them in a special order. Specifically, a stack is what's called a first-in-last-out (FILO) data structure. That is to say, the first integer inserted into the stack is the last value to be processed. The last value in the stack is the first one processed.

A stack is used as a part of many different algorithms in computer science. For now, when we say to "process" an integer on the stack, all I want you to do is print out what the integer is to the terminal, and then remove it from the array.

Here's a link for a visual on how it would work: https://www.cs.usfca.edu/~galles/visualization/StackArray.html

Here is how I want your program to work:

• Have the program present a menu where I can either:
  • Insert a new integer onto the stack.
  • Process an integer from the stack.
  • Quit the program.
• Every time that you present the menu, please print out the contents of the stack before I pick a menu option. If the stack is empty, please let the user know.
• The point of this assignment is to use dynamic memory allocation. So you must use malloc at the start of the program to allocate memory for a single integer. Then use realloc for the remainder of the program. Statically declaring arrays will result in no credit for the assignment!
• If I choose the second options, which is to process a node, please print out the value that is being processed and then use realloc to appropriately change the size of your array.
• Be sure to use the free function to release all memory if I decide to quit the program.

You do not have to do this in a function. This can all be done in the main function if you like.

I've attached the output from my version of the program in the sampleoutput.txt file if you would like to see an example of what I'm looking for.

*****Extra credit: 10%*****

A queue is a similar data structure in which the first item inserted into the queue is the first item processed (FIFO). After I choose to quit the stack loop, reallocate the array pointer back to a single integer and then repeat the program above, but so it processes the integers in the order of a queue rather than a stack. The output should indicate that we are now using a queue as well.

Answer 1

#include <iostream>

#include <cstdlib>

using namespace std;

int * insert_stack(int * arr, int size, int input) {
    int * newarr = (int * ) realloc(arr, sizeof(int) * (size + 1));
    *(newarr + size) = input;
    return newarr;
}

int process_stack(int * arr, int size) {
    int x = arr[size - 1];
    arr = (int * ) realloc(arr, sizeof(int) * (size - 1));
    return x;
}

int * insert_queue(int * arr, int size, int input) {
    int * newarr = (int * ) realloc(arr, sizeof(int) * (size + 1));
    *(newarr + size) = input;
    return newarr;
}

int process_queue(int * arr, int size) {
    int x = arr[0];
    for (int i = 1; i < size; i++) {
        arr[i - 1] = arr[i];
    }
    arr = (int * ) realloc(arr, sizeof(int) * (size - 1));

    return x;
}

int main() {

    int * stack = (int * ) malloc(sizeof(int));
    int size = 0;
    cout << "Stack\n";
    while (1) {
        cout << "Enter 1 to insert\nEnter 2 to process\nEnter any key to enter Queue!\n";
        int key;
        cin >> key;
        if (key == 1) {
            int input;
            cin >> input;
            stack = insert_stack(stack, size, input);
            size++;
        } else if (key == 2) {
            if (size == 0) {
                cout << "Stack Empty!" << endl;
                continue;
            }
            cout << "Processed Element is: " << process_stack(stack, size) << endl;
            size--;
        } else {
            break;
        }
        cout << "Current Stack\n";
        for (int i = 0; i < size; i++) {
            cout << * (stack + i) << " ";
        }
        cout << endl;
    }
    //if size is not empty then free the memory
    if (size > 0)
        free(stack);
    //Now used as queue
    size = 0;
    stack = (int * ) malloc(sizeof(int));
    cout << "Queue\n";
    while (1) {
        cout << "Enter 1 to insert\nEnter 2 to process\nEnter any key to exit!\n";
        int key;
        cin >> key;
        if (key == 1) {
            int input;
            cin >> input;
            stack = insert_queue(stack, size, input);
            size++;
        } else if (key == 2) {
            if (size == 0) {
                cout << "Queue Empty!" << endl;
                continue;
            }
            cout << "Processed Element is: " << process_queue(stack, size) << endl;
            size--;
        } else {
            break;
        }
        cout << "Current Queue\n";
        for (int i = 0; i < size; i++) {
            cout << * (stack + i) << " ";
        }
        cout << endl;
    }
    if (size > 0)
        free(stack);
    return 0;
}

Steps :

1. Compile and Run the program

2. Enter 1 to insert, 2 to process, and any other key to enter Queue

3. Once in Queue enter 1 to insert, 2 to process and any other key to exit the program