Data Structures - Stacks and Queues

Data Structures

Lecture 05: 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;

data

.

..

}

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

Stack – Pop

public StackNode<T> Pop(){

if (top == null)

return null;

else{

StackNode<T> node = top;

top = top.Next;

return node;

}

top

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

}

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

back

data

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

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.