Array vs Stack – Differences Explained

arraydata structuresstack

According to Wikipedia, a stack:

is a last in, first out (LIFO) abstract data type and linear data structure.

is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.

As far as I understand, they are fairly similar. So, what are the main differences? If they are not the same, what can an array do that a stack can't and vice-versa?

Best Answer

Well, you can certainly implement a stack with an array. The difference is in access. In an array, you have a list of elements and you can access any of them at any time. (Think of a bunch of wooden blocks all laid out in a row.)

But in a stack, there's no random-access operation; there are only Push, Peek and Pop, all of which deal exclusively with the element on the top of the stack. (Think of the wooden blocks stacked up vertically now. You can't touch anything below the top of the tower or it'll fall over.)

Related Solutions

Data Structures – Abstract Data Type vs Data Structure

Simply put, an ADT (Abstract Data Type) is more of a logical description, while a Data Structure is concrete.

Think of an ADT as a picture of the data and the operations to manipulate and change it.

A Data Structure is the the real, concrete thing. It can be implemented and used within an algorithm.

Reverse Subarray – How to Reverse an Array Subarray with O(1) Space

You could use a xor linked list variant (using indexes into an array for the pointer).

Then reversing is easy:

reverse(int city1prev, int city1index, int city2prev, int city2index)
{

    int city1next = array[city1index].ptr^city1prev;
    int city2next = array[city2index].ptr^city2prev;

    city1.ptr = city2next^city1next;
    city2.ptr = city2prev^city1prev;

    array[city1prev].ptr^= city1index^city2index;
    array[city2next].ptr^= city1index^city2index;

}

The downside is (as with all linked list implementations) that indexing into it is O(n).

This will reverse the sub array due to how the xor link works: city2 will be where city1 used to be and city2prev will be after it and so on. So the new sequence becomes: city1prev, city2, city2prev,..., city1next, city1, city2next.

Key point is that there is no difference between traversing a xor linked list forward or backward (you keep a index to the current and the previous items and you get the next by doing array[current].ptr^previous).

Best Answer

Related Solutions

Data Structures – Abstract Data Type vs Data Structure

Reverse Subarray – How to Reverse an Array Subarray with O(1) Space

Related Topic