Queue & Stack
Second Year
(Computer Science and Computer
Technology)
Prepared by
Daw Yee Mon Kyaw
6/20/2024 UCS(Mgy) 1
Queue (တန်းစီ)
Queue
A queue is a data structure used to model a First-
In-First-Out (FIFO) strategy, that is the item first put
into the queue will be the first served, the second item
added to the queue will be the second to be served and
so on.
A traditional queue only allows you to access the
item at the front of the queue; when you add an item
to the queue that item is placed at the back of the
queue.
6/20/2024 UCS(Mgy) 3
Methods of Queue
Queue always have the following three core
methods,
• Enqueue: places an item at the back of the queue;
• Dequeue: retrieves the item at the front of the queue,
and removes it from the queue;
• Peek: retrieves the item at the front of the queue
without removing it from the queue.
6/20/2024 UCS(Mgy) 4
Types of Queue
• A standard Queue
• Priority Queue
• Double Ended Queue
6/20/2024 UCS(Mgy) 5
A standard Queue
• The main property of a queue is that we have access to the item
at the front of the queue.
• The queue data structure can be efficiently implemented using a
singly linked list
• The run time complexity for searching a queue remains the same
as that of singly linked list:O(n).
Dequeue/ Enqueue/
Deletion Insertion
Front Back
6/20/2024 UCS(Mgy) 6
Priority Queue
• A priority queue determines the order of its items by using a
form of custom comparer to see which item has the highest
priority.
• the items in a priority queue being ordered by priority it
remains the same as a normal queue: It can only access the
item at the front of the queue.
• a priority queue is to use a heap data structure (Heap tree).
Enqueue
Dequeue
Element with the Element with the
highest priority lowest priority
6/20/2024 UCS(Mgy) 7
Double Ended Queue
• A double ended queue allows to access the items at both the
front, and back of the queue.
• A double ended queue is commonly known as a “Dequeue”
• A dequeue applies no prioritization strategy to its items like a
priority queue does, items are added in order to either the
front of back of the dequeue.
Deletion Insertion
Insertion Front Back Deletion
6/20/2024 UCS(Mgy) 8
Stack
Stack
Stack is a linear data structure which follows a particular order in
which the operations are performed.
Stack is also called last in first out (LIFO) or First in last out
(FILO)system
Insertion of element into stack is called PUSH and deletion of
element from stack is called POP.
PUSH POP
FIRST IN LAST OUT LAST IN FIRST OUT
TOP 5
4
3
2
1 NEXT NULL
6/20/2024 UCS(Mgy) 10
Memory Management
Stack
The stack can be 206
Pointer
implemented into two ways:
• Using arrays (Static
4
implementation)
6 Room for growth
• Using pointer (Dynamic
7 2 7 6 4
implementation)
2
Stack 203 204 205 206 207 208
Figure 6 : Stack Pointers
University of Computer Studies, FCS 11
Methods of Stack
• EmptyStack, the empty stack.
• Push(element,stack), which takes an element and
pushes it on top of an existing stack.
• Pop(stack), which gives back the stack without
the top most element.
• top(stack), which gives back the top most
element of a stack.
6/20/2024 UCS(Mgy) 12