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:
| 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.
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
Island Class 
[…] Note that this attempt does not use a pointer to the top of the stack; instead we keep track of the size of the stack , much like our implementation found here : Stacks. […]
LikeLike