1.difference between stack using arrays and queue using arrays and 2.difference between stack using linked list and queue using linked list?

Answer 1

Both questions really boil down to the difference between a stack and a queue, so let's deal with that first. A stack is used when you want a last-in, first-out collection (LIFO), like a stack of plates; the last plate you place on the stack is the first to come off the stack. A queue is a first-in, first out collection (FIFO); the first person in a queue is the first to be served.

Secondly, we would never use an array for a stack or a queue. Arrays must be resized dynamically, both to cater for new elements and to remove redundant elements. When catering for a new element, it may be necessary to reallocate the entire array because arrays must reside in contiguous memory. We can alleviate some of this burden by allocating more elements than we actually need, but this wastes precious memory unnecessarily. Alternatively, we can use a two-dimensional array to allocate non-contiguous blocks of memory (which is important when the array is large), but it still wastes memory unnecessarily.

Linked lists are the optimum model for both stacks and queues as the nodes need not reside in contiguous memory and memory can be allocated and deallocated on a per-node basis with minimum impact on performance and memory consumption. While it is true some additional memory is required per-node to cater for each node pointing to the next, there is no redundant memory. And while arrays do allow constant-time random access to any element, stacks and queues do not require random access.

The main feature of a stack is that we require constant time access to the head of the stack. Insertions and extractions are made only to the head of the stack, therefore we need only maintain one pointer to the head of the stack. When a new node is inserted, its next node points to the existing head of the stack (which may be NULL if the stack is empty), and then the head pointer points to the new node. When the head node is extracted, its next node (which may be NULL) becomes the new head pointer.

The main feature of a queue is that we require constant time access to both the head and the tail. Insertions occur at the tail and extractions at the head, therefore we need two pointers, one at the head node, the other at the tail node. Initially both point to NULL. When a new node is inserted and the tail is NULL, both the head and tail point to the new node, otherwise the tail node points to the new node and the new node becomes the tail. The tail node always points to NULL. Extracting the head node is the same as in a stack, except the tail node is set to NULL whenever the head is set to NULL.

To fully address the question, let's consider stacks and queues using arrays. We'll ignore the resizing issues simply by assuming that there are initially 10 unused elements, and whenever there are fewer than 5 unused elements the array will be resized by an extra 10 elements, and reduced by 10 elements whenever there are more than 15 unused elements. Thus there will always be at least 10 elements. There are better methods than this, but it will suffice for the purpose of this answer.

Since insertions at the start of the array would require us to copy all elements into the next element to make room for the insertion, all insertions will occur at the end of the array in the first unused element. Therefore we must maintain a zero-based index of the first unused element (the tail). When we insert an element at that index, the tail is simply incremented.

For the stack, extractions also occur at the tail. Therefore, if the tail is non-zero, we simply decrement the tail and extract the element at that index. If the tail is zero, the stack is empty. Otherwise the tail tells us how many elements have been used for resizing purposes. Resizing should be done after an insertion or extraction.

For the queue, extractions occur at the head, therefore we initially point at element zero. If the head and tail are different, an item exists at the head element so we extract it and increment the head. If the head and tail are the same, then there are no elements in use so both can be reset to zero. The only real complication is in working out how many unused elements there are for resizing purposes. For this we simply subtract the head from the tail to determine how many elements are in use. This should be done prior to any insertion. If a resize is required it would be prudent to shunt all used elements to the start of the array and adjust the head and tail accordingly, then perform the insertion.

As you can appreciate, a queue is more complex than a stack when using an array, but ultimately an array is more complex than a linked list for both stacks and queues.