Tag: Stacks

Stack Operations (Exercise)

vkunge1 Comment


After observing the code in this post (Stacks) , implement a stack with a maximum size of 5 elements using flowgorithm.

The program must continuously prompt the user for an option:

push -if the user enters push, prompt the user to enter an integer and push it onto the stack
pop -if the user enters pop, display the integer at the top of the stack and remove it
peek – If the user enters peek, display the integer at the top of the stack
exit – exits the program.

Ensure that the program works in all cases, e.g if the stack is full and and the user tries pushing another element, display an appropriate error message.

Updates to this post

2023-09-14 – Fixed broken link to stack code

© 2020  Vedesh Kungebeharry. All rights reserved. 

Stacks

vkunge2 Comments

A stack consists of a collection of items which analogous to  a real world stack of items stored on a desktop.

Discussion: Scenario of a traditional Inbox pile where new items are placed on the top of the stack. (Simalarity to: a/an

 Instagram feed

Cargo entering a ships container palate by palate, filled to capacity which must be processed by customs at the destination port.

Washing dishes collected after dinner.

)

Characteristics of a Stack

Form our discussion. We see that in a real life stack, the most recent item to enter the stack is the first to be processed and leave the stack.

We say that the Last item In is the First item Out (LIFO)

The stack ADT consists of a collection of items and an integer which keeps track of the size of the stack. 

The stack  supports the following operations:

OperationExplanation
Push(…)Adds an item to the top of the stack and returns the size of the stack. If an error occurs, return a negative number
Peek()Return the data at the top of the stack
Pop(…)Removes and Returns the item at the top of the stack, keeping track of the size.
IsEmpty()Returns true if the stack is empty, i.e, size==0

NB, When using a stack, the programmer only has access to the item stored at the top/head of the stack at any given point in time. The programmer is unable to access any other data that is stored under the top.

The top of the stack is also referred to as the head of the stack.

Coded example

Stack.h

#include <stdbool.h>
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

//push data if the stack is not full
bool push(int newData);

//returns the +ve integer at the 
//top of the stack or -1 if the stack is empty
int peek();

//Removes and returns the +ve integer at the 
//top of the stack or -1 if the stack is empty
int pop();

//returns the current size of the stack
int size();

//returns true if the stack is empty
bool isEmpty();


#endif // STACK_H_INCLUDED

Stack.c

#include <stdbool.h>
#include <stdio.h>
#define MAX_SIZE 10
#include "Stack.h"

int stackData[MAX_SIZE];
int sizeOfStack = 0;

bool push(int newData)
{

    if(sizeOfStack==MAX_SIZE)
    {
        puts("ERROR: Tried to push to a full stack. Operation failed\n");
        return false;
    }
    else
    {
        stackData[sizeOfStack]=newData;//add data to the next available location
        sizeOfStack++;//increment size
        return true;
    }



}

int peek()
{
    if(isEmpty())
    {
        puts("ERROR: Tried to peek at an empty stack. -999999 returned as result\n");
        return-999999;
    }

    else
        return stackData[sizeOfStack-1];//return item at the top of the stack
}

int pop()
{
    if(isEmpty())
    {
        puts("ERROR: Tried to pop an empty stack. -999999 returned as result\n");
        return -999999;
    }
    else
    {
        int result = stackData[sizeOfStack-1];//return item at the top of the stack
        sizeOfStack--;//reduce size
        return result;
    }

}

int size()
{
    return sizeOfStack;
}

bool isEmpty()
{
    return sizeOfStack==0;
}

Main.c

#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"
int main()
{
    //stack demo
    //try peeing at empty stack
    printf("%d\n",peek());

    //push 100,200,...,1000,1100 (push 11 numbers, 10 should be pushed, 1100 will not be pushed
    push(100);
    printf("%d\n",peek());
    push(200);
    printf("%d\n",peek());
    push(300);
    printf("%d\n",peek());
    push(400);
    printf("%d\n",peek());
    push(500);
    printf("%d\n",peek());
    push(600);
    printf("%d\n",peek());
    push(700);
    printf("%d\n",peek());
    push(800);
    printf("%d\n",peek());
    push(900);
    printf("%d\n",peek());
    push(1000);
    printf("%d\n",peek());
    push(1100);
    printf("%d\n",peek());

    //try displaying the size and popping 11 times.
    //failure expected on the 11th time.
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");
    printf("Size, Pop\n");
    printf("%d\n",size());
    printf("%d\n",pop());
    printf("\n\n");


    return 0;
}

© 2020 Vedesh Kungebeharry. All rights reserved