How do you represent stack and queue by using one dimensional array?

Answer 1

You would not use an array for a stack or queue, you would use a singly-linked list. The problem with arrays is that they must grow and shrink as items are inserted or extracted, which requires the entire array to be copied, whereas linked-lists can grow and shrink dynamically without the need to copy any elements. The only reason to use an array to implement a list is when you require random access in constant time. Queues and stacks only require constant time access to the head or tail of the list, and a linked list can easily achieve that.

Implementing a stack as an array requires that new elements be inserted at the end of the array. If the array is full, it must be reallocated in order to make space for a new element. Extraction always occurs at the end of the array. While this releases elements for insertions, if they go unused for any length of time they are simply wasting memory. Thus the array must be reallocated occasionally to free the redundant memory, which is highly inefficient.

Implementing a queue has similar issues as all insertions are at the end of the array, however it is further complicated by the fact extractions must occur at the beginning of the array. Thus every element must be copied to its preceding element every time an element is removed from the head of the queue. This frees up the end of the array, but the need to reallocate and copy elements is again, highly inefficient.

Linked lists overcome all these problems such that no memory is ever in a redundant state, and no copying is ever required.

Answer 2

A stack is easily implemented with an array and a top-of-stack marker (TOS), implemented as an array index.

At initialization time, the TOS would be initialized to -1 or 0 depending on the implementation: initialize to -1 if the PUSH operation uses pre-increment, or 0 if the PUSH uses post-increment. The POP operation uses the reverse (post-decrement or pre-decrement, respectively).

Following is a crude example using pre-increment for PUSH, not including boundary checks:

int tos = -1;

DataType array[MAX_STACK_SIZE];

void push(DataType v) {

array[++tos] = v;

}

DataType pop() {

return array[tos--];

}

Answer 3

A stack (first in, last out) is simpler. You just need an array and a separate value holding the number of items currently in the array.

Here's a very simple example; DON'T do it like this "for real," but it should be easy to understand:

#define STACK_SIZE 100 /* or 1000 or dynamically allocate, or whatever */

int number_of_items = 0;

int the_stack[STACK_SIZE];

void push_to_stack(int the_number)

{

if (number_of_items < STACK_SIZE)

{

the_stack[number_of_items] = the_number;

++number_of_items;

}

}

int pop_from_stack()

{

int return_value = 0;

if (number_of_items > 0)

{

--number_of_items;

return_value = the_stack[number_of_items];

}

return return_value;

}

Yes, indeed: I could have just said:

the_stack[number_of_items++] = the_number

and

return_value = the_stack[--number_of_items]

but this is clearer. Feel free to use the less clear way if you like, but my purpose here is just to be as clear as I can.

To do a queue (first in, first out), you need to keep track of which is the first item and which is the last one, because you keep "using up" the first one when you pop one off, and you add after the last one. And, eventually, you will either "run out" of your buffer because the active area keeps moving, or else you need a way to "circle back" to the beginning when you hit the end (some people might call this a "ring buffer"). This added complication is why many people think it's easier to use a linked list (instead of an array) for a queue.

I'm not going to write the code though, because that would be doing your homework for you. The guidelines in the above paragraph should point you to the right way.

Answer 4

You will need to pick up one end and put it back into the stack to remove the last item. A queue you can hold the head and advance it through the array.

Answer 5

bhenchod