Stacks and queues info

I checked out that confuzzled site that i was refered to on another post. it goes thru things that seem a little too dificult at the moment. Can anyone give an example of how a stack and queue are used and how it relates to an STL. if it is an stl, can someone show how an stl is used?

I understand the concept of stack (LIFO) and Queue (FIFO) , just not how it looks in actual code. The text book i have just gives pseudo code.

Queues (#include <queue>) and stacks (#include <stack>) are both standard template libraries. You can use them both to see if a word is a palindrome, use a queue for evaluating prefix expressions, stacks for post fix, queues for waiting lines of tickets or something, so on and so on. An example of finding a palindrome would be like the following.

Code:

queue<char> q;
stack<char> st;
string input = "abceba"; //not a palindrome, but close
for(int n = 0; n < input.length(); n++){
    q.push(input.at(n)); //add to queue
    st.push(input.at(n)); //add to stack
}

for(int i = 0; i < input.length(); i++){ //now we check if its a palindrome
    if(q.pop() != st.pop()) cout<<"not a palindrome\n";
    //at this part it is removing the first letter from the stack, and first from the queue,
    //since they work in opposite order it is checking the first letter in the string vs. the last
    //and works its way to the middle
}

I typed this in the reply window so it might not be 100&#37; correct.

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

I understand the nontemplate way....somewhat. I see where its going. But with the template, push, pop, and other things are functions that are standard that u can use when do

Code:

#include<stack>
#include<queue>

So stacks and queues are implemented as classes? What I am refering to is

Code:

queue<char> q;
stack<char> st;
string input = "abceba"; //not a palindrome, but close
for(int n = 0; n < input.length(); n++){
    q.push(input.at(n)); //add to queue
    st.push(input.at(n)); //add to stack

So when u want to use a array. Is it called implementing an array as a stack?
Thanks again, the theory of this is starting to click, is it possible to show another example?

When you want to use an array, why would you want a stack? If you want an array, you use an array. Neither a queue nor a stack allows you random access to all the nodes, for example.

All we're doing in this example is using an array to "feed" both a stack and a queue. The three things are not actually related in any way.