stack and queue with a link list

Question

I have an assignment where i need to implement a stack and a queue with a link list. How would i go about implementing it? would i use a circular link list and i can add to the head and tail? I wasnt looking for any code handouts and i dont think its fair that i got minus two points for asking a generalized question. This is how i think it should be done:

#pragma once

#include <ostream>

using namespace std;

class quack
{
public:
quack(int capacity);
~quack(void);
bool pushFront(const int n);    // push an item onto the front
bool pushBack(const int n);        // push an item onto the back
bool popFront(int& n);            // pop an item off the front
bool popBack(int& n);            // pop an item off the back
int    itemCount(void);            // return the current number of stored items

private:

 int front;
 int back;
 int maxsize;
 int count;

struct Node
{
Nutricalc Data;   // class wrapper?

Node* next;
};              


public:
friend ostream& operator<<(ostream& out, quack& q);
friend ostream& operator<<(ostream& out, quack::item& i);
};

Answer 1

neither a queue or a stack is circular so why would you use a circular linked list

you want a doubly linked list; one with forward and back pointers or an array

You could use the STL list; this is doubly linked list

Or STL vector if you want to use an array

of course you could get really cheeky and use STL stack and STL queue

Answer 2

Apparently, there was a communications issue and an understanding issue when linked lists were discussed by your professor. Hmmm, have you discussed this with your professor or teaching assistant?

Let us review.
A linked list is a bunch of nodes linked together:

+--------+---------+     +--------+---------+
|  Data  |  Link   | --> |  Data  | 0       |
+--------+---------+     +--------+---------+

A stack is a container where things are inserted and removed from the same end:

    +----+----+----+
--> |  3 |  2 | 1  |
<-- |    |    |    |
    +----+----+----+

This is how the structure looks after inserting 1, 2, then 3.

A stack that uses a linked list might look like:

+---+---+    +---+---+    +---+----+
| 3 |  ----->| 2 |  ----->| 1 | \0 |  where "\0" represents a null link.
+---+---+    +---+---+    +---+----+

Your task, should you choose to accept it, is to figure out how to link the nodes when an item is pushed onto the stack and also when an item is popped from the stack.

Hint: One step at a time, draw pictures.

Answer 3

Your linked list doesn't need to be circular. Remember that a stack is a Last-In-First-Out (LIFO) data structure and a queue is First-In-First-Out (FIFO). When you implement this think about which end of the list you add to and which end you remove from.