Data Structures & Algorithms Assignment 1: Implementation and Analysis

This document presents a comprehensive solution to a Data Structures and Algorithms assignment, focusing on the implementation and analysis of stack and queue data structures. The assignment covers the creation of design specifications for data structures, explaining valid operations. It details the operations of a memory stack and its use in function calls. The solution includes the specification of abstract data types and algorithms using imperative definitions, specifically for a software stack. Furthermore, it provides the implementation of complex ADTs and algorithms in an executable programming language, along with error handling and test results. The document also discusses the use of asymptotic analysis to assess algorithm effectiveness and illustrates two methods for measuring algorithm efficiency with examples. Detailed code implementations using arrays are provided for both stack and queue data structures, including operations like push, pop, enqueue, dequeue, peek, and isEmpty. The solution also covers the applications of stack and queue in various scenarios, such as balancing symbols, function calls, memory management, and asynchronous data transfer. Overall, the assignment provides a thorough understanding of data structures and algorithms, their implementations, and their practical applications.

PROGRAM TITLE: BTEC-COMPUTING
UNIT TITLE: Data Structures & Algorithms
ASSIGNMENT NUMBER: 1
ASSIGNMENT NAME: Assignment BKC
SUBMISSION DATE:
DATE RECEIVED: 28/01/2022
TUTORIAL LECTURER: Nguyen Duc Giang
WORD COUNT: 6646
STUDENT NAME: NGUYEN PHUONG NAM
STUDENT ID: BKC18316
MOBILE NUMBER: 0388898670

Summative Feedback
Internal verification
CONTENT
LO1 Examine abstract data types, concrete data structures and algorithms.............................................3

P1 Create a design specification for data structures explaining the valid operations that can be carried out
on the structures............................................................................................................................................3
P2 Determine the operations of a memory stack and how it is used to implement function calls in a
computer.......................................................................................................................................................3
LO2 Specify abstract data types and algorithms in a formal notation.............................................................11
P3 Using an imperative definition, specify the abstract data type for a software stack...............................11
LO3 Implement complex data structures and algorithms...............................................................................13
P4 Implement a complex ADT and algorithm in an executable programming language to solve a well-
defined problem..........................................................................................................................................13
P5 Implement error handling and report test results....................................................................................17
LO4 Assess the effectiveness of data structures and algorithms.....................................................................21
P6 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm....................21
P7 Determine two ways in which the efficiency of an algorithm can be measured, illustrating your answer
with an example..........................................................................................................................................29
References......................................................................................................................................................33
LO1 Examine abstract data types, concrete data structures and algorithms
P1 Create a design specification for data structures explaining the valid operations that can be
carried out on the structures.
1. Stack Data Structure:
What is a stack?
Stacks are linear data structures that follow the specific order in which operations are
performed. The command may be LIFO (Last In First Out) or FILO (First In Last Out).
There are many examples of real life piles. Consider the example of plates stacked against

each other in the cafeteria. The plate at the top is the first to be removed, which is the
plate that has been placed in a permanent camping position on the heap for the longest
time. Therefore, it can only be seen following the LIFO (Last In First Out) / FILO (First
In Last Out) command. In particular, the following three basic operations are performed in
heaps:
 Push: Adds items in the stack. If the pile is full, then it is said to be overflow.
 Pop: Removes items from the stack. These items appear in reverse order in which
they are rejected. If the pile is empty, then it is called Underflow condition.
 Peek or Top: Returns the top focus element.
 isEmpty: Returns true if the stack is empty, else false
How to understand a stack practically?
There are many real-life examples of a stack. Consider the simple example of plates stacked over
one another in a canteen. The plate which is at the top is the first one to be removed, i.e. the plate
which has been placed at the bottommost position remains in the stack for the longest period of
time. So, it can be simply seen to follow the LIFO/FILO order.
Time Complexities of operations on stack:
push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these
operations.
Applications of stack:
 Balancing of symbols
 Infix to Postfix /Prefix conversion
 Redo-undo features at many places like editors, photoshop.
 Forward and backward feature in web browsers
 Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem,
histogram problem.
 Backtracking is one of the algorithm designing techniques. Some examples of backtracking
are the Knight-Tour problem, N-Queen problem, find your way through a maze, and game-
like chess or checkers in all these problems we dive into someway if that way is not efficient
we come back to the previous state and go into some another path. To get back from a
current state we need to store the previous state for that purpose we need a stack.
 In Graph Algorithms like Topological Sorting and Strongly Connected Components
 In Memory management, any modern computer uses a stack as the primary management for
a running purpose. Each program that is running in a computer system has its own memory
allocations
 String reversal is also another application of stack. Here one by one each character gets
inserted into the stack. So the first character of the string is on the bottom of the stack and
the last element of a string is on the top of the stack. After Performing the pop operations on
the stack we get a string in reverse order.
Implementing Stack using Arrays
Create Arrays #define MAX 1000
class Stack {
int top;
public:

Push Stack
Pop Stack
bool Stack::push(int x)
{
if (top >= (MAX - 1)) {
cout << "Stack Overflow";
return false;
}
else {
a[++top] = x;
cout << x << " pushed into stack\n";
return true;
}
}
int Stack::pop()
{
if (top < 0) {
cout << "Stack Underflow";
return 0;
}
else {
int x = a[top--];
return x;
}
}}

Peek Stack
isEmpty()
int Stack:: peek ()
{
if (top < 0) {
cout << "Stack is Empty";
return 0;
}
else {
int x = a[top];
return x;
}
}}
Bool Stack::isEmpty()
{
return (top < 0);
}

2. Queue Data Structure:
What is a queue?
Queue is a linear structure which follows a particular order in which the operations are performed.
The order is First In First Out (FIFO). A good example of queue is any queue of consumers for a
resource where the consumer that came first is served first.
The difference between stacks and queues is in removing. In a stack we remove the item the most
recently added; in a queue, we remove the item the least recently added.
Operations on Queue:
Mainly the following four basic operations are performed on queue:
 Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow
condition.
 Dequeue: Removes an item from the queue. The items are popped in the same order in
which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
 Front: Get the front item from queue.
 Rear: Get the last item from queue.
Applications of Queue:
Queue is used when things don’t have to be processed immediately, but have to be processed in
First InFirst Out order like Breadth First Search. This property of Queue makes it also useful in
following kind of scenarios.
1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk
Scheduling.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.
Array implementation Of Queue
Create Queue
class Queue {
public:
int front, rear, size;
unsigned capacity;
int* array;
};
// function to create a queue
Queue* createQueue(unsigned capacity)
{
Queue* queue = new Queue();

Enqueue
Dequeue
void enqueue(Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)
% queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " enqueued to queue\n";
}
int dequeue(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size = queue->size - 1;
return item;
}

Front
Rear
P2 Determine the operations of a memory stack and how it is used to implement function calls in a
computer.
int front(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
int rear(Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}

The operations of a memory stack
Memory stack is a linear data structure (location) used to store data in the computer's
memory. They can also be called queues. Data in a stack must always be the same type.
An example of a stack is illustrated on the below:
Examples of Stacks/ Queues.
Items in the stack are inserted or deleted in a linear order and do not follow any random
string. As in any queue or collection that is assembled, data items in the stack are stored
and accessed in a specific way. In this case, a technique called LIFO (Last In First Out) is
used. This involves a series of insert and removal operations that we will discuss in the
following section.
LIFO (Last In First Out)
When a stack is accessed (there are inserted or deleted items), it is done in an orderly
manner by LIFO. LIFO stands for Last In First Out. Computers use this method to request
service data that the computer's memory receives. LIFO dictates that data is last inserted
or stored in any particular stack, must be the first data to be deleted. If that applies to our
queue for movies in Figure 1 above, there will be chaos! The operations on the stack are
discussed in the following sections with image on the below:

Stack Operations
1. The Push Operation
Push operation involves inserting data items into a stack. Let us check our restaurant
plate dispenser in Figure 9. Operation pushes additional plates (data items) into the
plate dispenser (stack). The first plate is pushed down to the bottom of the stack with
all subsequent plates in the following order after it. The first inserted data item is the
most inaccessible and is located at the bottom of the stack.
2. The Pop Operation
Pop operation involves removing data items from the loaded stack. In our plate
distributor illustration, the last sheet (data item) added is placed at the top of the stack.
This data item is turned off the stack as the first item is deleted. Think of the spring
loading system in the base of the plate distributor. It pushes the stack on top each time
you remove the plate. In memory, items continue to be turned on in that order.
3. The Peek Operation
In this operation, no data items are added or deleted from the stack. The snapshot
operation only requires the address location of the data item at the top of the stack (the
last item is pushed).
4. The Search Operation
In this operation, it do not have any data items are added or deleted from the stack.
The search operation require that geographical local of any data items in the stack. It
located the item at the top of thestack.