What are the advantages and disadvantages of stacks and queues in data structure?

Answer 1

Stack and Queue have elements enter and leave frequently, and the total number of elements within the container (the stack or the queue) may be unpredictable. That is, the size of the container may be 0 or very huge.

Array is a fixed size collection. When adding an element, if the array is already full, it cannot simply add another "slot" to hold the new entry. The program must create another array instance that is big enough to hold the original elements and the new comers, which means all the elements must be "moved" from the current array to the newly created one.

Linked list has the advantage of easily adding and removing a node (to hold an element) and keep the ones already in the list untouched.

Answer 2

Linked lists are the preferred method of implementing both stacks and queues. Arrays are the preferred method of implementing a list where random access is the guiding factor.

Firstly, let's just clarify what a queue and a stack are before we discuss the merits of a linked list over an array. Queues and stacks are actually quite similar. At the simplest level, they are nothing more than a sequential collection of data; that is, unsorted data. New data may be added to the head (stack) or the tail (queue), but existing data is always extracted from the head.

Queue

If we add data to the tail and extract it from the head, we create a queue. This can be likened to a queue of people waiting to be served. The British Bulldogs amongst you will be very familiar with this simple concept, but for those Johnny Foreigners who refuse to believe there is such a concept, the guiding principal is that new people must join the back of the queue, while those at the front get served first. We call this a First In, First Out (FIFO) structure. To implement this structure efficiently, we must have constant time access to both the head and the tail of the queue.

Stack

If we add data to the head of a queue and extract it from the head, we have a stack. This can be likened to a stack of serving plates. Clean plates are placed on top of the stack while those waiting to be served take a plate off the top of the stack. This is a Last In, First Out (LIFO) structure. To implement this efficiently, we must have constant time access to the top of the stack. When working with stacks, we use the terms "push" and "pop" . This is likened to those spring-loaded plate dispensers, where you push a plate on the stack and pop a plate off the stack.

Now that we're familiar with the concepts, let's consider using an array to implement them.

Array as Queue

To implement a queue using an array, we require constant-time access to the head and tail of the array. That's a given with arrays, since the upper and lower bounds of the array tell us which elements we need to access. However, we must also cater for new data being added to the tail. Immediately there's a problem, because we can't add new elements if all the current elements contain data. In order to create space for a new item of data, we must re-allocate the array with 1 additional element. This then means we must copy the entire array to the new allocation before deleting the existing array. That's a costly operation, both in terms of memory consumption (albeit temporarily), and in physically copying all the elements.

We can overcome much of this penalty by allocating enough memory to accommodate several new elements at a time, and keep track of the tail element, but this means allocating memory that may never be used, which is wasteful. As if that weren't enough, consider what happens when we extract items from the head...

Extracting from the head would leave us with an empty element at the head (element 0). Thus the entire array from element 1 to the last must be shunted up the array, one at time, thus moving the slot to the end of the queue. Shunting requires that we copy every value, which is just as inefficient as reallocating the array to accommodate new items. We can overcome this inefficiency by keeping track of the new head index until such times as the queue is completely empty (in which case element 0 is re-instated as the head) or we must reallocate to accommodate new items (in which case the queue is simply shunted towards the head to create space at the tail).

Although these solutions solve much of the problem, there's still the issue of unused elements that may never be used, and the need to reallocate when there are no empty elements available. What do we do when the queue is empty? Should we shrink the queue to a "default" size to free the unused memory? How many elements should we allocate when we need to reallocate? There is no simple answer to these questions (that is, there is no one solution that is suitable for all types of queue).

Stack as Array

Implementing a stack as an array is a bit more straightforward since we only need to keep track of the last element (perversely, the top of the stack is the tail of the array). We don't need to consider shunting items towards the head anymore, but we must still accommodate for new items which means we still waste memory allocating unused elements. Again, what do we do when the queue is empty? What is the "default" size? And how many elements to we allocate when an allocation is required?

Singly-Linked List

So much for arrays. Let's now consider the merits of linked lists. In both cases, we only need a singly-linked list. That is, we only need keep track of the head node and each node in the list points to the next node. The last node points to NULL. A queue requires a minor tweak in that it must also keep track of the tail node, since that is where new elements will be added. However, we don't need a doubly-linked list. Stacks and queues only require a traversal in one direction, and never by more than one node to the next (we never fully-traverse the list).

The only real downside to using linked lists for queues an stack is the need to maintain pointers to the head (and tail), and for each node to maintain a pointer to its next node. All those pointers consume additional memory but it is not redundant memory. At times, the additional memory may be more than might be required if we used an array, but the advantage of dynamic scaling without the need to copy or shunt nodes around more than outweighs this.

Queue as Linked ListLinked list queues are simple. Remember that we must insert at the tail and extract from the head. Thus the queue must keep track of both the head and the tail, both of which point to NULL whenever the queue is empty. When a new item is added and the tail node is currently NULL, the new node becomes both the head and tail of the queue (it is the first and only node). But if the tail is not NULL, then its next node is set to point at the new node, and the new node becomes the tail node of the queue. When we extract the head node, the head node's next node (which may be NULL if it is also the tail node) becomes the head node of the queue. If the head node becomes NULL, the tail node is also set to NULL (meaning the queue is empty).

Simple and elegant, if a bit of a mouthful to explain. But take my word for it, it's a tried and trusted algorithm. Read it again, more slowly, and hopefully it'll make sense.

Stack as Linked ListStacks are even simpler than queues. The head node is the top of the stack (we don't need to keep track of the tail). When we insert a new node, we set its next node to the current head node (which may be NULL if the stack is empty), and the new node becomes the head node of the stack. When we extract the head node, its next node (which may be NULL if it is the only node) becomes the head of the stack.

It really is as simple as that.

To Summarise

Although linked lists may consume more memory than might otherwise be consumed by an array, an array requires periodic reallocation to create room for new elements, and must be periodically shrunk to release unused memory. Linked lists dynamically scale and clean up all by themselves, without any additional work on the part of the programmer. And although memory consumption may not be optimal, every byte consumed serves a useful purpose.

One aspect we haven't touched upon is that array elements must always be a consistent size and type. However, the same is true of linked lists, so it's not really a disadvantage with arrays. When dealing with mixed data types, pointers can be used instead. So long as they all point to the same intrinsic type (such as an abstract class of object or a pointer to void), mixing data types can be achieved with arrays and linked lists.

Constant access to the first and last items is not an issue either since both achieve this in constant time. The main advantage to the linked list implementation is the ability to scale gracefully.

The same may not be said when random access is required. Although it is not a requirement of stacks or queues, if you require random access in constant time, an array is hard to beat.

Answer 3

The advantage of an array implementation of stack and queue is simplicity. The disadvantage is lack of expansion, i.e. the size of the stack or queue is preset.

The advantage of a linked list implementation of stack and queue is automatic expandability. The disadvantage is complexity, but the linked list is probably a better idea.

Answer 4

Arrays are best suited to structures that require constant time random access to any element in the array. Arrays are also best suited to static structures where the number of elements can be determined as a constant at compile time, or dynamic structures where the number of elements can be determined in advance at runtime and will not change for the lifetime of the array. Although dynamic arrays can be resized, they must be allocated a block of contiguous memory addresses. But if the current memory block is not large enough to meet a resize request, a larger block must be set aside to meet the allocation and the entire array must be copied into it before the original array can be destroyed. This is done automatically as part of an array resize request, but programmers need to be aware of what's going on Behind the Scenes in order to achieve best performance and efficient use of memory.

Re-allocating memory and copying array elements is a time-consuming task which will impact upon performance. The need to copy elements can be reduced by increasing the array size by several elements at a time, however this results in allocating far more memory than required at any given moment, some of which may never be required at all, which is ultimately wasteful. To alleviate this, arrays must be periodically shrunk to minimise the redundancy. Shrinking an array doesn't impact greatly on performance as the memory doesn't need to be re-allocated (the allocation is guaranteed to exist within the current allocation). However, you must also maintain an index of the last used element in order to know how many elements are used and how many are available at any given moment.

Inserting elements at the end of the array isn't a problem provided there are unused elements available. However, inserting anywhere else requires that all subsequent elements be shunted by one element towards the end of the array (starting with the last element) to make space for the new element, which means the elements must be copied. If the insert point is always at the front of the array, then every element must be copied with every insertion.

Extracting elements from an array requires that all subsequent elements be shunted forwards by one element to remove the hole left by the extraction, which requires yet more copying unless the extraction always occurs at the last used element. If the extractions always occur at the front of the array, maintaining another index of the first used element can reduce the need to shunt elements around the array. The number of used elements can be determined by subtracting the first used index from the last used index and adding 1.

By contrast, linked-lists are best suited to dynamic structures where the number of elements cannot be determined in advance. Memory is allocated on a per-element basis and elements needn't reside in contiguous memory addresses. This is achieved by maintaining a pointer to the head node, which contains a pointer to the next node, which points to the next, and so on. The last node points to zero. When the head node is zero, there are no elements in the list.

Although the head node is accessible in constant time, random access to any other node is not possible in constant time. The list must be traversed from the head node to locate the required node, thus random access is computed in linear time, which is typically expressed using "Big 'O'" notation. That is, for a list with n elements, the time complexity of a traversal has a worst case of O(n) when seeking the last element and O(1) when seeking the first element (constant time). Thus the average seek time for any element is O(n/2).

That said, neither a stack nor a queue require random access of any sort. A stack requires constant time access to the first element only because new elements are always pushed onto the front of the stack and always popped from the front. A push is achieved by creating a new node for the pushed element, with the head node as its next node, and then setting the head node to the new node. A pop simply extracts the head node's element and temporarily points at its next node. The head node is then deleted. The head node is then set to the temporary pointer. The final act of a pop is to return the extracted element.

Queues require constant time access to the head node for extractions (implemented exactly the same as for a stack pop). However they also require constant time access to the last node, the tail node. As mentioned above, this requires a complete traversal of the list to locate the last node. However, with a simple modification, a singly-linked list can also maintain another pointer to its tail. A doubly-linked list is another option (where every node points to its previous node as well as its next), but this is overkill for a queue. To perform an insertion, a new node is created for the new element which subsequently becomes the next node of the tail. The tail is then set to the new node.

Priority queues are a specialised form of queue where insertions occur according to an element's priority -- typically a weighted value in the range 0 to 1 (floating point value). In actual fact they are nothing more than sorted lists that implement a simple insertion sort. Locating the insert point is no better or worse whether dealing with an array or a singly-linked list but, with an array, all elements after the insert point must be shunted towards the end of the array to make a space for the insertion. Linked lists do not suffer from this, but there is additional work required to maintain the internal linkage of the nodes. Despite the extra work, linked lists generally perform better overall, because arrays will occasionally need to be resized.

During a priority queue insertion in a linked list, if there is no head node, a new node is created for the new element and the new node becomes the head node. Otherwise the element is passed to the head node. The head node compares its element to the new element. If the new element has a lower priority, it is passed to its next node for comparison. The element therefore passes from node to node until its priority is deemed greater than the current node or there is no next node. If there is no next node, a new node is created for the element which becomes the current node's next node, and the current node returns itself. Otherwise, a new node is created, it's next node points to the current node and the new node is returned. Whatever node is returned to the previous node becomes that node's next node, thus updating all the next pointers back to the head node and ultimately to the list itself. These return calls effectively permit two-way traversal of a singly-linked list, both to and from the insert point. Thus whatever node is returned by the head node becomes the new head node. To finish the process, the tail node is checked. If it is zero, then it points to the head node (there can only be one element in the list at that point, so it is both the head and tail of the list). If it is non-zero and its next pointer is also non-zero (which it normally wouldn't be), then the tail node becomes that next node because the new element must have ended up at the end of the list. It all sounds far more complex than it really is. Ultimately the list maintains its own internal linkage by delegating all the insertion work to the nodes themselves unless the list is empty, in which case the list simply creates a new node for the element and sets the head and tail to the new node.

Taking all of the above into account, it can clearly be seen that linked lists are ideally suited to implementing stacks and queues whereas arrays offer no advantages whatsoever. Comparing the memory consumption alone, arrays may use less memory overall, but in order to alleviate the burden of reallocating and copying elements an array ends up wasting memory for no good reason other than that arrays are not ideally suited to the task. Linked lists may use slightly more memory, but every byte is doing something useful to ensure the highest possible performance at all times.

Answer 5

A linked-list allows access to any element in the list by traversing the list and allows insertion and extraction at any point in the list. A stack implemented using a linked-list prevents traversal of the list and only allows insertion and extraction at the head of the list.

Answer 6

The only disadvantage of a stack or a queue is when they are used inappropriately. If we need a stack, we use a stack. If we need a queue, we use a queue. If we need something else, we use something else. Typically, we use a vector as our default data container unless we have good reason to use something else. It should be noted that a stack is simply an adaptor that modifies a vector such that all operations that are not required of a stack are eliminated.

Stacks are typically used to implement backtracking algorithms because elements are popped from the stack in the reverse order they were pushed onto it. Recursive functions provide automatic backtracking thus we only need a stack when we require backtracking without recursion.

Queues are typically used to synchronise an input process with an output process where the two may operate independently, possibly at different frequencies. For instance, when a process is busy it cannot receive messages from the operating system, thus messages intended for the process build up in the system message queue. Periodically, the process must yield control to the operating system in order to handle any pending messages before continuing with its work. Without a queue, those pending messages would be lost forever.

Answer 7

- dynamic memory allocation is possible by using link list.

- Avoid the problem of overflow.

- Memory utilization is better in link list than array implementation.