• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Stacks and Queues C++

Status
Not open for further replies.
Level 8
Joined
Oct 9, 2011
Messages
101
Hello guys,

Can anybody teach me how to make stacks and queues and only using
#include<iostream>
using namespace std;

I need to learn how to make stacks and queues using linked list and one using arrays

A simple yet easy to understand explanation will do :))

I need to learn before tomorrow XD
 

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,180
For the linked list implementation... Do note that I am writing this without testing it, so there might be some mistakes but hopefully nothing you cannot repair... Also DATATYPE has to be declared as the data type you want the queue to store, possibly as a template parameter. This solution is not thread safe, it would need mutexes for that which would need another header.

The idea is that of a doubly linked list with the list pointer being to the head node. FIFO mode is achieved by removing the head and replacing it with its next node while FILO mode is achieved by getting the last node (from the head node due to being a cyclic doubly linked list) and removing that instead. All 3 standard operations (add, dequeue and pop) have a complexity of O(1).

C++:
class DoublyLinkedList {
private:
    struct Node {
        Node *next;
        Node *prev;
        DATATYPE data;

        void insertAfter(Node *prev) {
            next = prev->next;
            this->prev = prev;
            prev->next = this;
            next->prev = this;
        }

        void remove() {
            prev->next = next;
            next->prev = prev;
            next = this;
            prev = this;
        }

        Node() {
            next = this;
            prev = this;
        }
    };

    Node *head;

public:
    DoublyLinkedList() : head() {}

    ~DoublyLinkedList() {
        // need to destroy all nodes on destruction to prevent memory leak
        while (!isEmpty()) {
            pop();
        }
    }

    // adds data to end of queue
    void add(DATATYPE data) {
        Node *const node = new Node();
        node->data = data;
        if (head) {
            node->insertAfter(head->prev);
        } else {
            head = node;
        }
    }

    // returns true if queue is empty
    bool isEmpty() {
        return !head;
    }

    // Retrieves and removes the head of the queue (queue mode operation). Only call when isEmpty returns false.
    DATATYPE dequeue() {
        Node *const node = head;
        DATATYPE const data = node->data;
        if (node->next != node) {
            head = node->next;
            node->remove();
        } else {
            head = 0;
        }
        delete node;
        return data;
    }

    // Retrieves and removes the end of the queue (stack mode operation). Only call when isEmpty returns false.
    DATATYPE pop() {
        Node *const node = head->prev;
        DATATYPE const data = node->data;
        if (node != head) {
            node->remove();
        } else {
            head = 0;
        }
        delete node;
        return data;
    }
}
 
Last edited:

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,180
The above doesn't initialize head to null, right?
It should according to some stack helper topics I read which say that NULL is the value for the default constructor for pointers...

Problem is NULL is defined in headers he may not have access to, so a constant of 0 (which should function like modern NULL for most purposes) has to be used instead. I was not sure what constructors are available for a pointer type and default sounded like it did what was needed according to some topics I read. This was meant to be pseudo code for the linked list implementation more than an actual implementation as I did not make the syntax perfect or test it.
 
Level 14
Joined
Dec 12, 2012
Messages
1,007
Just to add a bit on the stuff here:

head is initialized to zero. This is called value initialization ("otherwise, the object is zero-initialized.").

About the value itself... just use nullptr, thats more robust anyway.


But my real suggestion is: use none of these. Just use unique_ptr instead, then you don't have to take care about initialization. Also this will make the code exception safe, because the problem in the above implementation is, that if for example the copy constructor throws, you have a memory leak. If you don't want to use that header, write a small smart pointer class yourself, this is also a good exercise.
 
Status
Not open for further replies.
Top