And a simple (non-template) implementation in C or C++ can be done using a linked list (or vector).

In the case of a linked list, we can use a structure like this:

Code:

struct node
{
int value;
node *next;
};

The real difference is in the push/pop functionality:

stack pushes and pops at the same end of the list, the head (or top):

Code:

node *stack_push(node *head, int value)
{
node *tmp = new node;
tmp->value = value;
tmp->next = head;
return tmp;
}

Call with "head = stack_push(head, x);"

A queue pushes elements to the back of the list (which means that you have to have a TAIL and a HEAD):

Code:

node *queue_push(node *tail, int value)
{
node *temp = new node;
tmp->value = value;
tail->next = tmp;
return tmp;
}

Call with "tail = queue_push(tail, x);"

The pop operation would be the same for both:

Code:

node *pop(node *head, int &value)
{
assert(head);
value = head->value;
node *tmp = head;
head = head->next;
delete tmp;
return head;
}

Call with "head = pop(head, x);"

--

Mats