© 2020 Vedesh Kungebeharry. All rights reserved.
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.
2023-09-14 – Fixed broken link to stack code
© 2020 Vedesh Kungebeharry. All rights reserved.
Here’s a small vid which shows the movement of data when we perform stack operations push,peek, pop on data stored in an array.
© 2020 Vedesh Kungebeharry. All rights reserved.
An ADT must possess the following characteristics:[1]
1. the facility to create a container to hold the data;
2. the facility to add a new element to the container;
3. the facility to remove/delete an element which satisfies some
criterion form the container;
4. the facility to find an element which satisfies some criterion within
the container;
5. the facility to destroy the container when it is no longer required.
[1] (Caribbean Examinations Council Computer Science Syllabus, 2015, p. 83)
Having studied the principle of a stack, we will list the principle of operation for a queue:
A queue models a real-life queue, for example, a queue (line) of people in a cafeteria waiting to order and pay for food.
The queue (line) of people can be thought of as a list with a :
Head or Front– the first person in the line, and the first to be served.
Tail or End – the last person in the line and the last to be served.
Every time an lunch order is processed, the head of the queue leaves the line, the entire line moves up , and the next person becomes the new head.
The queue ADT consists of a list of items and at least 3 reference variables which keep track of the location of the head, tail and the size of the queue. Operations on the queue are shown below:
| Operation | Explanation | Example |
| Add(..) or Enqueue(..) | Adds/Enqueues an item to the end of the queue and updates the tail to point to the newly added item. if the queue is full, the item is not added and an error message displayed. If the queue is empty, add the new item at the head. In this case the head and tail point to the newly added item. | A person joins the end of the line at the cafeteria. If the line is full, the person cannot enter the line. If the line is empty, the person goes straight to the head, i.e the cash register. |
| Remove(..) or Dequeue(..) | Removes/Dequeues and returns the item at the head of the queue. If the que is empty, the remove operation fails , an error message is displayed. An appropriate dummy/null value is returned. | Accept payment from the person at the cash register and send them on their way. If there are more people in the line, the line moves up and the person at the front of the line is at the cash register. |
| Peek(..) | returns the item at the head of the queue. If the que is empty, the peek operation fails , an error message is displayed. An appropriate dummy/null value is returned. | |
| Size(…) | Returns the size of the queue | |
| IsEmpty() | Returns true if the queue is empty, i.e, size==0 |
In creating a coded implementation of a queue using an array, we observe the following characteristics:
State:
| Variable | Description | Value at initialization |
| size | Integer to keep track of the size f the queue. | 0 |
| head | Integer to keep track of the front of the queue. This value stores the array index of the head/front | 0 |
| tail | Integer to keep track of the tail/end of the queue. This value stores the array index of the tail/end | -1 |
| MAX_SIZE | This stores he maximum size of the array; the array length | Sufficiently large, chosen by the programmer. |
Behavior:
Items are added/enqueued using the tail index, items are removed/dequeued using the head index.
If the queue is full
Cannot add, display error message
Else
Increment tail index
Place new data at tail index
Increment size
If the queue is empty
Display error message, return dummy value e.g -999
Else
Store the data that was at the head in a new variable, X
Increment the head index
Decrement size
Return X
If the queue is empty
Display error message, return dummy value e.g -999
Else
Return the data stored at head index
( updated – 14th October 2020)
© 2020 Vedesh Kungebeharry. All rights reserved
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.
)
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:
| Operation | Explanation |
| 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.
#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
#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;
}
#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
Previously we’ve dealt with primitive datatypes in C.
Examples of some primitive data types are shown below:
| Data Type | Example |
| integer | int a=5; |
| Floating point numbers | float a=5.1; |
| Character | char input =’q’; |
In this case we see that only one item of data is stored per variable declared.
Abstract Data Types (ADTs) store collections of data and are accompanied by functions which perform operations on the data.
They are created for use by programmers who in turn manipulate the data collection by use of the provided functions. The programmer using the ADT is never expected to directly manipulate the collection of data.
ADTs are used to model collections of data in real world scenarios.
An ADT consists of :
State- The container of items itself, information about the container of items e.g the size, a reference to the first item in the list etc
Behaviour – The operations that can be performed on the collection of data. Usually adding and/or, updating, and/or removing items.
The array is the considered to be a basic abstract data type that was formalized to use indexing during the development of high level languages. supporting programs were built to allow for the creation and management of data access to arrays.
If you’ve previously created c structures and managed their use through functions then you’ve created a specialized ADT. For example, our book catalog is an ADT.
Even though assignment and retrieval of data in array seems trivial and is supported by basic syntax as with other primitive data types; this was not the case during the early development of programming languages.
High level programming languages were modified so that arrays could use the basic syntax of variable declaration, initialization, assignment and access because of their expected widespread use.
© 2018Vedesh Kungebeharry. All rights reserved. Last Updated 17/9/2020.
Island Class 