Data Structures  
Lecture 04: Stacks and Queues  
Edirlei Soares de Lima  
<edirlei.lima@universidadeeuropeia.pt>  
Stacks  
A stack is a data structure that stores a collection of elements  
and follows a specific order to add and remove elements to  
the structure: LIFO (Last In First Out).  
Stacks  
Basic operations:  
Push: adds an element to the stack.  
Pop: removes an element from the stack.  
The element are popped in the reversed order in which they were pushed.  
Peek: returns top element of stack.  
Without removing the element.  
IsEmpty: returns true if stack is empty.  
Stack Structure  
top  
public class StackNode<T>  
{
private StackNode<T> next;  
private T data;  
next  
data  
data  
data  
.
..  
}
next  
next  
public class Stack<T>  
{
private StackNode<T> top;  
.
..  
}
Stack Generic Class  
public class StackNode<T>  
{
public class Stack<T>  
{
private StackNode<T> next;  
private T data;  
private StackNode<T> top;  
public Stack()  
public StackNode(T t)  
{
{
top = null;  
next = null;  
data = t;  
}
}
}
public StackNode<T> Next{  
get { return next; }  
set { next = value; }  
}
public T Data{  
get { return data; }  
set { data = value; }  
}
}
Stack Push  
public void Push(T data)  
{
StackNode<T> node = new StackNode<T>(data);  
node.Next = top;  
top = node;  
}
top  
next  
new  
next  
data  
next  
data  
Stack Pop  
public StackNode<T> Pop(){  
if (top == null)  
return null;  
else{  
StackNode<T> node = top;  
top = top.Next;  
return node;  
}
}
next  
next  
next  
data  
top  
data  
data  
Stack Peek and IsEmpty  
public StackNode<T> Peek()  
{
return top;  
}
public bool IsEmpty()  
{
if (top == null)  
return true;  
else  
return false;  
}
Stack Applications in Game  
Programming  
Menu Systems:  
Every time the user selects a sub-menu, the new menu is created and pushed  
onto the stack. When the user presses Escape, the current menu is popped  
out of the stack.  
The current menu is always on the top of the stack.  
Stack-Based Finite State Machine (FSM):  
Unlike normal FSMs, a stack-based FSM uses a stack to control states.  
The top of the stack contains the active state.  
Transitions are handled by pushing or popping states from the stack.  
Other programming tasks:  
Expression evaluation, backtracking, reverse data, memory management (heap), graph  
search, etc...  
Assignment Stack  
1
) Implement a history system to allow the player to undo his  
actions by pressing a key.  
Every time the player presses an arrow key (up, down, left, and right),  
the character must move one unit to the corresponding direction.  
Use the Input.GetKeyDown function to move only in the first frame when the  
player starts pressing the key.  
When the player presses the undo key (e.g. spacebar), the player  
character must undo the last movement.  
If the player keeps pressing again the undo key, the player character must undo all  
his movements in the correct order.  
You must use a stack structure to store the player positions.  
The last position is always on the top of the stack.  
Queue  
A queue is a data structure that stores a collection of  
elements and follows a specific order to add and remove  
elements to the structure: FIFO (First In First Out).  
Queue  
Basic operations:  
Enqueue: adds an element to the queue.  
Dequeue: removes an element from the queue.  
The elements are popped in the same order in which they are pushed.  
Front: get the front element from queue.  
Back: get the last element from queue.  
IsEmpty: returns true if queue is empty.  
Queue Structure  
public class QueueNode<T>  
{
private QueueNode<T> next;  
private T data;  
back  
data  
data  
data  
next  
.
..  
}
next  
next  
public class Queue<T>  
{
private QueueNode<T> front;  
private QueueNode<T> back;  
front  
.
..  
}
Queue Generic Class  
public class QueueNode<T>  
{
public class Queue<T>  
{
private QueueNode<T> next;  
private T data;  
private QueueNode<T> front;  
private QueueNode<T> back;  
public QueueNode(T t){  
public Queue()  
next = null;  
{
data = t;  
}
front = null;  
back = null;  
}
}
public QueueNode<T> Next{  
get { return next; }  
set { next = value; }  
}
public T Data{  
get { return data; }  
set { data = value; }  
}
}
Queue Enqueue  
public void Enqueue(T data){  
QueueNode<T> node = new QueueNode<T>(data);  
if (back == null){  
back = node;  
front = node;  
}
else{  
back.Next = node;  
back = node;  
}
}
new  
next  
front  
back  
data  
data  
next  
data  
next  
next  
Queue Dequeue  
public QueueNode<T> Dequeue(){  
if (front == null)  
return null;  
else{  
QueueNode<T> node = front;  
front = front.Next;  
if (front == null)  
back = null;  
return node;  
}
}
front  
back  
data  
data  
next  
data  
next  
next  
Queue Front, Back, and IsEmpty  
public QueueNode<T> Front()  
{
return front;  
}
public QueueNode<T> Back()  
{
return back;  
}
public bool IsEmpty()  
{
if (front == null)  
return true;  
else  
return false;  
}
Queue Applications in Game  
Programming  
Command Queues:  
Every time the player selects a command for a unit/character, add it to a queue.  
The first command added to the queue will be executed first.  
The order of the commands will always follow the order in which they were  
added to queue.  
Production Systems:  
Players can use a factory/machine to build items/objects. The production  
process can take a certain amount of time.  
Building requests can be added to a queue to allow the player to schedule the  
production of items/objects.  
Other programming tasks:  
Job scheduling, requests queues, io buffers, graph search, etc ...  
Assignment Queue  
1
) Implement a command system to allow the player to send  
commands to a character. The character must follow the  
player commands in the order they were given.  
The commands consist of positions where the character must go.  
The player can select a position by clicking on any position of the  
screen.  
Use function Camera.main.ScreenToWorldPoint to get world coordinate where the  
is clicking.  
The character must move gradually to the target position.  
The player can click on new position while the character is still going to  
previous positions.  
The character must go to all selected position in the correct order.  
You must use a queue structure to store the selected positions.  
The next target position is always on the front of the queue.  
Further Reading  
Penton, R. (2002). Data Structures for Game Programmers.  
Muska & Lipman/Premier-Trade. ISBN: 978-1931841948  
Chapter 7: Stacks and Queues  
Sherrod, A. (2007). Data Structures and Algorithms for  
Game Developers. Charles River Media. ISBN: 978-  
1
584504955  
Chapter 6: Stacks and Queues