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

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A03 notes: Basic Data Structures - Stacks

In this lecture

• Kruse - Chapters 3.1.1 - 3.1.5
• Deitel & Deitel - Chapter 12.5
• Langsam - Chapter 2
• Standish - Chapters 7.1 - 7.6

• A sequence of items in which all insertions and deletions are made at one end, called the top of the stack.
• Also called Last-In First-Out lists, or LIFO lists.
• Items are put onto the top of the stack with the push operation.
• Items are taken off the top of the stack with the pop operation.
• Used when calling functions.
• Used when implementing recursion.

Code for this lecture

/* stack.h */
#ifndef STACKH
#define STACKH

#include <stdbool.h>

#define MAXSTACK 20

struct StackRec
{
  int top;
  float entry[MAXSTACK];
};

typedef struct StackRec  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

/* stack.c */

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

/* Initialize the stack to be empty.  */
void initializeStack(Stack* stackPtr)
{
   stackPtr->top = -1;
}

/* Returns true if the stack is full.  */
bool stackFull(const Stack* stackPtr)
{
   if (stackPtr->top >= MAXSTACK-1)
   {
      return true;
   }
   else
   {
      return false;
   }
}

/* Returns true if the stack is empty.  */
bool stackEmpty(const Stack* stackPtr)
{
   if (stackPtr->top < 0)
   {
      return true;
   }
   else
   {
      return false;
   }
}

/* Push a float onto the Stack.  */
void push(Stack* stackPtr, float item)
{
   if (stackFull(stackPtr))
   {
     fprintf(stderr, "Stack is full\n");
     exit(1);
   }
   else
   {
     stackPtr->top++;
     stackPtr->entry[stackPtr->top] = item;
   }
}

/* Pop a float from the stack.  */
float pop(Stack* stackPtr)
{
   float item;

   if (stackEmpty(stackPtr))
   {
      fprintf(stderr, "Stack is empty\n");
      exit(1);
   }
   else
   {
      item = stackPtr->entry[stackPtr->top];
      stackPtr->top--;
   }
   return item;
}

#include <stdio.h>
#include "stack.h"

/* Reverse a sequence of numbers */
int main()
{
   Stack theStack;
   float next;

   initializeStack(&theStack);

   printf("Enter number sequence: ");
   while(scanf("%f", &next) != EOF)
   {
     if (!stackFull(&theStack))
     {
       push(&theStack, next);
     }
   }

   printf("Sequence of numbers reversed: ");
   while (!stackEmpty(&theStack))
   {
     next = pop(&theStack);
     printf("%f", next);
   }
   printf("\n");
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:00:57