Stacks and queues info

This is a discussion on Stacks and queues info within the C++ Programming forums, part of the General Programming Boards category; I checked out that confuzzled site that i was refered to on another post. it goes thru things that seem ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    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.

  2. #2
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    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?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 05-04-2009, 07:54 PM
  2. linked lists, stacks and queues
    By aniramg69 in forum C Programming
    Replies: 10
    Last Post: 11-29-2008, 10:58 AM
  3. stacks and queues
    By j0hnb in forum C Programming
    Replies: 4
    Last Post: 04-16-2003, 09:44 PM
  4. using Stacks & Queues to compare Strings
    By eskimo083 in forum C++ Programming
    Replies: 1
    Last Post: 03-09-2003, 04:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21