Data Structures
Lecture 05: Stacks and Queues
Edirlei Soares de Lima
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()
{
}
public bool IsEmpty()
{
if (top == null)
return true;
else
return false;
}
Stack Applications in Game
Programming
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.
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
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.
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.