STACK AND QUEUE
ABDALMOHAYMEN ALESMAEEL
AGENDA
• What is Stack
• Stack Types
• Most Important Operations (Push-POP)
• Real Applications
• Time Complexity
• What is Queue
• Queue Types
• Most Important Operations (Enqueue-Dequeue)
• Circular Queue
• Real Applications
• Time Complexity
STACK
• A Stack is a linear data structure that operates under the Last In, First Out (LIFO) principle, where the most
recently added element is the first to be removed. This operational order is essential for applications that
require a reverse sequence of actions or a history of operations.
Key functionalities of a stack include:
• Push: This operation adds an element to the top of the stack.
• Pop: This operation removes and returns the top element of the stack.
• Peek: This operation returns the top element without removing it, useful for observing the stack's current state.
• IsEmpty: This checks if the stack is empty, which is crucial for avoiding errors like stack underflow.
• Stacks are fundamental in managing recursive function calls and reversing data sequences, offering efficient O(1)
operations for push and pop. These features make stacks a vital component in programming and algorithm
design.
STACK TYPES
• Array Based
• LinkedList Based
A
ARRAY BASED STACK B
class ArrayStack<T>{ public T pop(){
T[] arr; if (isEmpty()) { C
int size=0; return null;
int top=-1; }
public ArrayStack(int size){ T item=(T)arr[top];
arr=(T[]) new Object[size]; arr[top]=null;
} top--;
public boolean isEmpty(){ return item;
return size==0; }
} }
public boolean isFull(){
return top==[Link]-1;
}
public void push(T item){
if (isFull()) {
return ;
}
arr[++top]=item;
}
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item;
}
Top=-1
55
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item;
}
Top=-1
55
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item;
}
Top=-1
55
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item;
}
Top=-1
55
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item; Top=0
}
55
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item; Top=0
}
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item; Top=0 55
}
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item; Top=0 55
}
33
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item; Top=0 55
}
33
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item; Top=0 55
}
33
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
top = top + 1;
stackArr[top] = item; Top=0 55
}
33
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
Top=1
top = top + 1;
stackArr[top] = item; 55
}
33
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
Top=1
top = top + 1;
stackArr[top] = item; 55
}
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
Top=1 33
top = top + 1;
stackArr[top] = item; 55
}
44
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
Top=1 33
top = top + 1;
stackArr[top] = item; 55
}
44
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
Top=1 33
top = top + 1;
stackArr[top] = item; 55
}
44
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return;
}
Top=1 33
top = top + 1;
stackArr[top] = item; 55
}
44
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return; Top=2
}
33
top = top + 1;
stackArr[top] = item; 55
}
44
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return; Top=2
}
33
top = top + 1;
stackArr[top] = item; 55
}
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return; Top=2 44
}
33
top = top + 1;
stackArr[top] = item; 55
}
StackDS<Integer> st=new StackDS<>(8);
[Link](55);
[Link](33);
[Link](44);
public void push(T item) {
if (isFull()) {
[Link]("Stack is full");
return; Top=2 44
}
33
top = top + 1;
stackArr[top] = item; 55
}
STACK UNDO EXAMPLE
class TextEditor{
TextEditor editor =new TextEditor();
String content; [Link]("Hello");
Stack<String> history; [Link](" World");
public TextEditor(){ [Link](" New");
content=""; [Link]([Link]()); // Output: Hello World New
history=new Stack<>(); [Link]();
} [Link]([Link]()); // Output: Hello World
public void write(String newText){ [Link]();
[Link](content); [Link]([Link]()); // Output: Hello
content+=newText; [Link]();
} [Link]([Link]()); // Output: (empty string)
public void undo(){ [Link]() ; // Output: empty
if (![Link]()) {
content=[Link]();
}else{ Stack History
[Link]("Empty");
}
Hello World [Link]();
}
public String read(){
Hello [Link]();
return content;
} [Link]();
}
DOUBLY LINKED LIST STACK
Implementing a stack using a doubly linked list can be achieved either by adding and removing elements from the
beginning (the head) of the list or from the end (the tail) of the list. Both approaches will maintain the Last In, First
Out (LIFO) property of a stack. Here are the two methods you
Add First and Delete First:
Push operation: Add a new element at the beginning (head) of the doubly linked list. This involves adjusting the
head pointer and possibly the previous pointer of the existing head element to point to the new element.
Pop operation: Remove the element at the beginning (head) of the list. Update the head to the next element in the
list and adjust the previous pointer of the new head to null.
Add Last and Delete Last:
Push operation: Add a new element at the end (tail) of the doubly linked list. This means adjusting the next pointer
of the current tail to point to the new element and updating the tail pointer to this new element.
Pop operation: Remove the element at the end (tail) of the list. This involves moving the tail pointer to the previous
element and setting its next pointer to null.
DOUBLY LINKED LIST STACK FROM FIRST
class DoublyLinkedListFirstStack<T>{ public T peek() {
LinkedList<T> items; if ([Link]()) {
int size; return null;
public DoublyStack(){ }
items=new LinkedList<>(); return [Link]();
size=0; }
} public boolean isEmpty() {
public void push(T item){ return [Link]();
[Link](item); }
size++; public int size() {
} return size;
public T pop(){ }
if ([Link]()) { }
return null;
}
T item=[Link]();
size--;
return item;
}
DOUBLY LINKED LIST STACK FROM LAST
class DoublyLinkedListFirstStack<T>{ public T peek() {
LinkedList<T> items; if ([Link]()) {
int size; return null;
public DoublyStack(){ }
items=new LinkedList<>(); return [Link]();
size=0; }
} public boolean isEmpty() {
public void push(T item){ return [Link]();
[Link](item); }
size++; public int size() {
} return size;
public T pop(){ }
if ([Link]()) { }
return null;
}
T item=[Link]();
size--;
return item;
}
DOUBLY LINKED LIST STACK PUSH FROM HEAD
head tail
Null Null
DOUBLY LINKED LIST STACK PUSH FROM HEAD
head tail
Null Null
DOUBLY LINKED LIST STACK PUSH FROM HEAD
head tail
Null
Null
DOUBLY LINKED LIST STACK PUSH FROM HEAD
head tail
Null
Null
DOUBLY LINKED LIST STACK POP FROM HEAD
head tail
Null
Null
DOUBLY LINKED LIST STACK POP FROM HEAD
head tail
Null
Null
DOUBLY LINKED LIST STACK POP FROM HEAD
head tail
Null
Null
REAL APPLICATIONS
• Undo Mechanisms in Software
• Web Browsers (Forward and Back Navigation)
• Expression Evaluation and Syntax Parsing
• Recursion (Function Call Management)
• Reverse String
• Parsing HTML and XML Documents
TIME COMPLEXITY
Task Complexity
POP O(1)
PUSH O(1)
PEEK O(1)
SEARCH O(N)
ToList O(N)
Print O(N)
QUEUE
A Queue is a linear data structure where the first item added is the first to be taken out. This is often summarized as
First In, First Out (FIFO). It's like waiting in line at a store— the first person in line is the first to be served.
Key features of a queue include:
• Enqueue: Adds an item to the end of the queue.
• Dequeue: Removes and returns the item at the front of the queue.
• Peek: Shows the first item without removing it, helpful for seeing who's at the front of the line.
• IsEmpty: Checks if the queue is empty, which helps prevent errors from trying to remove an item when there are
none.
Queues are used in many places, like when computers manage tasks that need to happen in the order they were
received or in organizing people waiting for customer service. They are fast and efficient, making sure everything is
handled in the order it arrives.
QUEUE TYPES
• Array Based
• Circular Array Based
• LinkedList Based
• Priority QUEUE
A
ARRAY BASED QUQUE B
class QueueArray<T>{ public T deQueue(){ C
T[] arr; if (size==0) {
int front=0; return null;
int rear=0; }
int size=0; T output=arr[front];
public QueueArray(int size){ arr[front]=null;
arr=(T[]) new Object[size]; front++;
} size--;
public void enQueue(T item){ return output;
if (rear==[Link]) { }
return ; }
}
arr[rear++]=item; QueueArray<String> q=new QueueArray<>(3);
size++; [Link]("A");
} [Link]("B");
[Link]("C");
[Link](); //A
[Link](); //B
[Link](); //C
ARRAY BASED CIRCULAR QUQUE
class CircularQueueArray<T>{ public T deQueue() {
T[] arr; if (size == 0) {
int front = 0; return null;
int rear = 0; }
int size = 0; T item = arr[front];
public CircularQueueArray(int capacity) { arr[front] = null; // Help with garbage collection
arr = (T[]) new Object[capacity]; front = (front + 1) % [Link]; //wrap-around
} size--;
public void enQueue(T item) { if (size == 0) {
if (size == [Link]) { front = 0;
return; rear = 0;
} }
arr[rear] = item; return item;
rear = (rear + 1) % [Link]; //wrap-around }
size++; }
}
DOUBLY LINKED LIST QUQUE
When implementing a queue using a doubly linked list, there are two primary approaches you can take to manage the
addition and removal of items. These approaches reflect the flexibility and efficiency benefits that doubly linked lists
provide over simpler data structures:
From First to Last:
Enqueue Operation: Add elements at the head (beginning) of the list.
Dequeue Operation: Remove elements from the tail (end) of the list.
This approach uses the head of the list to add new items and the tail to remove items, ensuring that elements move
through the list from the head towards the tail.
From Last to First:
Enqueue Operation: Add elements at the tail (end) of the list.
Dequeue Operation: Remove elements from the head (beginning) of the list.
In this method, elements are added at the tail and removed from the head, effectively processing items in reverse order
compared to the first approach.
head tail
Null
Null
DOUBLY LINKED LIST QUQUE
First To Last Last To First
public class QueueLinkedFirst<T> { public class QueueLinkedLast<T> {
private LinkedList <T> items; private LinkedList <T> items;
public QueueLinkedFirst() { public Queue() {
items = new LinkedList <>(); items = new LinkedList <>();
} }
public void enqueue(T item) { public void enqueue(T item) {
[Link](item); [Link](item);
} }
public T dequeue() { public T dequeue() {
if (is_empty()) { if (is_empty()) {
throw new IndexOutOfBoundsException("empty queue"); throw new IndexOutOfBoundsException("empty queue");
} }
return [Link](); return [Link]();
} }
public T peek() { public T peek() {
if (is_empty()) { if (is_empty()) {
throw new IndexOutOfBoundsException("empty queue"); throw new IndexOutOfBoundsException("empty queue");
} }
return [Link](); return [Link]();
} }
public boolean is_empty() { public boolean is_empty() {
return [Link](); return [Link]();
} }
} }
REAL APPLICATIONS
• Operating Systems
• Print Queue Management
• Call Center Systems
• Web Server Request Management
• Traffic Management
• Data Streaming
TIME COMPLEXITY
Task Complexity
ENQUEUE O(1)
DEQUEUE O(1)
PEEK O(1)
SEARCH O(N)