Thread: Stacks and queues info

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