Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A08 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A08 notes: Linked Stacks and Queues

In this lecture

• Kruse 3.1.6, 4.6
• Standish 7.6, 7.8

• The main benefit to using a linked structure for these data structures is so they are resizable - you don't run out of room.
• Uses nodes as entries in the stack or queue.
• Creating a new entry (using push or append) dynamically allocates space for a new node and links that node in.
• When removing an entry (using pop or serve), you must free the memory allocated to that node and update any values in the stack or queue.

Code for this lecture

/* linkStack.h */
#ifndef LINKSTACKH
#define LINKSTACKH

#include <stdbool.h> 
#include "node.h"

struct LinkedStackRec
{
  Node*  topPtr;
};

typedef struct LinkedStackRec  Stack;

void initializeStack(Stack* stackPtr);
bool stackFull(const Stack* stackPtr);
bool stackEmpty(const Stack* stackPtr);
void push(Stack* stackPtr, float item);
float pop(Stack* stackPtr);

#endif

/* linkStack.c */
#include <stdio.h>
#include <stdlib.h>
#include "linkStack.h"

/* Initialize a Linked Stack. */
void initializeStack(Stack* stackPtr)
{
  stackPtr->topPtr = NULL;
}

/* Push an item onto a Linked Stack. */
void push(Stack* stackPtr, float item)
{
  Node* newNodePtr = makeNode(item);

  newNodePtr->nextPtr = stackPtr->topPtr;
  stackPtr->topPtr = newNodePtr;
}

/* Pop an item off a Linked Stack. */
float pop(Stack* stackPtr)
{
  float item;
  Node* oldNodePtr = stackPtr->topPtr;

  if (stackEmpty(stackPtr))
  {
    fprintf(stderr, "Stack is empty\n");
    exit(1);
  }
  else
  {
    item = oldNodePtr->value;
    stackPtr->topPtr = oldNodePtr->nextPtr;
    free(oldNodePtr);
  }
  return item;
}

/* linkQueue.h */
#ifndef QUEUEH
#define QUEUEH

#include "node.h"

struct LinkedQueueRec
{
 int    count;
 Node*  frontPtr;
 Node*  rearPtr;
};

typedef struct LinkedQueueRec  Queue;

void intializeQueue(Queue* queuePtr);
bool queueEmpty(Queue* queuePtr);
bool queueFull(Queue* queuePtr);
void append(Queue* queuePtr, float item);
float serve(Queue* queuePtr);

#endif

/* linkQueue.c */
#include <stdio.h>
#include <stdlib.h>
#include "linkQueue.h"

/* Initialize a Linked Queue to be empty. */
void initializeQueue(Queue* queuePtr)
{
  queuePtr->frontPtr = NULL;
  queuePtr->rearPtr = NULL;
  queuePtr->count = 0;
}

/* Returns true if queue is empty */
bool queueEmpty(const Queue* queuePtr)
{
  if (queuePtr->count <= 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}

/* Returns true if the queue is full */
bool queueFull(const Queue* queuePtr)
{
  return false;
}

/* Append an item to the rear of the queue. */
void append(Queue* queuePtr, float item)
{
 Node* newNodePtr = makeNode(item);

 if (queueEmpty(queuePtr))
 {
   queuePtr->frontPtr = newNodePtr;
   queuePtr->rearPtr = newNodePtr;
   queuePtr->count = 1;
 }
 else
 {
   queuePtr->rearPtr->nextPtr = newNodePtr;
   queuePtr->rearPtr = newNodePtr;
   queuePtr->count++;
 }
}

/* Serve the item at the front of a Linked Queue. */
float serve(Queue* queuePtr)
{
  float item;
  Node* oldNodePtr = queuePtr->frontPtr;

  if (queueEmpty(queuePtr))
  {
    fprintf(stderr, "Queue is empty\n");
    exit(1);
  }
  else
  {
    item = oldNodePtr->value;
    queuePtr->frontPtr = oldNodePtr->nextPtr;
    queuePtr->count--;

    free(oldNodePtr);

    if (queuePtr->count == 0)
    {
       queuePtr->rearPtr = NULL;
    }
  }
  return item;
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:02:58