1
Algorithm Design.
Basic stack data structure Algorithm Design.
Department of Computer Science, University of the People
CS 3303: Data Structures
Instructor: Professor Mahmoud Mohanna
February 20, 2024
2
Algorithm Design.
Basic stack data structure Algorithm Design.
When considering the stack assignment to follow track of inspections within a
manufacturing assembly line, I came up with a stack implementation using either an array or
linked list. Here is a Java implementation for both methods, along with a brief explanation on
how they work and their asymptotic analysis.
Array Implementation of Stack
public class Stack {
private final int maxSize;
private final int[] stackArray;
private int top;
public Stack(int size) {
this.maxSize = size;
this.stackArray = new int[maxSize];
this.top = -1;
}
public void push(int element) {
if (isFull()) {
System.out.println("Stack is full. Cannot push element " + element);
} else {
top++;
stackArray[top] = element;
}
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot pop element.");
return -1;
} else {
int poppedElement = stackArray[top];
top--;
return poppedElement;
}
}
3
Algorithm Design.
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public static void main(String[] args) {
Stack stack = new Stack(10);
// Pushing elements onto the stack
stack.push(0);
stack.push(1);
stack.push(2);
// Popping elements from the stack
System.out.println(stack.pop()); // should print 2
System.out.println(stack.pop()); // should print 1
System.out.println(stack.pop()); // should print 0
// Trying to pop when the stack is empty
System.out.println(stack.pop()); // should print "Stack is empty. Cannot pop element."
}
}
Linked List Implementation of Stack
class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
this.next = null;
}
}
class Stack {
private Node top;
4
Algorithm Design.
// Push an element onto the stack
public void push(int value) {
Node newNode = new Node(value);
if (top != null) {
newNode.next = top;
}
top = newNode;
System.out.println("Pushed: " + value);
}
// Pop an element from the stack
public int pop() {
if (top == null) {
System.out.println("Stack is Empty");
return -1;
}
int poppedValue = top.value;
top = top.next;
System.out.println("Popped: " + poppedValue);
return poppedValue;
}
// Check if the stack is empty
public boolean isEmpty() {
return top == null;
}
}
public class ManufacturingStack {
public static void main(String[] args) {
Stack stack = new Stack();
// Push inspection stages onto the stack
stack.push(0); // Inspection not yet occurred
stack.push(1); // Inspection at stage 1
stack.push(2); // Inspection at stage 2
// Pop inspections as they occur
while (!stack.isEmpty()) {
stack.pop();
}
}
}
5
Algorithm Design.
Algorithm Explanation and Asymptotic Analysis Array Implementation:
Push Operation: O(1)- Pushing an item onto the stack is a constant time operation
because it involves appending an item to the end of the array.
Pop Operation: O(1)- Popping an item from the stack is also a constant time operation because it
involves removing an item from the end of the array.
In a Linked list implementation:
It will always take constant time to Insert and delete a node. The time complexity of
push() and pop() operations in a stack using linked list is O(1).
Both implementations serve their purpose but of course using the array-based implementation
has both its advantages and disadvantages.
The time complexity of both the implementations are the same but the linked list
implementation has a slightly better space complexity.
When posting an algorithm, it is always expedient to compare its efficiency with other
algorithms, focusing on the impact of the implementation choice (array vs. linked list) and how it
affects the performance and memory usage.
Word count: 589
6
Algorithm Design.
References:
Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg:
Virginia. Tech.
