Introduction to Stacks, Queues and Linked Lists
In computer Science, we say:
Don't
Reinventing the wheel !
However, in this class, we will "understand the wheel", "how to use the wheel", "how to build a wheel"
Review: Array
Before we start, which Zombie TV show do you like best?
If in a zombie apocalypse, what shall we store?
In computer science, we have two basic data structures to
store items:
Stack and Queues
What is a Stack
A stack is a data structure of ordered items such that items can be inserted and removed only at one end.
LIFO (Last In First Out)
Basic operation of stack:
push - place an item on the stack
pop - Look at the item on top of the stack and remove it
peek - Look at the item on top of the stack, but do not remove
it
isEmpty - Check if the stack is empty
size - check the size (how many items) of stack
Scroll of town portal
What is a Queue
A data structure of ordered items such that items can be inserted only at one end and removed at the other end.
FIFO (First In First Out)
Basic operation of Queue:
Enqueue - Add an item to the queue
Dequeue - Remove an item from the queue
Scroll of town portal
"How to build a wheel"
Implementing a Stack
Implementing a stack using an array is fairly easy:
The bottom of the stack is at data[0]
The top of the stack is at data[numItems-1]
push onto the stack at data[numItems]
pop off of the stack at data[numItems-1]
Implementing a Queue
Implementing a queue using an array is kind of complicated:
Enqueue at data[rear+1]
Dequeue at data[front]
The rear variable always contains the index of the last item in
the queue.
The front variable always contains the index of the first item
in the queue.
When we reach the end of the array, wrap around to the front
again.
What is a Linked List
A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node.
Implementing a queue using a linked list is very
easy:
Front of the queue is stored as the head node of the linked
list, rear of the queue is stored as the tail node.
Enqueue by adding to the end of the list
Dequeue by removing from the front of the list.