Stack and queue operations on the same array.

Question

Hi. I've been thinking about a program logic, but I cannot draw a conclusion to my problem.

Here, I've implemented stack and queue operations to a fixed array.

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;
}

It is presumed(or obvious) that the bottom of the stack and the front of the queue is pointing at the same location, and vice versa(top of the stack points the same location as rear of the queue).

For example, integer 1 and 2 is inside an array in order of writing. And if I call StackPop(), the integer 2 will be popped out, and if I call QueuePop(), the integer 1 will be popped out.

My problem is that I don't know what happens if I do both stack and queue operations on the same array. The example above is easy to work out, because there are only two values involved. But what if there are more than 2 values involved?

For example, if I call

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

what values will be returned in the order of bottom(front) from the final array?

I know that if I code a program, I would receive a quick answer. But the reason I'm asking this is because I want to hear a logical explanations from a human being, not a computer.

ADDED: For the second example, I have 4 candidates. 25 12 24 45 or no answer from here at all.

Answer 1

the result will be 4 and 1, because the array has 1 2 4 and when you say stack pop it gets the recently added item which is 4. and when after the stack push 5 the array will be 1 2 5 and then when you pop from the queue you will get 1 as queue pop gets the first added item.

Answer 2

Why are you implementing these on the same array? The elements of one structure might overwrite those from the other if you do it like this.

You essentially have (something resembling) a deque there however, but it's difficult to run your program by hand because you have different pointers for the two data structures but only one array for both of them.

It is presumed(or obvious) that the bottom of the stack and the front of the queue is pointing at the same location, and vice versa(top of the stack points the same location as rear of the queue).

Well, ok in this case, but you should just use a Deque, which doesn't work on this assumption. Or use different vectors for the queue and stack.

Generally a human does this is just how a computer does it. Just have your program print the contents of A after each operation, and it should be logical enough.

Answer 3

I'm not sure exactly what problem you're trying to solve, but this looks very much like a double-ended queue. Depending on the problem you're trying to solve, a circular buffer may be worth examining.

Have a look at those proven data structures to at least give yourself more context for implementing your own data structure, and hopefully one of them is what you're after.

Answer 4

In the case of your code, it will probably not do what you expect since the stack routines and the queue routines maintain different variables for where to push to.

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

---

If you instead wrote the code so that the stack use rear instead of top, then you would see these results.

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