Chapter Four: Stacks and Queues

Data Structures and Algorithms

Prepared by:
Ataklti Nguse

07/07/2023 Ataklti N. 1
 4.1. Stack
Stack is a linear data structure which follows a particular order in which the
operations are performed.

A stack is a list with the restriction that insertions and deletions can be
performed in only one position, namely, the end of the list, called the top.

Stacks are known as LIFO (Last In, First Out) lists.

07/07/2023 Ataklti N. 2
 Operations of Stack

IsEmpty: return true if stack is empty, return false otherwise(underflow)

IsFull: return true if stack is full, return false otherwise(overflow)

Top: return the element at the top of stack

Push: add an element to the top of stack

Pop: delete(accessing) the element at the top of stack

DisplayStack: print all the data in the stack

primary operations are − Push and POP

Example??

07/07/2023 Ataklti N. 3
 …Continue
Example of A stack of cafeteria trays, stack of books, stack of computer box in
store.
Any list implementation could be used to implement a stack
– Arrays (static: the size of stack is given initially)
– Linked lists (dynamic: never become full)

07/07/2023 Ataklti N. 4
 Array Implementation

Need to declare an array size ahead of time

Associated with each stack is TopOfStack
– for an empty stack, set TopOfStack to -1
• Push
– (1)   Increment TopOfStack by 1.
– (2)   Set Stack[TopOfStack] = X
• Pop
– (1)   Set return value to Stack[TopOfStack]
– (2)   Decrement TopOfStack by 1

When the stack is full, top will have its maximum value, i.e. size – 1.
Initially top is set to -1. It means the stack is empty.

07/07/2023 Ataklti N. 5
 Linked List Implementation of Stacks

It’s very similar to the insertion operation in a dynamic singly linked list.

The only difference is that here you'll add the new element only at the end of the
list.

which means addition can happen only from the TOP.

– In Step [1] we create the new element to be pushed to the Stack.
– In Step [2] the TOP most element is made to point to our newly created element.

– In Step [3] the TOP is moved and made to point to the last element in the stack,
which is our newly added element.

Since a dynamic list is used for the stack, the Stack is also dynamic, means it has no

prior upper limit set.

07/07/2023 Ataklti N. 6
 Applications of Stacks

Many application areas use stacks:

• line editing
• BracketChecker (balancer)

07/07/2023 Ataklti N. 7
 4.2. Queue
Like a stack, a queue is also a list.

However, a queue, insertion is done at one end, while deletion is performed at the other end.

Queue is a data structure that has access to its data at the front and rear.

Accessing the elements of queues follows a First In, First Out (FIFO) order.

has two basic operations:

– enqueue - inserting data at the rear of the queue
– dequeue – removing data access at the front of the queue

Implementation of queue
– Array
– Linked list

07/07/2023 Ataklti N. 8
 Operations of Queue

– IsEmpty: return true if queue is empty, return false otherwise

– IsFull: return true if queue is full, return false otherwise

– Enqueue: add an element to the rear of queue

– Dequeue: delete the element at the front of queue

– DisplayQueue: print all the data

07/07/2023 Ataklti N. 9
 Various Queues

• Normal queue (FIFO)

• Circular Queue
• Double-ended Queue (Deque)
• Priority Queue

07/07/2023 Ataklti N. 10
 Normal queue (FIFO)
dequeue enqueue

Front Rear

Operation Content of queue

Enqueue(B) B

Enqueue(C) B, C

Dequeue() C

Enqueue(G) C, G

Enqueue (F) C, G, F

Dequeue() G, F

Enqueue(A) G, F, A

Dequeue() F, A

07/07/2023 Ataklti N. 11
 Simple array Queue and Circular Queues
implementation of enqueue and dequeue operations

• A problem with simple arrays is we run out of space even if the queue
never reaches the size of the array.
• Thus, simulated circular arrays (in which freed spaces are re-used to store
data) can be used to solve this problem.

07/07/2023 Ataklti N. 12
 Circular Queues

• When a new item is inserted at the rear, the pointer to rear moves upwards.

• Similarly, when an item is deleted from the queue the front arrow moves
downwards.
• After a few insert and delete operations the rear might reach the end of the
queue and no more items can be inserted although the items from the front
of the queue have been deleted and there is space in the queue.
• To solve this problem, queues implement wrapping around. Such queues
are called Circular Queues.
• Example: Consider a queue with MAX_SIZE = 4

07/07/2023 Ataklti N. 13
 Example of Circular and Simple array
queue
Simple array Circular array
Content of the array Content of the QUEUE SIZE Message Content of the array Content of the QUEUESIZE Message
Queue queue
Operation

Enqueue(B) B 1 B B 1
B
Enqueue(C) BC 2 B C BC 2
B C
Dequeue() C 1 C C 1
C
Enqueue(G) CG 2 C G CG 2
C G
Enqueue (F) CGF 3 C G F CGF 3
C G F
Dequeue() GF 2 G F GF 2
G F
Enqueue(A) GF 2 Overflow A G F GFA 3
G F
Enqueue(D) GF 2 Overflow A D G F GFAD 4
G F
Enqueue(C) GF 2 Overflow A D G F GFAD 4 Overflow
G F
Dequeue() F 1 A D F FAD 3
F
Enqueue(H) F 1 Overflow A D H F FADH 4
F
Dequeue () Empty 0 A D H ADH 3

Dequeue() Empty 0 Underflow D H DH 2

Dequeue() Empty 0 Underflow H H 1

Dequeue() Empty 0 Underflow Empty 0

Dequeue() Empty 0 Underflow Empty 0 Underflow

07/07/2023 Ataklti N. 14
 Linked list implementation of enqueue
and dequeue operations
• Enqueue- is inserting a node at the end of a linked list
• Dequeue- is deleting the first node in the list
• Queue implemented using linked list will be never full

07/07/2023 Ataklti N. 15
 Application Area of Queue

• There are many applications of Queue

– Printer queues, transport Service queue

07/07/2023 Ataklti N. 16
 4.3 Deque
• It is a double-ended queue.
• Items can be inserted and deleted from either ends.
• More versatile data structure than stack or queue.
• has the following basic operations
EnqueueFront – inserts data at the front of the list
DequeueFront – deletes data at the front of the list
EnqueueRear – inserts data at the end of the list
DequeueRear – deletes data at the end of the list
• Deque is best implemented using doubly linked list

Front Rear
DequeueFront EnqueueFront DequeueRear EnqueueRear

07/07/2023 Ataklti N. 17
 4.4. Priority Queues

More specialized data structure.

Similar to Queue, having front and rear.
Dequeue operation deletes data having highest priority in the list
Items are ordered by key value so that the item with the lowest key (or
highest) is always at the front.

Items are inserted in proper position to maintain the order.

One of the previously used dequeue or enqueue operations has to be
modified

07/07/2023 Ataklti N. 18
 Examples of Priority Queue

Abebe Alemu Aster Belay Kedir Meron Yonas

Male Male Femal Male Male Femal Male
e e

Abebe AlemuDequeue()-
Belay deletes
Kedir Aster
Meron Yonas
Male Male Male Male Femal Male
e

Abebe Alemu Belay

Dequeue()- deletesKedir
Meron Yonas
Male Male Male Male Male

Now the queue has data having equal priority and dequeue operation deletes the front element like in the case of
ordinary queues.
Dequeue()- deletes Abebe
Alemu Belay Kedir Yonas
Male Male Male Male

07/07/2023 Ataklti N. 19
 Demerging Queues

• Demerging queue is the process of creating two or more queues from a

single queue.
• used to give priority for some groups of data
Merging Queues
• Merging queue is the process of creating a priority queue from two or more
queues.
• the ordinary dequeue implementation can be used to delete data in the
newly created priority queue.

07/07/2023 Ataklti N. 20
 »I Thank You

07/07/2023 Ataklti N. 21