CODEWITHSUNDEEP
cdata-structureslinked-liststackqueue
Praveen Parihar
Praveen Parihar

Reputation: 292

Linked stacks and queues

Came across Linked Stacks and Queues in a book(and it is not stack/queue implementation using linked list). it says that stack/queue can be represented sequentially if we had only one stack/queue.However, when several stacks/queues coexisted ,then there is no efficient way to represent them sequentially. Below is the code given 

#define MAX_STACKS 10 //maximum number of stacks;
typedef struct {
        int key;
        //other fields.
}element;
typedef struct stack *stackpointer;
typedef struct {
        element data;
        stackpointer link;
}stack;
stackpointer top[MAX_STACKS];

void push(int i ,element item) {
     stackpointer temp;
     malloc(temp,sizeof(*temp));
     temp->data = item;
     temp->link = top[i];
     top[i] = temp;
}

Am newbie to data structures. Can I get the brief explantion of above concept i.e Linked Stacks/Queues.

Upvotes: 2

Views: 397

Answers (1)

Anshuman Kumar
Anshuman Kumar

Reputation: 577

So I checked out your book and I kind of understand what your problem is.

Such a representation proved efficient if we had only one stack or one queue. However, when several stacks and queues co−exist, there was noefficient way to represent them sequentially

So, by sequential, you must understand that it means using arrays to represent stacks and not a linked list. Now just assume that you have a matrix comprising of 10 arrays to represent each of size 100, and you push some data into each. Say you push only a few elements in each stack, what happens is that you end up wasting a lot of data as there are a 1000 elements in the matrix. This problem was there while using a single array but it becomes more pronounced when you have multiple arrays for multiple stacks.

Now as you might have understood, using the linked list representation of a stack uses as much memory as needed, with only a slight overhead of keeping track of the next element, in this case stackpointer link.

stackpointer top[MAX_STACKS]

So what we have done here is create an array of type stackpointer to keep track of the top position of each individual stack. So now whenever the user wishes to enter an element, they must pass the index(int i) as well as the data (element item).

void push(int i ,element item) 
{
     stackpointer temp;
     malloc(temp,sizeof(*temp));
     temp->data = item;
     temp->link = top[i];
     top[i] = temp;
}

So what we do is create a temp variable to store our data, which will now become the top of our stack but before doing so we must point it to the previous top of stack, (that is done in line 5) and in line 6, we just point the top[i] to temp. However, you might want to correct your code with this 

stackpointer temp = (stackpointer)malloc(sizeof(element));

If you have doubts, on malloc, just refer to this. If you have a doubt, let me know and I will clarify anything you need.

Upvotes: 1

Related Questions