Join 149,540 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,524 people online right now. Registration is fast and FREE... Join Now!
Hi all. I have an assignment that asks me to implement a queue using arrays and linked lists, supporting the following functions (I assume I create them): Create, Enqueue, Dequeue, Empty, Print. I made a similar program (split into 2 files) that implemented a Stack using those, and supported Create, Push, Pop, Top,Empty, FindMax, FindMin, Print. The code for those is as follows, first as arrays then as linked lists:
int push(int val){ array[StackTop] = val; StackTop++; }
int pop(int val){ StackTop--; array[StackTop] = val; }
int top(){ int x = StackTop-1; int place = array[x]; printf("%d\n", place); }
int empty(){ int x = StackTop; StackTop = 0; while(StackTop != x){ array[StackTop] = 0; StackTop++; } }
int PrintStack(){ int x = StackTop; StackTop = 0; while(StackTop != x){ int place = array[StackTop]; printf("%d\n", place); StackTop++; } }
int FindMax(){ int x = StackTop; StackTop = 0; int y = array[StackTop]; int max = array[StackTop]; while(StackTop != x){ int place = array[StackTop]; if(max<y){ max = y; StackTop++; }else{ StackTop++; }
y = array[StackTop]; } printf("%d\n", max); }
int FindMin(){ int x = StackTop; StackTop = 0; int y = array[StackTop]; int min = array[StackTop]; while(StackTop != x){ int place = array[StackTop]; if(min>y){ min = y; StackTop++; }else{ StackTop++; }
y = array[StackTop]; } printf("%d\n", min); }
int main(){ int choice = 0; while(choice != 9){
printf("Pick a choice.\n"); printf(" 1) Create new stack\n"); printf(" 2) Push on the stack\n"); printf(" 3) Print the top value\n"); printf(" 4) Print the stack\n"); printf(" 5) Print max value in stack\n"); printf(" 6) Print min value in stack\n"); printf(" 7) Pop on the stack\n"); printf(" 8) Empty the stack\n"); printf(" 9) Quit\n");
typedef struct Node // new struct, linked list node { int value; // holds a value struct Node *next; // also holds a pointer to next node }Node; // for recursive reference.
//This function is optional. It creates an empty node at the head of an empty list.
void create(Node **head){ // void returns nothing, name = create, takes in Node head. if(*head == NULL){ Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = NULL; // Passes val, the user's input, to value, node's value slot. node->next = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. *head = node; // Head's parameters now = node's parameters I guess. }else{ printf("A list already exists\n"); } };
//This makes a new node, and inserts on the head of the list. Can be done whether or not there is a list.
void push(int val, Node **head){ // void type returns nothing. name is push. it takes in a user value and a Node. Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = val; // Passes val, the user's input, to value, node's value slot. node->next = *head; // Passes *head, the pointer to the head of the list, to the pointer of the current node. *head = node; // Head's parameters now = node's parameters I guess. }
//Deletes the top node...
int pop(Node **head){ // So its int, dunno why it isnt void int returnValue = -1; if(*head == NULL){ // catches if head is null. if it is, its the beginning of the list, so we can't delete. printf("Head = Null\n"); // does something to notify the user they are trying to do something bad. }else{ // if *head is anything but null. Node *temp = *head; // make a temp node and it equals head now. returnValue = temp->value; *head = temp->next; // basically, head = whatever it was pointing to. free(temp); // free up temp, its done being used. } return returnValue; }
//Prints the top node's value.
void top(Node *head){ // this just takes in a *pointer rather than **pointer, dunno why though. if(head == NULL){ // if head is null, its the beginning of the list. printf("Head = Null\n"); // prints this }else{ // otherwise printf("%d\n", head->value); // print head's value. } }
//Delete entire list
int empty(Node **head){ int returnValue = -1; while(*head != NULL){ Node *temp = *head; // make a temp node and it equals head now. returnValue = temp->value; *head = temp->next; // basically, head = whatever it was pointing to. free(temp); // free up temp, its done being used. } return returnValue; }
void PrintStack(Node **head){ Node *bla = head; // Allocates memory for Node *node. while(bla != NULL){ printf("%d\n", bla->value); // Head's pointed-at node (second node) is now the first thing of this second list bla = bla->next; } }
//Finds the maximum value held inside the list
int FindMax(Node **head){ Node *bla = head; // Allocates memory for Node *node. int x = bla->value; int max = bla->value; while(bla != NULL){ x = bla->value; if(max<x){ max = x; bla = bla->next; }else{ bla = bla->next; } } printf("%d\n", max); }
//Finds the minimum value.
int FindMin(Node **head){ Node *bla = head; // Allocates memory for Node *node. int x = bla->value; int max = bla->value; while(bla != NULL){ x = bla->value; if(max>x){ max = x; bla = bla->next; }else{ bla = bla->next; } } printf("%d\n", max); }
int main(){ Node *head = NULL; int choice = 0; while(choice != 9){
printf("Pick a choice.\n"); printf(" 1) Create new stack\n"); printf(" 2) Push on the stack\n"); printf(" 3) Print the top value\n"); printf(" 4) Print the stack\n"); printf(" 5) Print max value in stack\n"); printf(" 6) Print min value in stack\n"); printf(" 7) Pop on the stack\n"); printf(" 8) Empty the stack\n"); printf(" 9) Quit\n");
Do you understand the similarities and differences between a queue and a stack? That should go a long way towards answering your question. If you can point out the semantic differences, then you should be able to identify the parts of your Stack code where you need to make modifications. At least part of your stack code will likely be able to remain the same, depending on what kind of queue you're going to implement, the main alterations revolve around the introduction of a "front" and "rear" of the queue structure rather than just a top, which you have in your stack.
(Hint: Start out by concentrating on operations which modify the queue; ie, insertion & deletion. later on you can add the non-modifying operations, such as isEmpty, and FindMax. The non-modifying operations are probably going to be almost identical to your stack functions)
This post has been edited by Bench: 24 Nov, 2007 - 02:26 PM
In terms of understanding the differences/similarities between stacks and queues, I know that both are chunks of memory. A stack is a chunk of memory that is being used currently, and holding whatever necessary things for programs. The queue is accessible, unused, allocated(or unallocated?) memory. As I understand it you can put things in here as well, but I don't remember that explanation. Oh, and stack is FILO, whereas queue is FIFO.
I can implement any kind of queue that I want, but it should probably be as simple as possible. I don't see why I'd need a tail and a head. But, if its going to involve using both then I can just modify my prototype and change a few things.
Well, yes... and no. both can be used as a storage mechanism on a disk. Both can be implemented over a linked list making them a bunch of little chunks of memory. This is like saying, "Cars and trucks are chucks of metal" -- while is seems like a safe enough statement it is not really very accurate.
QUOTE
A stack is a chunk of memory that is being used currently
-- again... has nothing to do with anything.
QUOTE
The queue is accessible, unused, allocated(or unallocated?) memory
-- No... but this makes me think that maybe your definition of stack can be explained:
"The stack" or "the program stack" is actually chunk of memory used by the current program for temporary storage. this is a stack (and is usually called "the stack") but it is not the only stack.
"The heap" is the large expanse of free memory controlled by the operating system. Programs can request (allocate) chunks of this memory for their own use. A heap is another data structure unrelated to stacks and queues.
QUOTE
and stack is FILO, whereas queue is FIFO.
yes...
Stacks and Queues are "Abstract Data Structures" -- more specifically they are conceptual mechanism of how to store and retrieve data.
A stack can be thought of as stack of plates (it is best to think of those spring loaded plate stacking mechanisms popular at buffets) where you can only see the top plate. There are three possible simple operations with a stack... you can push a plate on the the stack, you can peek at the top plate, or you can pop it off the stack.
A queue is like a first grader a single file line to get cookies. The first person in the line is the first to get a cookie... the last person in line is the last person to get a cookie. There is no cutting in line. There are only two operations with a queue: enqueue, dequeue.
Note that stacks and queues may be implemented in many many different ways. That is why they are called "Abstract Data Structures" because they can be made out of plates, or first graders, or chunks of memory, files on a disk, abstract objects... what makes a stack of a queue is how it is used, not what it is made of.
In terms of understanding the differences/similarities between stacks and queues, I know that both are chunks of memory. A stack is a chunk of memory that is being used currently, and holding whatever necessary things for programs. The queue is accessible, unused, allocated(or unallocated?) memory.
I think you're getting confused between the term "stack" as described in compiler theory, versus a stack data structure. As NickDMax explained, a queue is no different in memory to a stack, and for your purposes, what happens in memory is the same that happens to any other program variables in memory - ie, the physical view of a stack and a queue is just as memory that belongs to your program. The important difference between a queue and a stack is the functionality that you, the programmer, give to it within your program. (mainly, how you add and remove elements from that memory)
QUOTE
I can implement any kind of queue that I want, but it should probably be as simple as possible. I don't see why I'd need a tail and a head. But, if its going to involve using both then I can just modify my prototype and change a few things.
That is what I would normally expect of a queue - You can't easily implement a queue without knowing where it starts and where it ends. Almost any queue should have 2 operations available to the user - Insert to the back, and Remove from the front. Which means that, unlike a stack, you generally need to insert and delete at opposite ends of the data structure.
removing an element from the beginning of an array has implications which can muddy the water somewhat. You essentially have two options; 1 - Move your "front" to the next position in the array or 2 - Copy every single element in the array from their current position to position-1
If you pick option 1 (The preferred option usually), and move your array front to the next position, you will eventually reach the end of the array to insert new data. From here, you'll probably find that you need to "wrap around" to the beginning of the array. Such a structure is more efficient than physically shifting each element of the queue; and the technique is known as a 'circular queue' or 'circular array'.
This post has been edited by Bench: 25 Nov, 2007 - 04:11 AM
Thanks for the info guys, I got the array implementation working perfectly now. I'm stuck on the linked list implementation. Specifically printing... every other function seems to work. Here's my code:
typedef struct Node // new struct, linked list node { int value; // holds a value struct Node *next; // also holds a pointer to next node }Node; // for recursive reference.
//This function is optional. It creates an empty node at the front of an empty list.
void create(Node **back, Node **front){ // void returns nothing, name = create, takes in Node front. if(*front == NULL && *back == NULL){ Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = NULL; // Passes val, the user's input, to value, node's value slot. node->next = *front; // Passes *front, the pointer to the front of the list, to the pointer of the current node. *front = node; // front's parameters now = node's parameters I guess. node->next = *back; // Passes *front, the pointer to the front of the list, to the pointer of the current node. *back = node; // front's parameters now = node's parameters I guess. }else{ printf("A list already exists\n"); } };
//This makes a new node, and inserts on the front of the list. Can be done whether or not there is a list.
void enqueue(int val, Node **back){ // void type returns nothing. name is push. it takes in a user value and a Node. Node *node = (Node*)malloc(sizeof(Node)); // Allocates memory for Node *node. node->value = val; // Passes val, the user's input, to value, node's value slot. node->next = *back; // Passes *front, the pointer to the front of the list, to the pointer of the current node. *back = node; // front's parameters now = node's parameters I guess. }
//Deletes the top node...
int dequeue(Node **front){ // So its int, dunno why it isnt void int returnValue = -1; if(*front == NULL){ // catches if front is null. if it is, its the beginning of the list, so we can't delete. printf("front = Null\n"); // does something to notify the user they are trying to do something bad. }else{ // if *front is anything but null. Node *temp = *front; // make a temp node and it equals front now. returnValue = temp->value; *front = temp->next; // basically, front = whatever it was pointing to. free(temp); // free up temp, its done being used. } return returnValue; }
//Delete entire list
int empty(Node **front){ int returnValue = -1; while(*front != NULL){ Node *temp = *front; // make a temp node and it equals front now. returnValue = temp->value; *front = temp->next; // basically, front = whatever it was pointing to. free(temp); // free up temp, its done being used. } return returnValue; }
void PrintQueue(Node **front){ Node *bla = front; // Allocates memory for Node *node. while(bla != NULL){ printf("%d\n", bla->value); // front's pointed-at node (second node) is now the first thing of this second list bla = bla->next; } }
int main(){ Node *front = NULL; Node *back = NULL; int choice = 0; while(choice != 6){
printf("Pick a choice.\n"); printf(" 1) Create new queue\n"); printf(" 2) Enqueue the queue\n"); printf(" 3) Dequeue the queue\n"); printf(" 4) Print the queue\n"); printf(" 5) Empty the queue\n"); printf(" 6) Quit\n");
| 