Stacks and Queues

Dr. Nguyen Ho
Man Rang

Chapter 6
Stacks and Queues Basic operations of
Stacks

Implementation of
Data Structures and Algorithms Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Dr. Nguyen Ho Man Rang Basic operations of

Queues
Faculty of Computer Science and Engineering Implementation of
University of Technology, VNU-HCM Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.1
 Stacks and Queues
Outcomes
Dr. Nguyen Ho
Man Rang

• L.O.2.1 - Depict the following concepts: (a) array list

and linked list, including single link and double links,
and multiple links; (b) stack; and (c) queue and circular
queue. Basic operations of
Stacks
• L.O.2.2 - Describe storage structures by using Implementation of
Stacks
pseudocode for: (a) array list and linked list, including Linked-list implementation

single link and double links, and multiple links; (b) Array implementation

Applications of
stack; and (c) queue and circular queue. Stack

• L.O.2.3 - List necessary methods supplied for list, Basic operations of

Queues
stack, and queue, and describe them using pseudocode. Implementation of
• L.O.2.4 - Implement list, stack, and queue using Queue
Linked-list implementation

C/C++. Array implementation

Applications of
Queue

6.2
 Stacks and Queues
Outcomes
Dr. Nguyen Ho
Man Rang

• L.O.2.5 - Use list, stack, and queue for problems in

real-life, and choose an appropriate implementation
type (array vs. link).
• L.O.2.6 - Analyze the complexity and develop Basic operations of
Stacks
experiment (program) to evaluate the efficiency of
Implementation of
methods supplied for list, stack, and queue. Stacks
Linked-list implementation
• L.O.8.4 - Develop recursive implementations for Array implementation

methods supplied for the following structures: list, tree, Applications of

Stack
heap, searching, and graphs. Basic operations of
Queues
• L.O.1.2 - Analyze algorithms and use Big-O notation to
Implementation of
characterize the computational complexity of algorithms Queue

composed by using the following control structures: Linked-list implementation

Array implementation

sequence, branching, and iteration (not recursion). Applications of

Queue

6.3
 Stacks and Queues
Contents
Dr. Nguyen Ho
Man Rang

1 Basic operations of Stacks

2 Implementation of Stacks
Linked-list implementation
Array implementation Basic operations of
Stacks

Implementation of
3 Applications of Stack Stacks
Linked-list implementation
Array implementation

4 Basic operations of Queues Applications of

Stack

Basic operations of
5 Implementation of Queue Queues
Linked-list implementation Implementation of
Queue
Array implementation Linked-list implementation
Array implementation

Applications of
6 Applications of Queue Queue

6.4
 Stacks and Queues

Dr. Nguyen Ho
Man Rang

Basic operations of Basic operations of

Stacks

Implementation of
Stacks

Stacks Linked-list implementation

Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.5
 Stacks and Queues
Linear List Concepts
Dr. Nguyen Ho
Man Rang
General list:

• No restrictions on which operation can be

used on the list.
• No restrictions on where data can be Basic operations of
Stacks

inserted/deleted. Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Restricted list: Stack

Basic operations of
Queues
• Only some operations can be used on the Implementation of
Queue
list. Linked-list implementation
Array implementation

• Data can be inserted/deleted only at the Applications of

Queue
ends of the list.
6.6
 Stacks and Queues
Linear list concepts
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.7
 Stacks and Queues
Stack
Dr. Nguyen Ho
Definition Man Rang

A stack of elements of type T is a finite, ordered sequence of

elements of T, in which all insertions and deletions are
restricted to one end, called the top.

Basic operations of
Stacks
Stack is a Last In - First Out (LIFO) data structure. Implementation of
LIFO: The last item put on the stack is the first item that Stacks
Linked-list implementation
can be taken off. Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.8
 Stacks and Queues
Basic operations of Stacks
Dr. Nguyen Ho
Man Rang

Basic operations:

• Construct a stack, leaving it empty. Basic operations of

Stacks
• Push an element: put a new element on to Implementation of
Stacks
the top of the stack. Linked-list implementation
Array implementation

• Pop an element: remove the top element Applications of

Stack

from the top of the stack. Basic operations of

Queues

• Top an element: retrieve the top element. Implementation of

Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.9
 Stacks and Queues
Basic operations of Stacks
Dr. Nguyen Ho
Man Rang

Extended operations:

• Determine whether the stack is empty or Basic operations of

Stacks
not. Implementation of
Stacks
• Determine whether the stack is full or Linked-list implementation
Array implementation

not. Applications of
Stack

• Find the size of the stack. Basic operations of

Queues

• Clear the stack to make it empty. Implementation of

Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.10
 Stacks and Queues
Basic operations of Stacks: Push
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Hình: Successful Push operation Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.11
 Stacks and Queues
Basic operations of Stacks: Push
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation
Hình: Unsuccessful Push operation. Stack remains unchanged.
Applications of
Queue

6.12
 Stacks and Queues
Basic operations of Stacks: Pop
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Hình: Successful Pop operation Linked-list implementation
Array implementation

Applications of
Queue

6.13
 Stacks and Queues
Basic operations of Stacks: Pop
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation
Hình: Unsuccessful Pop operation. Stack remains unchanged. Applications of
Queue

6.14
 Stacks and Queues
Basic operations of Stacks: Top
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation

Hình: Successful Top operation. Stack remains unchanged. Array implementation

Applications of
Queue

6.15
 Stacks and Queues
Basic operations of Stacks: Top
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation
Hình: Unsuccessful Top operation. Stack remains unchanged. Applications of
Queue

6.16
 Stacks and Queues

Dr. Nguyen Ho
Man Rang

Implementation of Basic operations of

Stacks

Implementation of
Stacks

Stacks Linked-list implementation

Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.17
 Stacks and Queues
Linked-list implementation
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.18
 Stacks and Queues
Linked-list implementation
Dr. Nguyen Ho
Man Rang

Stack structure

stack
count < integer >
Basic operations of
top < node pointer > Stacks
end stack
Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack node structure Stack

Basic operations of
Queues

node Implementation of
Queue
data < dataType > Linked-list implementation
next < node pointer > Array implementation

end node Applications of

Queue

6.19
 Stacks and Queues
Linked-list implementation in C++
Dr. Nguyen Ho
Man Rang

template <c l a s s ItemType>

s t r u c t Node {
ItemType d a t a ; Basic operations of
Stacks
Node<ItemType> ∗ n e x t ;
Implementation of
}; Stacks
Linked-list implementation
Array implementation

Applications of
Stack
template <c l a s s L i s t _ I t e m T y p e >
Basic operations of
c l a s s Stack { Queues

public : Implementation of
Queue
Stack ( ) ; Linked-list implementation
Array implementation
~Stack ( ) ;
Applications of
Queue

6.20
 Stacks and Queues
Linked-list implementation in C++
Dr. Nguyen Ho
Man Rang

v o i d Push ( L i s t _ I t e m T y p e d a t a I n ) ;
i n t Pop ( L i s t _ I t e m T y p e &dataOut ) ;
i n t GetStackTop ( L i s t _ I t e m T y p e &dataOut ) ;
Basic operations of
void C l e a r ( ) ; Stacks

i n t IsEmpty ( ) ; Implementation of
Stacks
int GetSize ( ) ; Linked-list implementation
Array implementation
Stack <L i s t _ I t e m T y p e >∗ C l o n e ( ) ;
Applications of
void P r i n t 2 C o n s o l e ( ) ; Stack

Basic operations of
Queues
private : Implementation of
Node<L i s t _ I t e m T y p e >∗ t o p ; Queue
Linked-list implementation
i n t count ; Array implementation

}; Applications of
Queue

6.21
 Stacks and Queues
Create an empty Linked Stack
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.22
 Stacks and Queues
Create an empty Linked Stack
Dr. Nguyen Ho
Man Rang

Algorithm createStack(ref stack

<metadata>)
Initializes the metadata of a stack Basic operations of
Stacks
Pre: stack is a metadata structure of a Implementation of
Stacks
stack Linked-list implementation
Array implementation

Post: metadata initialized Applications of

Stack

Basic operations of
stack.count = 0 Queues

Implementation of
stack.top = null Queue
Linked-list implementation

return Array implementation

Applications of
End createStack Queue

6.23
 Stacks and Queues
Create an empty Linked Stack
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

Stack <L i s t _ I t e m T y p e > : : S t a c k ( ) { Basic operations of
t h i s −>t o p = NULL ; Stacks

Implementation of
t h i s −>c o u n t = 0 ; Stacks
} Linked-list implementation
Array implementation

Applications of
template <c l a s s L i s t _ I t e m T y p e > Stack

Basic operations of
Stack <L i s t _ I t e m T y p e >::~ S t a c k ( ) { Queues
t h i s −>C l e a r ( ) ; Implementation of
Queue
} Linked-list implementation
Array implementation

Applications of
Queue

6.24
 Stacks and Queues
Push data into a Linked Stack
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues
1 Allocate memory for the new node and set up data. Implementation of
Queue
2 Update pointers: Linked-list implementation

• Point the new node to the top node (before adding the Array implementation

Applications of
new node). Queue
• Point top to the new node.
3 Update count
6.25
 Stacks and Queues
Push data into a Linked Stack
Dr. Nguyen Ho
Man Rang

Algorithm pushStack(ref stack

<metadata>, val data <dataType>)
Inserts (pushes) one item into the stack Basic operations of
Stacks

Pre: stack is a metadata structure to a Implementation of

Stacks

valid stack Linked-list implementation

Array implementation

data contains value to be pushed into the Applications of

Stack

stack Basic operations of

Queues

Post: data have been pushed in stack Implementation of

Queue
Return true if successful; false if Linked-list implementation
Array implementation

memory overflow Applications of

Queue

6.26
 Stacks and Queues
Push data into a Linked Stack
Dr. Nguyen Ho
Man Rang

if stack full then

success = false
else
Basic operations of
allocate (pNew) Stacks

Implementation of
pNew -> data = data Stacks
Linked-list implementation

pNew -> next = stack.top Array implementation

Applications of
stack.top = pNew Stack

Basic operations of
stack.count = stack.count + 1 Queues

success = true Implementation of

Queue
end Linked-list implementation
Array implementation

return success Applications of

Queue

End pushStack
6.27
 Stacks and Queues
Push data into a Linked Stack
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

v o i d Stack <L i s t _ I t e m T y p e > : : Push Basic operations of
( List_ItemType v a l u e ){ Stacks

Implementation of
Node<L i s t _ I t e m T y p e >∗ pNew = Stacks
new Node<L i s t _ I t e m T y p e > ( ) ; Linked-list implementation
Array implementation

pNew−>d a t a = v a l u e ; Applications of
pNew−>n e x t = t h i s −>t o p ; Stack

Basic operations of
t h i s −>t o p = pNew ; Queues
t h i s −>c o u n t ++; Implementation of
Queue
} Linked-list implementation
Array implementation

Applications of
Queue

6.28
 Stacks and Queues
Push data into a Linked Stack
Dr. Nguyen Ho
Man Rang

• Push is successful when allocation memory for the new

node is successful.
• There is no difference between push data into a stack
Basic operations of
having elements and push data into an empty stack Stacks

(top having NULL value is assigned to pNew->next: Implementation of

Stacks
that’s corresponding to a list having only one element). Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
pNew−>n e x t = t o p Queues

t o p = pNew Implementation of
Queue
count = count + 1 Linked-list implementation
Array implementation

Applications of
Queue

6.29
 Stacks and Queues
Pop Linked Stack
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
1 dltPtr holds the element on the top of the stack. Linked-list implementation
Array implementation

2 top points to the next element. Applications of

Queue
3 Recycle dltPtr. Decrease count by 1.
6.30
 Stacks and Queues
Pop Linked Stack
Dr. Nguyen Ho
Man Rang

Algorithm popStack(ref stack

<metadata>, ref dataOut <dataType>)
Pops the item on the top of the stack and Basic operations of
Stacks

returns it to caller Implementation of

Stacks

Pre: stack is a metadata structure to a Linked-list implementation

Array implementation

valid stack Applications of

Stack

dataOut is to receive the popped data Basic operations of

Queues

Post: data have been returned to caller Implementation of

Queue
Return true if successful; false if stack Linked-list implementation
Array implementation

is empty Applications of
Queue

6.31
 Stacks and Queues
Pop Linked Stack
Dr. Nguyen Ho
Man Rang

if stack empty then

success = false
else
Basic operations of
dltPtr = stack.top Stacks

Implementation of
dataOut = stack.top -> data Stacks
Linked-list implementation

stack.top = stack.top -> next Array implementation

Applications of
stack.count = stack.count - 1 Stack

Basic operations of
recycle(dltPtr) Queues

success = true Implementation of

Queue
end Linked-list implementation
Array implementation

return success Applications of

Queue

End popStack
6.32
 Stacks and Queues
Pop Linked Stack
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

i n t Stack <L i s t _ I t e m T y p e > : : Pop
( L i s t _ I t e m T y p e &dataOut ) { Basic operations of
Stacks
i f ( t h i s −>G e t S i z e ( ) == 0 )
Implementation of
return 0; Stacks

Node<L i s t _ I t e m T y p e >∗ d l t P t r = t h i s −>t o p ; Linked-list implementation

Array implementation

dataOut = d l t P t r −>d a t a ; Applications of

Stack
t h i s −>t o p = d l t P t r −>n e x t ;
Basic operations of
t h i s −>count −−; Queues

delete d l t P t r ; Implementation of
Queue
return 1; Linked-list implementation
Array implementation
}
Applications of
Queue

6.33
 Stacks and Queues
Pop Linked Stack
Dr. Nguyen Ho
Man Rang

• Pop is successful when the stack is not empty.

• There is no difference between pop an element from a
stack having elements and pop the only-one element in
Basic operations of
the stack (dltPtr->next having NULL value is Stacks

assigned to top: that’s corresponding to an empty Implementation of

Stacks
stack). Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
t o p = d l t P t r −>n e x t Queues

recycle dltPtr Implementation of

Queue
count = count − 1 Linked-list implementation
Array implementation

Applications of
Queue

6.34
 Stacks and Queues
Stack Top
Dr. Nguyen Ho
Man Rang

Algorithm stackTop(ref stack

<metadata>, ref dataOut <dataType>)
Retrieves the data from the top of the Basic operations of
Stacks

stack without changing the stack Implementation of

Stacks

Pre: stack is a metadata structure to a Linked-list implementation

Array implementation

valid stack Applications of

Stack

dataOut is to receive top stack data Basic operations of

Queues

Post: data have been returned to caller Implementation of

Queue
Return true if successful; false if stack Linked-list implementation
Array implementation

is empty Applications of
Queue

6.35
 Stacks and Queues
Stack Top
Dr. Nguyen Ho
Man Rang

if stack empty then

success = false Basic operations of
Stacks

else Implementation of
Stacks
dataOut = stack.top -> data Linked-list implementation
Array implementation

success = true Applications of

Stack
end Basic operations of

return success Queues

Implementation of
End stackTop Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.36
 Stacks and Queues
Stack Top
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

i n t Stack <L i s t _ I t e m T y p e > : : GetStackTop
Basic operations of
( L i s t _ I t e m T y p e &dataOut ) { Stacks

Implementation of
Stacks
i f ( t h i s −>G e t S i z e ( ) == 0 ) Linked-list implementation

return 0; Array implementation

Applications of
Stack
dataOut = t h i s −>top−>d a t a ; Basic operations of
Queues

Implementation of
return 1; Queue
Linked-list implementation
} Array implementation

Applications of
Queue

6.37
 Stacks and Queues
Destroy Stack
Dr. Nguyen Ho
Man Rang

Algorithm destroyStack(ref stack

Basic operations of
<metadata>) Stacks

Implementation of
Releases all nodes back to memory Stacks
Linked-list implementation
Array implementation

Pre: stack is a metadata structure to a Applications of

Stack

valid stack Basic operations of

Queues

Post: stack empty and all nodes recycled Implementation of

Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.38
 Stacks and Queues
Destroy Stack
Dr. Nguyen Ho
Man Rang

if stack not empty then

while stack.top not null do
temp = stack.top Basic operations of
Stacks

stack.top = stack.top -> next Implementation of

Stacks

recycle(temp) Linked-list implementation

Array implementation

end Applications of
Stack

end Basic operations of

Queues

stack.count = 0 Implementation of
Queue
return Linked-list implementation
Array implementation

End destroyStack Applications of

Queue

6.39
 Stacks and Queues
Destroy Stack
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

v o i d Stack <L i s t _ I t e m T y p e > : : C l e a r ( ) { Basic operations of
Node<L i s t _ I t e m T y p e >∗ temp ; Stacks

Implementation of
w h i l e ( t h i s −>t o p != NULL) { Stacks
temp = t h i s −>t o p ; Linked-list implementation
Array implementation

t h i s −>t o p = t h i s −>top−>n e x t ; Applications of

d e l e t e temp ; Stack

Basic operations of
} Queues
t h i s −>c o u n t = 0 ; Implementation of
Queue
} Linked-list implementation
Array implementation

Applications of
Queue

6.40
 Stacks and Queues
isEmpty Linked Stack
Dr. Nguyen Ho
Man Rang

Algorithm isEmpty(ref stack

<metadata>)
Determines if the stack is empty
Pre: stack is a metadata structure to a Basic operations of
Stacks

valid stack Implementation of

Stacks

Post: return stack status

Linked-list implementation
Array implementation

Return true if the stack is empty, false Applications of

Stack

otherwise Basic operations of

Queues

if count = 0 then Implementation of

Queue
Return true Linked-list implementation
Array implementation

else Applications of
Queue
Return false
end 6.41
 Stacks and Queues
isEmpty Linked Stack
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

i n t Stack <L i s t _ I t e m T y p e > : : I s E m p t y ( ) { Basic operations of
Stacks
r e t u r n ( c o u n t == 0 ) ; Implementation of
} Stacks
Linked-list implementation
Array implementation

template <c l a s s L i s t _ I t e m T y p e > Applications of

Stack
i n t Stack <L i s t _ I t e m T y p e > : : G e t S i z e ( ) { Basic operations of
return count ; Queues

Implementation of
} Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.42
 Stacks and Queues
isFull Linked Stack
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

i n t Stack <L i s t _ I t e m T y p e > : : I s F u l l ( ) {
Node<L i s t _ I t e m T y p e >∗ pNew = Basic operations of
Stacks
new Node<L i s t _ I t e m T y p e > ( ) ;
Implementation of
Stacks
Linked-list implementation
i f ( pNew != NULL) { Array implementation

delete pNew ; Applications of

Stack
return 0;
Basic operations of
} else { Queues

return 1; Implementation of
Queue
} Linked-list implementation
Array implementation
}
Applications of
Queue

6.43
 Stacks and Queues
Print Stack
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

v o i d Stack <L i s t _ I t e m T y p e > : : P r i n t 2 C o n s o l e ( ) { Basic operations of
Node<L i s t _ I t e m T y p e >∗ p ; Stacks

Implementation of
p = t h i s −>t o p ; Stacks
w h i l e ( p != NULL) { Linked-list implementation
Array implementation

c o u t << p−>d a t a << " ␣ " ; Applications of

p = p−>n e x t ; Stack

Basic operations of
} Queues
c o u t << e n d l ; Implementation of
Queue
} Linked-list implementation
Array implementation

Applications of
Queue

6.44
 Stacks and Queues
Using Stack
Dr. Nguyen Ho
Man Rang

i n t main ( i n t a r g c , char ∗ a r g v [ ] ) {
Stack <i n t > ∗ myStack = new Stack <i n t > ( ) ;
int val ;
Basic operations of
myStack−>Push ( 7 ) ; Stacks

myStack−>Push ( 9 ) ; Implementation of
Stacks
myStack−>Push ( 1 0 ) ; Linked-list implementation
Array implementation
myStack−>Push ( 8 ) ;
Applications of
myStack−>P r i n t 2 C o n s o l e ( ) ; Stack

myStack−>Pop ( v a l ) ; Basic operations of

Queues
myStack−>P r i n t 2 C o n s o l e ( ) ; Implementation of
d e l e t e myStack ; Queue
Linked-list implementation
return 0; Array implementation

} Applications of
Queue

6.45
 Stacks and Queues
Array-based stack implementation
Dr. Nguyen Ho
Man Rang

Implementation of array-based stack is very simple. It uses

top variable to point to the topmost stack’s element in the
array.
Basic operations of
Stacks
1 Initialy top = -1;
Implementation of
2 push operation increases top by one and writes pushed Stacks
Linked-list implementation
element to storage[top]; Array implementation

Applications of
3 pop operation checks that top is not equal to -1 and Stack
decreases top variable by 1; Basic operations of
Queues
4 getTop operation checks that top is not equal to -1 Implementation of
and returns storage[top]; Queue
Linked-list implementation

5 isEmpty returns boolean if top == -1. Array implementation

Applications of
Queue

6.46
 Stacks and Queues
Array-based stack implementation
Dr. Nguyen Ho
Man Rang

#i n c l u d e <s t r i n g >
u s i n g namespace s t d ;

class ArrayStack {
Basic operations of
private : Stacks

i n t top ; Implementation of
Stacks
int capacity ; Linked-list implementation
Array implementation
int ∗ storage ;
Applications of
Stack

public : Basic operations of

Queues
ArrayStack ( int capacity ) { Implementation of
s t o r a g e = new i n t [ c a p a c i t y ] ; Queue
Linked-list implementation
t h i s −>c a p a c i t y = c a p a c i t y ; Array implementation

t o p = −1; Applications of
Queue
}
// . . .
6.47
 Stacks and Queues
Array-based stack implementation
Dr. Nguyen Ho
Man Rang

~ArrayStack () {
delete [ ] storage ;
}
Basic operations of
v o i d push ( i n t v a l u e ) { Stacks

i f ( t o p == c a p a c i t y − 1 ) Implementation of
Stacks
throw s t r i n g ( " S t a c k ␣ i s ␣ o v e r f l o w " ) ; Linked-list implementation
Array implementation
t o p++;
Applications of
s t o r a g e [ top ] = v a l u e ; Stack

} Basic operations of
Queues

Implementation of
v o i d pop ( i n t &dataOut ) { Queue
Linked-list implementation
i f ( t o p == −1) Array implementation

throw s t r i n g ( " S t a c k ␣ i s ␣ empty " ) ; Applications of

Queue
dataOut = s t o r a g e [ t o p ] ;
top −−;
6.48
 Stacks and Queues
Array-based stack implementation
Dr. Nguyen Ho
Man Rang

i n t getTop ( ) {
i f ( t o p == −1)
throw s t r i n g ( " S t a c k ␣ i s ␣ empty " ) ;
Basic operations of
return s t o r a g e [ top ] ; Stacks

} Implementation of
Stacks
Linked-list implementation
Array implementation
bool i s E m p t y ( ) {
Applications of
r e t u r n ( t o p == −1); Stack

} Basic operations of
Queues

Implementation of
bool i s F u l l ( ) { Queue
Linked-list implementation
r e t u r n ( t o p == c a p a c i t y −1); Array implementation

} Applications of
Queue

6.49
 Stacks and Queues
Array-based stack implementation
Dr. Nguyen Ho
Man Rang

int getSize () {
return top + 1 ;
}
Basic operations of
Stacks
void p r i n t 2 C o n s o l e ( ) { Implementation of
i f ( t o p > −1) { Stacks
Linked-list implementation

f o r ( i n t i = t o p ; i >= 0 ; i −−) { Array implementation

c o u t << s t o r a g e [ i ] << " ␣ " ; Applications of

Stack
} Basic operations of
c o u t << e n d l ; Queues

Implementation of
} Queue
} Linked-list implementation
Array implementation

Applications of
}; Queue

6.50
 Stacks and Queues
Using array-based stack
Dr. Nguyen Ho
Man Rang

i n t main ( i n t a r g c , char ∗ a r g v [ ] ) {
A r r a y S t a c k ∗ myStack = new A r r a y S t a c k ( 1 0 ) ;
int val ;
Basic operations of
myStack−>push ( 7 ) ; Stacks

myStack−>push ( 9 ) ; Implementation of
Stacks
myStack−>push ( 1 0 ) ; Linked-list implementation
Array implementation
myStack−>push ( 8 ) ;
Applications of
myStack−>p r i n t 2 C o n s o l e ( ) ; Stack

myStack−>pop ( v a l ) ; Basic operations of

Queues
myStack−>p r i n t 2 C o n s o l e ( ) ; Implementation of
d e l e t e myStack ; Queue
Linked-list implementation
return 0; Array implementation

} Applications of
Queue

6.51
 Stacks and Queues

Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Applications of Stack Implementation of

Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.52
 Stacks and Queues
Applications of Stack
Dr. Nguyen Ho
• Reversing data items Man Rang

• Reverse a list
• Convert Decimal to Binary
• Parsing
Basic operations of
• Brackets Parse Stacks

• Postponement of processing data items Implementation of

Stacks
Linked-list implementation

• Infix to Postfix Transformation Array implementation

Applications of
• Evaluate a Postfix Expression Stack

• Backtracking Basic operations of

Queues

• Goal Seeking Problem Implementation of

Queue
Linked-list implementation

• Knight’s Tour Array implementation

Applications of
• Exiting a Maze Queue

• Eight Queens Problem

6.53
 Stacks and Queues

Dr. Nguyen Ho
Man Rang

Basic operations of Basic operations of

Stacks

Implementation of
Stacks

Queues Linked-list implementation

Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.54
 Stacks and Queues
Queue
Dr. Nguyen Ho
Man Rang
Definition
A queue of elements of type T is a finite sequence of
elements of T, in which data can only be inserted at one end
called the rear, and deleted from the other end called the
front. Basic operations of
Stacks

Implementation of
Stacks
Queue is a First In - First Out (FIFO) data structure. Linked-list implementation
Array implementation
FIFO: The first item stored in the queue is the first item that Applications of
can be taken out. Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.55
 Stacks and Queues
Basic operations of Queues
Dr. Nguyen Ho
Basic operations: Man Rang

• Construct a queue, leaving it empty.

• Enqueue: put a new element in to the rear
of the queue. Basic operations of
Stacks

• Dequeue: remove the first element from Implementation of

Stacks

the front of the queue. Linked-list implementation

Array implementation

• Queue Front: retrieve the front element. Applications of

Stack

Basic operations of
• Queue Rear: retrieve the rear element. Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.56
 Stacks and Queues
Basic operations of Queues: Enqueue
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.57
 Stacks and Queues
Basic operations of Queues: Dequeue
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.58
 Stacks and Queues
Basic operations of Queues: Queue Front
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.59
 Stacks and Queues
Basic operations of Queues: Queue Rear
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.60
 Stacks and Queues

Dr. Nguyen Ho
Man Rang

Implementation of Basic operations of

Stacks

Implementation of
Stacks

Queue Linked-list implementation

Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.61
 Stacks and Queues
Linked-list implementation
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.62
 Stacks and Queues
Linked-list implementation
Dr. Nguyen Ho
Man Rang
Queue structure

queue
count < integer >
front < node pointer > Basic operations of
Stacks
rear < node pointer >
endqueue Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack
Queue node structure
Basic operations of
Queues

Implementation of
node Queue
Linked-list implementation
data < dataType > Array implementation
next < node pointer >
Applications of
end node Queue

6.63
 Stacks and Queues
Linked-list implementation in C++
Dr. Nguyen Ho
Man Rang

template <c l a s s ItemType>

s t r u c t Node {
ItemType d a t a ; Basic operations of
Stacks
Node<ItemType> ∗ n e x t ;
Implementation of
}; Stacks
Linked-list implementation
Array implementation

Applications of
Stack
template <c l a s s L i s t _ I t e m T y p e >
Basic operations of
c l a s s Queue { Queues

public : Implementation of
Queue
Queue ( ) ; Linked-list implementation
Array implementation
~Queue ( ) ;
Applications of
Queue

6.64
 Stacks and Queues
Linked-list implementation in C++
Dr. Nguyen Ho
Man Rang

v o i d Enqueue ( L i s t _ I t e m T y p e d a t a I n ) ;
i n t Dequeue ( L i s t _ I t e m T y p e &dataOut ) ;
i n t GetQueueFront ( L i s t _ I t e m T y p e &dataOut ) ;
Basic operations of
i n t GetQueueRear ( L i s t _ I t e m T y p e &dataOut ) ; Stacks
void C l e a r ( ) ; Implementation of
Stacks
i n t IsEmpty ( ) ; Linked-list implementation
Array implementation
int GetSize ( ) ;
Applications of
void P r i n t 2 C o n s o l e ( ) ; Stack

Basic operations of
Queues
private : Implementation of
Node<L i s t _ I t e m T y p e > ∗ f r o n t , ∗ r e a r ; Queue
Linked-list implementation
i n t count ; Array implementation

}; Applications of
Queue

6.65
 Stacks and Queues
Create Queue
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.66
 Stacks and Queues
Create Queue
Dr. Nguyen Ho
Man Rang

Algorithm createQueue(ref queue

<metadata>)
Initializes the metadata of a queue
Basic operations of
Pre: queue is a metadata structure of a Stacks

Implementation of
queue Stacks
Linked-list implementation

Post: metadata initialized Array implementation

Applications of
Stack

queue.count= 0 Basic operations of

Queues

queue.front = null Implementation of

Queue

queue.rear = null Linked-list implementation

Array implementation

return Applications of
Queue

End createQueue
6.67
 Stacks and Queues
Create Queue
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

Queue<L i s t _ I t e m T y p e > : : Queue ( ) {
Basic operations of
t h i s −>c o u n t = 0 ; Stacks
t h i s −>f r o n t = NULL ; Implementation of
Stacks
t h i s −>r e a r = NULL ; Linked-list implementation

} Array implementation

Applications of
Stack
template <c l a s s L i s t _ I t e m T y p e > Basic operations of
Queues
Queue<L i s t _ I t e m T y p e >::~ Queue ( ) {
Implementation of
t h i s −>C l e a r ( ) ; Queue
Linked-list implementation
} Array implementation

Applications of
Queue

6.68
 Stacks and Queues
Enqueue: Insert into an empty queue
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Hình: Insert into an empty queue Implementation of

Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.69
 Stacks and Queues
Enqueue: Insert into a queue with data
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Hình: Insert into a queue with data Linked-list implementation
Array implementation

Applications of
Queue

6.70
 Stacks and Queues
Enqueue
Dr. Nguyen Ho
Man Rang

Algorithm enqueue(ref queue

<metadata>, val data <dataType>)
Inserts one item at the rear of the queue
Basic operations of
Stacks

Pre: queue is a metadata structure of a Implementation of

Stacks
Linked-list implementation

valid queue Array implementation

Applications of
data contains data to be inserted into Stack

queue Basic operations of

Queues

Implementation of
Queue
Post: data have been inserted in queue Linked-list implementation
Array implementation

Return true if successful, false if Applications of

Queue

memory overflow
6.71
 Stacks and Queues
Enqueue
Dr. Nguyen Ho
Man Rang

if queue full then

return false
end
allocate (newPtr)
newPtr -> data = data Basic operations of
Stacks
newPtr -> next = null Implementation of
if queue.count = 0 then Stacks
Linked-list implementation

// Insert into an empty queue Array implementation

queue.front = newPtr Applications of

Stack
else Basic operations of
// Insert into a queue with data Queues

queue.rear -> next = newPtr Implementation of

Queue
end Linked-list implementation
Array implementation

queue.rear = newPtr Applications of

queue.count = queue.count + 1 Queue

return true
End enqueue 6.72
 Stacks and Queues
Enqueue
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

v o i d Queue<L i s t _ I t e m T y p e > : : Enqueue
( List_ItemType v a l u e ){
Node<L i s t _ I t e m T y p e >∗ newPtr = new Basic operations of
Stacks
Node<L i s t _ I t e m T y p e > ( ) ; Implementation of
newPtr−>d a t a = v a l u e ; Stacks
Linked-list implementation

newPtr−>n e x t = NULL ; Array implementation

i f ( t h i s −>c o u n t == 0 ) Applications of
Stack
t h i s −>f r o n t = newPtr ; Basic operations of
else Queues

t h i s −>r e a r −>n e x t = newPtr ; Implementation of

Queue
t h i s −>r e a r = newPtr ; Linked-list implementation
Array implementation

t h i s −>c o u n t ++; Applications of

} Queue

6.73
 Stacks and Queues
Dequeue: Delete data in a queue with only one item
Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues
Hình: Delete data in a queue with only one item Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.74
 Stacks and Queues
Dequeue: Delete data in a queue with more than one
item Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Implementation of
Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Hình: Delete data in a queue with more than one item Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.75
 Stacks and Queues
Dequeue
Dr. Nguyen Ho
Man Rang

Algorithm dequeue(ref queue

<metadata>, ref dataOut <dataType>)
Deletes one item at the front of the queue
and returns its data to caller Basic operations of
Stacks

Implementation of
Stacks
Pre: queue is a metadata structure of a Linked-list implementation
Array implementation

valid queue Applications of

Stack

dataOut is to receive dequeued data Basic operations of

Queues

Implementation of

Post: front data have been returned to Queue

Linked-list implementation
Array implementation

caller Applications of
Queue
Return true if successful, false if
memory overflow 6.76
 Stacks and Queues
Dequeue
Dr. Nguyen Ho
Man Rang

if queue empty then

return false
end
dataOut = queue.front -> data Basic operations of
Stacks
dltPtr = queue.front
Implementation of
if queue.count = 1 then Stacks
Linked-list implementation
// Delete data in a queue with only one item Array implementation

queue.rear = NULL Applications of

Stack
end Basic operations of
queue.front = queue.front -> next Queues

queue.count = queue.count - 1 Implementation of

Queue
recycle (dltPtr) Linked-list implementation
Array implementation

return true Applications of

End dequeue Queue

6.77
 Stacks and Queues
Dequeue
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

i n t Queue<L i s t _ I t e m T y p e > : : Dequeue (
L i s t _ I t e m T y p e &dataOut ) {
i f ( c o u n t == 0 ) Basic operations of
Stacks
return 0; Implementation of
dataOut = f r o n t −>d a t a ; Stacks
Linked-list implementation

Node<L i s t _ I t e m T y p e >∗ d l t P t r= t h i s −>f r o n t ; Array implementation

i f ( c o u n t == 1 ) Applications of
Stack
t h i s −>r e a r = NULL ; Basic operations of
t h i s −>f r o n t = t h i s −>f r o n t −>n e x t ; Queues

t h i s −>count −−; Implementation of

Queue
delete d l t P t r ; Linked-list implementation
Array implementation

return 1; Applications of
} Queue

6.78
 Stacks and Queues
Queue Front
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

Basic operations of
i n t Queue<L i s t _ I t e m T y p e > : : GetQueueFront Stacks

( L i s t _ I t e m T y p e &dataOut ) { Implementation of
Stacks
i f ( c o u n t == 0 ) Linked-list implementation
Array implementation
return 0;
Applications of
dataOut = t h i s −>f r o n t −>d a t a ; Stack

return 1; Basic operations of

Queues
} Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.79
 Stacks and Queues
Queue Rear
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

Basic operations of
i n t Queue<L i s t _ I t e m T y p e > : : GetQueueRear Stacks

( L i s t _ I t e m T y p e &dataOut ) { Implementation of
Stacks
i f ( c o u n t == 0 ) Linked-list implementation
Array implementation
return 0;
Applications of
dataOut = t h i s −>r e a r −>d a t a ; Stack

return 1; Basic operations of

Queues
} Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.80
 Stacks and Queues
Destroy Queue
Dr. Nguyen Ho
Man Rang

Algorithm destroyQueue(ref queue

<metadata>)
Basic operations of
Deletes all data from a queue Stacks

Implementation of
Stacks

Pre: queue is a metadata structure of a Linked-list implementation

Array implementation

valid queue Applications of

Stack

Basic operations of
Queues
Post: queue empty and all nodes recycled Implementation of
Queue
Linked-list implementation

Return nothing
Array implementation

Applications of
Queue

6.81
 Stacks and Queues
Destroy Queue
Dr. Nguyen Ho
Man Rang

if queue not empty then

while queue.front not null do
temp = queue.front
Basic operations of
queue.front = queue.front->next Stacks

recycle(temp) Implementation of
Stacks
Linked-list implementation
end Array implementation

Applications of
end Stack

queue.front = NULL Basic operations of

Queues

queue.rear = NULL Implementation of

Queue

queue.count = 0 Linked-list implementation

Array implementation

return Applications of
Queue

End destroyQueue
6.82
 Stacks and Queues
Destroy Queue
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

v o i d Queue<L i s t _ I t e m T y p e > : : C l e a r ( ) {
Node<L i s t _ I t e m T y p e >∗ temp ; Basic operations of
Stacks
w h i l e ( t h i s −>f r o n t != NULL) {
Implementation of
temp = t h i s −>f r o n t ; Stacks

t h i s −>f r o n t= t h i s −>f r o n t −>n e x t ; Linked-list implementation

Array implementation

d e l e t e temp ; Applications of
Stack
}
Basic operations of
t h i s −>f r o n t = NULL ; Queues

t h i s −>r e a r = NULL ; Implementation of

Queue
t h i s −>c o u n t = 0 ; Linked-list implementation
Array implementation
}
Applications of
Queue

6.83
 Stacks and Queues
Queue Empty
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

i n t Queue<L i s t _ I t e m T y p e > : : I s E m p t y ( ) { Basic operations of
Stacks
r e t u r n ( t h i s −>c o u n t == 0 ) ; Implementation of
} Stacks
Linked-list implementation
Array implementation

template <c l a s s L i s t _ I t e m T y p e > Applications of

Stack
i n t Queue<L i s t _ I t e m T y p e > : : G e t S i z e ( ) { Basic operations of
r e t u r n t h i s −>c o u n t ; Queues

Implementation of
} Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.84
 Stacks and Queues
Print Queue
Dr. Nguyen Ho
Man Rang

template <c l a s s L i s t _ I t e m T y p e >

v o i d Queue<L i s t _ I t e m T y p e > : : P r i n t 2 C o n s o l e ( ) {
Basic operations of
Node<L i s t _ I t e m T y p e >∗ p ; Stacks
p = t h i s −>f r o n t ; Implementation of
Stacks
c o u t << " F r o n t : ␣ " ; Linked-list implementation

w h i l e ( p != NULL) { Array implementation

Applications of
c o u t << p−>d a t a << " ␣ " ; Stack
p = p−>n e x t ; Basic operations of
Queues
}
Implementation of
c o u t << e n d l ; Queue
Linked-list implementation
} Array implementation

Applications of
Queue

6.85
 Stacks and Queues
Using Queue
Dr. Nguyen Ho
Man Rang

i n t main ( i n t a r g c , char ∗ a r g v [ ] ) {
Queue<i n t > ∗myQueue = new Queue<i n t > ( ) ;
int val ;
Basic operations of
myQueue−>Enqueue ( 7 ) ; Stacks

myQueue−>Enqueue ( 9 ) ; Implementation of
Stacks
myQueue−>Enqueue ( 1 0 ) ; Linked-list implementation
Array implementation
myQueue−>Enqueue ( 8 ) ;
Applications of
myQueue−>P r i n t 2 C o n s o l e ( ) ; Stack

myQueue−>Dequeue ( v a l ) ; Basic operations of

Queues
myQueue−>P r i n t 2 C o n s o l e ( ) ; Implementation of
d e l e t e myQueue ; Queue
Linked-list implementation
return 1; Array implementation

} Applications of
Queue

6.86
 Stacks and Queues
Array-based queue implementation
Dr. Nguyen Ho
Man Rang

#i n c l u d e <s t r i n g >
u s i n g namespace s t d ;
c l a s s ArrayQueue {
private :
Basic operations of
int capacity ; Stacks

int front ; Implementation of

Stacks
int rear ; Linked-list implementation
Array implementation
int ∗ storage ;
Applications of
Stack

public : Basic operations of

Queues
ArrayQueue ( i n t c a p a c i t y ) { Implementation of
s t o r a g e = new i n t [ c a p a c i t y ] ; Queue
Linked-list implementation
t h i s −>c a p a c i t y = c a p a c i t y ; Array implementation

f r o n t = −1; Applications of
Queue
r e a r = −1;
}
6.87
 Stacks and Queues
Array-based queue implementation
Dr. Nguyen Ho
Man Rang

~ArrayQueue ( ) {
delete [ ] storage ;
}
Basic operations of
v o i d enQueue ( i n t v a l u e ) { Stacks

i f ( i s F u l l ( ) ) throw s t r i n g ( " Queue ␣ i s ␣ f u l l " Implementation

); of
Stacks
i f ( f r o n t == −1) f r o n t = 0 ; Linked-list implementation
Array implementation
r e a r ++;
Applications of
storage [ rear % capacity ] = value ; Stack

} Basic operations of
Queues

Implementation of
v o i d deQueue ( i n t &v a l u e O u t ) { Queue
Linked-list implementation
i f ( isEmpty ( ) ) Array implementation

throw s t r i n g ( " Queue ␣ i s ␣ empty " ) ; Applications of

Queue
valueOut = storage [ f r o n t % c a p a c i t y ] ;
f r o n t ++;
6.88
 Stacks and Queues
Array-based queue implementation
Dr. Nguyen Ho
Man Rang

int getFront () {
i f ( isEmpty ( ) )
Basic operations of
throw s t r i n g ( " Queue ␣ i s ␣ empty " ) ; Stacks
return storage [ f r o n t % c a p a c i t y ] ; Implementation of
Stacks
} Linked-list implementation
Array implementation

Applications of
int getRear () { Stack
i f ( isEmpty ( ) ) Basic operations of
Queues
throw s t r i n g ( " Queue ␣ i s ␣ empty " ) ;
Implementation of
return storage [ r e a r % c a p a c i t y ] ; Queue
Linked-list implementation
} Array implementation

Applications of
Queue

6.89
 Stacks and Queues
Array-based queue implementation
Dr. Nguyen Ho
Man Rang

bool i s E m p t y ( ) {
r e t u r n ( f r o n t > r e a r | | f r o n t == −1);
}
Basic operations of
Stacks
bool i s F u l l ( ) { Implementation of
r e t u r n ( r e a r − f r o n t + 1 == Stacks
Linked-list implementation

capacity ); Array implementation

} Applications of
Stack

Basic operations of
int getSize () { Queues

return r e a r − f r o n t + 1; Implementation of
Queue
} Linked-list implementation
Array implementation

Applications of
}; Queue

6.90
 Stacks and Queues
Using Array-based queue
Dr. Nguyen Ho
Man Rang

i n t main ( i n t a r g c , char ∗ a r g v [ ] ) {
ArrayQueue ∗myQueue = new ArrayQueue ( 1 0 ) ;
Basic operations of
int val ; Stacks
myQueue−>enQueue ( 7 ) ; Implementation of
Stacks
myQueue−>enQueue ( 9 ) ; Linked-list implementation

myQueue−>enQueue ( 1 0 ) ; Array implementation

Applications of
myQueue−>enQueue ( 8 ) ; Stack
myQueue−>deQueue ( v a l ) ; Basic operations of
Queues
d e l e t e myQueue ;
Implementation of
return 1; Queue
Linked-list implementation
} Array implementation

Applications of
Queue

6.91
 Stacks and Queues

Dr. Nguyen Ho
Man Rang

Basic operations of
Stacks

Applications of Queue Implementation of

Stacks
Linked-list implementation
Array implementation

Applications of
Stack

Basic operations of
Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.92
 Stacks and Queues
Applications of Queue
Dr. Nguyen Ho
Man Rang

• Polynomial Arithmetic Basic operations of

• Categorizing Data Stacks

Implementation of
Stacks
• Evaluate a Prefix Expression Linked-list implementation
Array implementation

• Radix Sort Applications of

Stack

• Queue Simulation Basic operations of

Queues

Implementation of
Queue
Linked-list implementation
Array implementation

Applications of
Queue

6.93