Data Structure
Stacks, Queues and Lists
Instructor: Hasan Alkhatib
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Definition
Stack is a data structure in which data is added and removed at only one end
called the top.
To add (i.e. push) an item to the stack, it must be placed on the top of the
stack.
To remove (i.e. pop) an item from the stack, it must be removed from the top
of the stack too.
Definition
Thus, the last element that is pushed into the stack is the first element to be
popped out of the stack.
o i.e., stack is a Last In First Out (LIFO) data structure
How stack works?
Definition - LIFO
Last In First Out is a method of organizing data, in which last item added to
the structure, will be the first to be retrieved.
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Stack Methods
purge() — Clear the stack.
isEmpty() — Check to see if the stack is empty.
push(el) — Put the element el on the top of the stack.
pop() — Take the topmost element from the stack.
peek() — Return the topmost element in the stack without removing it.
Stack Methods - Constructor
public class Stack<E>{
Object[] elementData;
int count = 0;
int initialCapacity = 10;
public Stack(){
array = new Object[initialCapacity];
}
Stack Methods – Clear
The purpose of the clear method is to remove all the contents of a container
public void clear() {
ListIterator<E> it = listIterator(fromIndex);
for (int i=0, n=size; i<n; i++) {
it.next(); it.remove();
}
}
Complexity is O(n)
Stack Methods - Push
push() method adds an element at the top the stack. It takes as argument an Object to be
pushed.
public T push(T obj) {
ensureCapacityHelper();
elementData[count] = obj;
count++;
}
Complexity is O(1)
Stack Methods - Peek
Peek() method first checks if the stack is empty,
public T peek() { then returns the top item in the stack without
removing that item
if (count == 0)
throw new EmptyStackException();
return elementData[count - 1);
}
Complexity is O(1)
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Stack Applications
Useful for any kind of problem involving LIFO data
Backtracking: in puzzles and games
Browsers: To keep track of pages visited in a browser tab
Stack Applications
Word Processors, editors: To check expressions or strings of text for matching
parentheses / brackets
Markup languages (e.g. HTML, XML): have formatting information (tags) as well as
raw text.
<HEAD>
<TITLE>Computer Science 1027a</TITLE>
</HEAD>
Stack Applications
Call stack (Runtime stack)
Used by runtime system when methods are invoked, for method call / return processing.
Stack Applications
Why we use stack structure for this purpose?
Because the first method to be called will be using returned values from the sub-methods.
So with stack popping the last called method will make sure that we use returned values
after performing their methods.
Stack Applications – Postfix
Evaluating Postfix Expression
● Using the regular form of arithmetic expressions is called infix-expression. i.e.
(5+9)*2+6
● The order of the arithmetic operations is determined by the precedence rules.
● However, there is an expression we can use called postfix-expression, and it can help
representing arithmetic operations.
Stack Applications – Postfix
● The advantage of postfix notation is that Postfix Infix
the order of operation evaluation is 16 2 / 16 / 2
unique without the need for precedence
rules or parenthesis. 2 14 + 5 * (2 + 14)* 5
2 14 5 * + 2 + 14 * 5
6 2 - 5 4 +* (6 – 2) * (5 + 4)
Stack Applications – Postfix
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as Circular Array
● Priority Queues
● Queue in Java
● Lists
Queues – Introduction
● Queues are linear data structures in which we add elements to one end and remove
them from the other end.
● The first item to be enqueued is the first to be dequeued. Queue is therefore called a
First In First Out (FIFO) data structure
Rear Front
3 1 4 Given this queue, how will it change when we
apply the following operations?
enqueue(1);
3 1 4 1
enqueue(5);
3 1 4 1 5
dequeue();
1 4 1 5
dequeue();
4 1 5 dequeue(); 1 5
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Queue Methods
enqueue(E e), offer(E e) — Add a new element to the end of the queue.
dequeue(), poll() — get the first element added to the queue, then delete it.
clear() — Remove all elements from the queue.
isEmpty() — Check if the queue has any elements.
getHead() — Return the first element added to the queue.
Queue Methods – Offer
//This code is used to clarify the specification, it’s not fully functional
public void offer(T obj) {
ensureCapacityHelper();
elementData[count] = obj;
count++;
}
Complexity is O(1)
Queue Methods – Poll
//This code is used to clarify the specification, it’s not fully functional
public T poll () {
T result = (T) elementData[0];
T tempLast = elementData[count];
elementData[count] = null;
count--;
if(count != 0)
shiftDown(tempLast);
return result;
Complexity is O(n)
}
Queue Methods – Clear
//This code is used to clarify the specification, it’s not fully functional
public void clear () {
for (int i=0, i<elementData.length; i++) {
elementData[i] = null;
}
count = 0;
}
Complexity is O(n)
Queue Methods – isEmpty
//This code is used to clarify the specification, it’s not fully functional
public Boolean isEmpty() {
return count>0 ? True : False;
}
Complexity is O(1)
Queue Methods – getHead
//This code is used to clarify the specification, it’s not fully functional
public T getHead() {
return (T) elementData[0];
}
Complexity is O(1)
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Queue as LinkedList
● In linked list mode we will use Head node and Last “Tail” node.
1 2 3 4 5
Head Tail
● After enqueuer(6) operation:
1 2 3 4 5 6
Head Tail
Queue as LinkedList
● After dequeuer() operation:
2 3 4 5 6
Head Tail
Queue as LinkedList – Cons
● Same cons for a regular LinkedList, each node will cost you a special location on
memory for the new instance.
● PS. Java chosen arrays to implement Queues.
Queue as Circular Array
● To overcome the memory issue, we use circular queue instead of linkedlist queue.
Queue as Circular Array
● head increases by 1 after each dequeue( )
● tail increases by 1 after each enqueue( )
0 1 2 3 48 49 50
New Queue: 1 2 3 …………………..
Head Tail
0 1 2 3 48 49 50
After enqueu(4): 1 2 3 4 …………………..
Head Tail
Queue as Circular Array
0 1 2 3 48 49 50
After dequeuer(): 2 3 4 …………………..
Head Tail
Queue as Circular Array – Exmple
0 1 2 3 48 49 50
Current Queue 4 ………………….. 46 47 48
Head Tail
0 1 2 3 48 49 50
After enqueue(49) 49 4 ………………….. 46 47 48
Tail Head
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Priority Queue
● Priority queue specification makes it an un-usual queue, it follows the FIFO concept in
the polling operation, but the offering operation is different.
● Think about the priority queue as a bag that hold priorities, in which the most important
element will be the next to be polled.
● Java uses a natural ordering to determine what to dequeuer from the queue.
الجديد هوHead وبناء على هذا الفحص يكون ال ً ،يعني أنه عند اإلضافة تقوم الجافا بفحص عناصر الطابور
. فإن الرقم األصغر أو الحرف األول هو األهم، وباعتبار الترتيب الطبيعي.العنصر األهم في الطابور كله
Priority Queue – How priority is determined?
● For example, in the next queue, the next element to be polled is the number (1),
because in natural ordering it’s smaller than other elements.
55 3 6 1
System.out.println(priorityQueue.poll()); 1
● However, you can tell java how to compare elements and determine what is more
important using Comparator interface.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(10,
new Comparator<Integer>() {
@Override
public int compare(Integer x, Integer y) {
if (x < y)
{
return 1;
}
else if (x > y)
{
return -1;
}
return 0;
}
});//This comparator will return bigger number first.
How to define priorities in PriorityQueue
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Queue in Java
● You can use the queue according to its specification by using ArrayDeque ADT in Java.
public E poll() {
public boolean offer(E e){
int h = head;
if (e == null)
@SuppressWarnings("unchecked")
throw new NullPointerException();
E result = (E) elements[h];
elements[tail] = e;
// Element is null if deque empty
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
if (result == null)
doubleCapacity();
return null;
elements[h] = null; // Must null out slot
}
head = (h + 1) & (elements.length - 1);
return result;
}
Agendas
● Stack Introduction
● Stack Methods & Implementation
● Application of Stack
● Queue Introduction
● Queue Implementation
● Queue as LinkedList vs as Circular Array
● Priority Queues
● Queue in Java
● Lists
Lists introduction
● In java, there is a set of abstract data types that represent a linear sequence of elements. These ADTs
implements the List interface in Java.
java.util.List
List Methods
Size() — Returns the number of added elements to List.
isEmpty() — Check if the list has any element.
get(index) — Returns the element that’s stored in specific index in list.
set(index, e) — Add an element in a specific index, the new element will override
the old one.
add(index, e) — Add an element in a specific index, the new element will shift the
next elements by 1.
remove(index) — Remove an element from a specific index in list. Other elements
will be shifted by -1.
List – Implementation Classes
ArrayList Operations Operation Complexity
ArrayList Get() O(1)
● Uses arrays to store data, and
Add(e) O(1)
double it by 150% when it’s full.
Add(index, e) O(n)
● There is no synchronization
when it comes to access it’s Set(index, e) O(1)
elements. Remove(index) O(n)
List – Implementation Classes
ArrayList Operations Operation Complexity
Vector Get() O(1)
● Uses arrays to store data too, but the
doubling is by 200% when it’s full. Add(e) O(1)
● Vector has synchronous access. Add(index, e) O(n)
Set(index, e) O(1)
Remove(index) O(n)
List – Implementation Classes
Other ADTs that has List interface:
● Stack
● LinkedList
