TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Chapter 2. Basic data structures

Michel Toulouse & Nguyễn Khánh Phương

Computer Science department
School of Information and Communication technology
E-mail: phuongnk@[Link]
Contents
2.0 Pointers
2.1 Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

2
 Dereferencing a pointer
• Pointers have a type (int *ptr), the type is used when dereferencing the
pointer
• Dereferencing a pointer means read the contain of the address stored
in the pointer
• Example:
– int a = 8; int b; int *ptr;
– ptr = &a; // store the address of ‘a’ in the pointer ptr
– b = *ptr; //store in b the value of the address stored in ptr. This is
dereferencing the pointer ptr

• The type of the pointer ‘ptr’ indicates how many bytes have to be read
starting at the address in ptr.
– Here the type of the ptr is int, which means 4 bytes must be read when
dereferencing ptr

3
 Variables and types
• Programs have variables. In a
This program (basic1-1.c) assigned the
number 16 to the 4 memory cells starting compiled/linked/loaded code,
at addr represented by “myvar” variable names are transformed
into memory addresses. CPU
only know memory addresses
#include <stdio.h> • Variables have types. Variables
#include <stdlib.h> are place holder, storage. The
type of a variable indicates the
int main(){ amount of storage used by the
int myvar; variable.
• Examples:
myvar = 16;
– int 4 bytes 5
– double 8 bytes 6.75
printf("addr myvar %8u, and value stored at
– char 1 bytes ‘b’
the addr of myvar %d\n",&myvar,myvar);
}

4
 Pointers

• Pointer is a variable that store the address of another

variable
• Pointer syntax in C:
– Data_type *pointer_name; or
– Data_type* pointer_name;
• Examples of pointers declaration:
int *p; char *p;
• The amount of storage used by a pointer is always the
same, it is equal to the size of the addresses in a
particular computer architecture. For example 4 or 8
bytes

5
 Pointer initialization

• Pointer initialization is the process of assigning

address of a variable to pointer variable.
• Pointer variable contains the address of a
variable of same data type
• In C, the address operator & is used to determine
the address of a variable, the & returns the
address of the variable
• Examples:
– int a = 10;
– int *ptr;
– ptr = &a;

6
 Computer memory
• Computer memory is made of a
long sequence of memory cells,
each 8 bits (one byte) long
• Associated with each memory
cell is 8address
• Variable names in a program are
addresses, i.e. the cell where
the data is stored
– int myvar;
• The type of a variable “int”
defines the number of
consecutive memory cells used
to store the data
– int means 4 consecutive cells are
reserved to store the data of myvar

7
 Example of program (pointer2.c)
#include <stdio.h>
int main() {
int *ptr, q; //declarations
q = 50;
ptr = &q; //initialization of pointer ptr
printf(“print addr of pointer ptr %8u\n\n",&ptr);
printf(“print addr of q %8u\n\n",&q);
printf(“print addr of q stored in ptr %8u\n\n",ptr);
printf(“print the value of the addr stored in ptr%d\n",*ptr); //dereferencing ptr
}

8
 Rules of pointers
• A pointer variable can be assigned the address of
another variable
– int v; int * ptr; ptr = &v;
• A pointer variable can be assigned the address of
another pointer variable
– int *ptr1, **ptr2; ptr2 = &ptr1; (pointer3.c)
• A pointer variable can be initialized with NULL or 0 value
– int *ptr = NULL; int *ptr1 = 0;

9
 ARRAYS

• An array is a sequence of consecutive memory cells

(bytes)
• The number of memory cells is
– size of array * sizeof(type)

10
Declaring an one-dimensional array
To declare an array, we need to specify its data type, the array’s identifier and the
size:

type arrayName [arraySize];

Example:
int A[5];
declare an array A having 5 elements of integer type (4 bytes for each element)

int *A[5];
declare an array of pointers to integers. Each entry in the array is a pointer.

The declaration of array returns an address, the address of the first byte of the array
• int *ptr, A[5];
• ptr = A;

11
Initializing a one-dimensional array
• We can initialize fixed-length array elements when we
define an array.
• If we initialize fewer values than the length of the array, C
assigns zeroes to the remaining elements.

12
Accessing Elements
To access an array’s element, an integer is provided which is
the index of the element to access.

Note, in C, the index of arrays start at 0

The index can be specify using a constant:

scores[0];

The index can also by specified using a variable:

for(i = 0; i < 9; i++)
scoresSum += scores[i];

13
Example
In a C program, the index returns the address of an element in an 1D array:
#include <stdio.h>
int main()
{ int A[ ] = {5, 10, 12, 15, 4};
int rows=5;
/* print the address of 1D array using pointer */
int *ptr = A;
printf("Address Contents\n");
for (int i=0; i < rows; i++)
printf("%8u %5d\n", ptr+i, *(ptr+i));
}
(sizeof(int)=4)
ptr+i : address of element A[i]
*(ptr+i) : content of element A[i]

Memory Location(A[i]) = start_address + W*i

5 10 12 15 4

start_address=6487536
Arrays and pointers

• Arrays can be declared dynamically in C using the

malloc() instruction
• Example
– int *ptr;
– ptr = (int *) malloc(6 * sizeof (int));
• The malloc instruction allocate consecutive memory for 6
integers and returns the address of the first byte of the
sequence of allocated bytes
• Example
– for (i=0; i < 6; i++)
ptr[i] = i;

15
Declaring two-dimensional array
• How to declare:
<element-type> <arrayName> [size1][size2];
Example: double a[3][4];
may be shown as a table

• Using the two-dimensional array initializer

Example: int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
• Access to element of array: a[2] [1]; a[0][0] = 1 a[0][1]=2 a[0][2]=3 a[0][3]=4

a[1][0] = 5 a[1][1]=6 a[1][2]=7 a[1][3]=8

a[2][0] = 9 a[2][1]=10 a[2][2]=11 a[2][3]=12

Representation of Arrays
• In the computer memory there is no such thing as a multidimensional array, an array
is just a sequence of contiguous bytes
• If you declare a two-dimensional array, the programming language must decide how
the dimensions of the array are transformed into a sequence of bytes.
• There are two policies: row major order or column major order.
Row-Major Mapping (e.g. Pascal, C/C++)
 In a 2-dimensional array, with row- major policy, the rows of the array are sequenced, arranged
sequentially row by row. Thus, elements of the first row occupies the first sequence of bytes
reserved for the array, elements of the second row occupies the next sequence of memory and so
on.
Elements of Elements of Elements of Elements of
…. ……..
Row 0 Row 1 Row 2 Row i

 Example: int a[4][3]

in ascending direction of memory address

a[0][0] a[0][1] a[0][2]

row 0 row 1 row 2 row 3

Column-Major Mapping (e.g. Matlab, Fortran)
 In a 2-dimensional array, with column- major policy, the columns are
arranged sequentially one after the other one. The elements of the first
column occupies the first sequence of bytes reserved for the array, elements
of the second column occupies the next sequence of memory and so on.
Elements of Elements of Elements of Elements of
…. ……..
column 0 column 1 column 2 column i

 Example 3 x 4 array:
abcd
efgh
i jkl
Convert into 1D array Y by collecting elements by columns.
 Within a column elements are collected from top to bottom.
 Columns are collected from left to right.

Thus, we get Y[ ] =
{a, e, i, b, f, j, c, g, k, d, h, l}
Row- and Column-Major Mappings
2D array: r rows, c columns
Example: int a[3][6]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
a[0][0]=0 a[0][1]=1 a[0][2]=2 a[0][3]=3 a[0][4]=4 a[0][5]=5
a[1][0]=6 a[1][1]=7 a[1][2]=8 a[1][3]=9 a[1][4]=10 a[1][5]=11
a[2][0]=12 a[2][1]=13 a[2][2]=14 a[2][3]=15 a[2][4]=16 a[2][5]=17

Memory: row-major order

c elements of c elements of c elements of c Elements of
…. ……..
Row 0 Row 1 Row 2 Row r

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

6 elements of row 0 6 elements of row 1 6 elements of row 2

Memory: column-major order

r Elements of r Elements of r Elements of r Elements of
…. ……..
column 0 column 1 column 2 column i

0 6 12 1 7 13 2 8 14 3 9 15 4 10 16 5 11 17

3 elements of col 0 3 elements of col 5

Locating Element x[i][j]: row-major order
 Assume x:
 has r rows and c columns (thus, each row has c elements)

c elements of c elements of c elements of c Elements of

…. ……..
Row 0 Row 1 Row 2 Row r-1

 Locating element x[i][j]:

 i rows to the left of row 0  so i*c elements to the left of x[i][0]
 x[i][j] is mapped to position: i*c + j of the 1D array
 The location of element x[i][j]:

Location(x[i][j]) =start_address + W * (i*c + j)

Where
• start_address: the address of the first element (x[0][0]) in the array
• W: is the size of each element
• c: number of columns in the array
Locating Element x[i][j]: row-major order
2D array: 3 rows, 6 columns
Example: int a[3][6]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
a[0][0]=0 a[0][1]=1 a[0][2]=2 a[0][3]=3 a[0][4]=4 a[0][5]=5
a[1][0]=6 a[1][1]=7 a[1][2]=8 a[1][3]=9 a[1][4]=10 a[1][5]=11
a[2][0]=12 a[2][1]=13 a[2][2]=14 a[2][3]=15 a[2][4]=16 a[2][5]=17

 Locating element x[i][j]:

 x[i][j] is mapped to position: i*c + j of the 1D array
 The location of element x[i][j]:

Location(x[i][j]) =start_address + W * (i*c + j)

• Locating a[1][3]: 4 *(1*6+3) = 36

Locating Element x[i][j]: column-major order
r Elements r Elements r Elements r Elements of
 Assume x: ….. of column 0 of column 1 of column 2 …. columns i …….

 has r rows and c columns (thus, each column has r elements)

 Locating element x[i][j]:
 j columns to the left of column 0  so j*r elements to the left of x[0][j]
 x[i][j] is mapped to position: j*r + i of the 1D array
 The location of element x[i][j]:

Location(x[i][j]) = start_address + W * (j*r + i)

Where
• start_address: the address of the first element in the array
• W: is the size of each element
• c: number of columns in the array

Example: array : int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};

Locating Element x[i][j]: column-major order
2D array: 3 rows, 6 columns
Example: int a[3][6]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
a[0][0]=0 a[0][1]=1 a[0][2]=2 a[0][3]=3 a[0][4]=4 a[0][5]=5
a[1][0]=6 a[1][1]=7 a[1][2]=8 a[1][3]=9 a[1][4]=10 a[1][5]=11
a[2][0]=12 a[2][1]=13 a[2][2]=14 a[2][3]=15 a[2][4]=16 a[2][5]=17
 Locating element x[i][j]:
 j columns to the left of column 0  so j*r elements to the left of x[0][j]
 x[i][j] is mapped to position: j*r + i of the 1D array
 The location of element x[i][j]:

Location(x[i][j]) = start_address + W * (j*r + i)

• Locating a[1][3] = 4*(3*3+1) = 40

Exercises
Assume I declare a 2-dimensional array int A[2]
[7]={1,2,3,4,5,6,7,8,9,10,11,12,13,14}. Let also assume that an "int" is
4 bytes long.

1. List the elements of A as they will appear in the computer memory if

the language stores the array A in row-major order
2. The array A is stored in row-major order starting at address 0 in the
computer memory. What is the address of A[1][3]?
3. The array A is stored in row-major order starting at address 0 in the
computer memory. Which value of A is stored at address 32?
4. List the elements of A as they appear in the computer memory if the
language stored the array A in column-major order
5. The array A is stored in column-major order starting at address 0 in
the computer memory. What is the address of A[1][3]?
6. The array A is stored in column-major order starting at address 0 in
the computer memory. Which value is stored at address 20?

11.
25
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

26
27
28
29
30
Record
• A record is a type of data structure like arrays
• A record have different fields each with its own type and name
• In C, the declaration of a record starts with the reserved word “struct”
• Then the type and the name of the fields in the record are defined
• Finally, the record is given a name
• To assign a value to a field of a record, we must first name the record and
then the field

int main(){
struct {
int num;
int deno;
}fraction;
[Link] = 13;
[Link] = 17;
}

31
2.2. More examples of records
• These define two objects of type record

• Example:

struct {
int numerator;
int denominator;
} fraction;
[Link] = 13;
[Link] = 17;
32
 An array of records
• The example below declare an array of records

int main(){
struct {
int id;
char* name;
char grade;
}student[3];
student[0].id = 2021;
student[1].name = "Big-X";
student[2].grade= 'A’;
printf("id %d, name %s, grade %c\n",student[0].id, student[1].name, student[2].grade);
}

33
 Records as types
• The record type can be used by the programmer to define its own types
• In this case, in C, the declaration of a record type starts by “typedef struct”
• Below, student is a type, not an object
• Minh is declared as pointer to an object of type student
• This pointer will store the addr of the first byte of a record of type student
• malloc allocate memory cells for a data structure of type student
• Since Minh is a pointer, we must dereference the fields of the object to which it points using “->”
• Minh->grade means “take the address stored in the pointer Minh (not the address of the pointer), then add
to this address the offset of grade

int main(){
typedef struct {
int id;
char* name;
char grade;
}student;
student* Minh;
Minh = (student*)malloc(sizeof(student));

Minh->id = 2021;
Minh->name = "Minh";
Minh->grade= 'A';
} 34
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

35
Linked lists

• A linked list is a data structure that stores

a sequence of elements.
• Each element in the list is a record called a
node, and each node has at least one
pointer field to another node in the list.
• The first node in the list is called the head,
and the last node in the list is called the
tail.
• Example:
10 8 20
head

36
37
38
39
2.3. Three types of linked list
• Singly linked list

10 8 20
head

• Doubly linked list

10 8 20
head

• Circular linked list

head

10 8 20
 Nodes in linked lists
• A node is a type
• The type node is declared through a record, a typedef struct
• Then pointers of type node are declared, such as “node *head”, here head is a
pointer
• Then memory for an object of type node is allocated through the malloc instruction
• This object is only known to the programmer through a pointer
• The pointer is given the address of the first byte of the object by a malloc instruction

int main(){
typedef struct {
int data;
struct node* next;
}node;
node* head;
head = (node*)malloc(sizeof(node));
}

41
 Create a second record of type node
• Here a second object of type node is created
– A pointer of type node is declared: “secondNode”
– Then malloc allocates memory for this second object, and returns the
address of the first byte of the object to the pointer secondNode

int main(){
typedef struct {
int data;
struct node* next;
}node;
node* head;
node* secondNode;
head = (node*)malloc(sizeof(node));
secondNode = (node*)malloc(sizeof(node));

42
 Create a link list of 2 nodes

• In the code below, a link list of two nodes is created

• The address of the first node of the link list is stored in the pointer head
• In the field head->next, the address of secondNode is copied
• The link list ends with the next pointer of secondNode set to NULL

node* head;
node* secondNode;
head = (node*)malloc(sizeof(node));
secondNode = (node*)malloc(sizeof(node));

head->data = 1;
head->next = secondNode;
secondNode->data = 2;
secondNode->next = NULL;
}

43
Singly Linked list
• A singly linked list is a sequences of nodes, each node contains 2 parts: data and
reference (address) to the next node:

• Example: Figure shows a singly linked list of four nodes:

• Keeping track of a singly linked list:

– Must know the pointer to the first element of the list (called start, head, etc.)
– If head is NULL, the singly linked list is empty

10 8 20
head
45
Elements of singly linked lists

• head: store the address of the first node in the linked list
• NULL: value of the pointer of the last node in the linked list
• cur: a pointer that stores the address of the current node

cur
head (or root)

NULL

46
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Traversing a singly linked list
for ( cur = head; cur != NULL; cur = cur->next )
print(Data_Of_Current_Node( cur->data ));

cur

head
NULL

• Change the value of the pointer cur

• Finish to browse the list when the NULL value is encountered

cur

head NULL
49
Operations on singly linked lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Operations on singly linked list: Insertion
• 4 positions in a singly linked list where a node can be inserted :
– At the beginning of the list
– After the position pointed by the pointer cur
– Before the position pointed by the pointer cur
– At the end of the list

cur
head

…
Insertion on singly linked list
Insert a new node:
• At the beginning of the list, asymptotic cost is O(1)

<create a new node new_node>;

new_node->next = head;
head= new_node;
head

…
node *Insert_ToHead(node *head, NodeType X)
{ node *new_node;
new_node = (node *) malloc(sizeof(node));
new_node->data = X;
new_nod new_node->next = head;
head=new_node;
e return head;
}

52
Insertion on singly linked list
• Insert a new node after the node pointed by the pointer cur, asymptotic cost
is O(1)
<create a new node new_node>;
new_node ->next = cur->next;
cur->next = new_node;

Write a function to insert a node with data = X (having the type «NodeType » after the
node pointed by the pointer cur. The function returns the address of the new node:
node *Insert_After(node *cur, NodeType X)
{ node *new_node;
new_node = (node *) malloc(sizeof(node)); //(1)
new_node -> data = X; //(1)
new_node->next = cur->next; //(2)
cur->next = new_node; //(3)
return new_node;
}

53
Insertion on singly linked list
Insert a new node before the node pointed by the pointer cur, asymptotic
cost is O(n)
<create a new node new_node>;
prev->next = new_node;
new_node->next = cur;

prev cur
head
…

Insert a new 54
node:
Operations on singly linked list: Insertion
Insert a new node: head
• At the beginning O(1)
• After the node pointed by cur O(1)
• Before the node pointed by cur O(n)
…
• At the end of the list O(n)
<create a new node new_node>;
if (head == NULL) { /* list does not have any node yet*/
head = new_node;
}
else {
//move the pointer to the end of the list:
node *last =head;
while (last->next != NULL) last = last->next;
//Change the pointer next of the last node:
last->next = new_node;
}
node *Insert_ToLast(node *head, NodeType X)
{ node *new_node;
new_node = (node *) malloc(sizeof(node));
new_node->data = X;
if (head == NULL) head = new_node;
else
{
node *last;
last=head;
while (last->next != NULL) // move to the last node
last = last->next;
last->next = new_node;
}
return head; 55
}
Delete the first node of the list
• Delete the node del that is currently the first node of the list
O(1):
head = del->next;
free(del);
del

head NULL

56
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Delete the node in the middle/end of the list
Delete node del that is currently the middle/last node of the list O(n):
<Determine the pointer prev pointed to the previous node of del>;
prev->next = del->next; //modify the link
free(del); //delete node del to free memory

prev del
head

prev del
head

NULL
58
Insertion on singly linked list
• Insert a new node after the node pointed by the pointer cur, asymptotic cost
is O(1):
<create a new node new_node>;
new_node->next = cur->next;
cur->next = new_node;

cur
head

new_nod 59
Delete the node at the middle/end of the list
Delete node del that is currently the middle/last node of the list O(n):

<Determine the pointer prev pointed to the previous node of del>;

prev->next = del->next; //modify the link
free(del); //delete node del to free memory)

Node *prev =head;

while (prev->next != del) prev = prev->next;

prev del
head

…
60
Delete the node at the middle/end of the list
Delete node del that is currently the middle/last node of the list:

<Determine the pointer prev pointed to the previous node of del>;

prev->next = del->next; //modify the link
free(del); //delete node del to free memory)

Node *prev =head;

while (prev->next != del) prev = prev->next;

prev del
head

…
61
Check whether the singly linked list is empty or not
Write the function int IsEmpty(node *head)
to check whether the singly linked list is empty or not (the pointer head pointed to the
first node of the list).
The function returns 1 if the list is empty; 0 otherwise

int IsEmpty(node *head) {

if (head == NULL)
return 1;
else return 0;
}
Operations on singly linked Lists
• Traverse the singly linked list
• Insert a node into the singly linked list
• Delete a node from the singly linked list
• Search data in the singly linked list
Searching
• To search for an element, we traverse from head until we locate the object or we reach the end
of the list.
Example: Given a linked list consisting of integer numbers. Count the number of nodes with data
field equal to number x.
int countNodes(int x){
typedef struct { int count = 0;
int data; node* e = head;
struct node* next; while(e != NULL){
}node; if(e->data == x) count++;
node* head; e = e->next;
}
return count;
}

int Result1 = countNodes(24);

Result1 = ?
int a =7; Result2 = ?
int Result2 = countNodes(a);
Time Complexity: Singly-linked lists vs. 1D-arrays

Operation ID-Array Complexity Singly-linked list Complexity

Insert at beginning O(n) O(1)
Insert at end O(1) O(1) if the list has tail reference
O(n) if the list has no tail reference

Insert at middle* O(n) O(n)

Delete at beginning O(n) O(1)
Delete at end O(1) O(n)
Delete at middle* O(n): O(n):
O(1) access followed by O(n) O(n) search, followed by O(1) delete
shift
Search O(n) linear search O(n)
O(log n) Binary search

Indexing: What is O(1) O(n)

the element at a
given position k?

* middle: neither at the beginning nor at the end

2.3. Linked list
• Singly linked list

10 8 20
head

• Doubly linked list

10 8 20
head
tail
Doubly linked list
• A Doubly Linked List (DLL) contains an extra pointer, typically called previous
pointer, together with next pointer and data which are there in singly linked list

tail

• 2 special nodes: tail and head

– head has pointer prev = null
– tail has pointer next = null
• Basic operations are considered similar as in the singly linked list
Doubly linked list
• Declare doubly linked list to store integer numbers:

10 8 20

head tail

typdedef struct {
int number;
struct dllist *next;
struct dllist *prev;
} dllist;
dllist *head, *tail;
Delete a node pointed by a pointer p, O(1)
void Delete_Node (ddlist *p){
if (head == NULL) printf(”Empty list”);
else {
if (p==head) head = head->next; //Delete first element
else p->prev->next = p->next;
if (p->next!=NULL) p->next->prev = p->prev;
else tail = p->prev;
free(p);}
}

8 5 12 5

head p tail

69
Delete a node pointed by a pointer p
void Delete_Node (ddlist *p){
if (head == NULL) printf(”Empty list”);
else {
if (p==head) head = head->next; //Delete first element
else p->prev->next = p->next;
if (p->next!=NULL) p->next->prev = p->prev;
else tail = p->prev;
free(p);
}
}

8 5 12 5

head p tail

70
Insert a node after the node pointed by pointer p O(1)
void Insert_Node (NodeType X, ddlist *p){
if (head == NULL){ // List is empty
head =(ddlist*)malloc(sizeof(ddlist));
head->data = X;
head->prev =NULL;
head->next =NULL;
}
else{
ddlist *newNode;
newNode=(ddlist*)malloc(sizeof(ddlist));
newNode->data = X;
newNode->next = NULL;

newNode->next = p->next;
newNode->prev=p;
if (p->next!=NULL)
p->next->prev=newNode; 12
p->next = newNode;
}
}

8 5 5
71
p
Several variants of linked lists
• Some common variants of linked list:
– Circular Linked Lists
– Circular Doubly Linked Lists
– Linked Lists of Lists
• Basic operations on these variants are built similarly to the singly linked list
and the doubly linked list that we consider above.
Circular linked list

list

typedef struct {
NodeType data;
struct node * next; Store data

}next;
Circular Doubly Linked Lists

list

typedef struct {
NodeType data;
struct node * prev;
Store data

struct node * next;

}node;
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

75
What is a stack?
• A stack is a data structure that only allows items to be inserted and removed at one end
– We call this end the top of the stack
– The other end is called the bottom
• Access to other items in the stack is not allowed
• The last element to be added is the first to be removed (LIFO: Last In, First Out)
Operation on stack
• Push: the operation to place a new item at the top of the stack O(1)
• Pop: the operation to remove the next item from the top of the stack O(1)

M
C C C
R push(M) R item = pop() R
item = M
X X X
A A A
Implementing a Stack
• At least two different ways to implement a stack
– array
– linked list
• Which method to use depends on the application
– what advantages and disadvantages does each implementation have?
Stack: Array Implementation
• Implementing a stack using an array is fairly easy:
– The bottom of the stack is at S[0]
– The top of the stack is at S[numItems-1]
– push onto the stack at S[numItems]
– pop off of the stack at S[numItems-1]

…
S
0 1 2 numItems N
Stack: Array Implementation
Basic operations: typedef .... Item;
static Item *s;
• void STACKinit(int); static int maxSize;//maximum number of elements that the stack could have
static int numItems; //current number of elements on stack
• int STACKempty(); void STACKinit(int maxSize)
{
• void STACKpush(Item); s = (Item *) malloc(maxSize*sizeof(Item));
• numItems = 0;
Item STACKpop(); }
int STACKempty(){return numItems==0;}
int STACKfull() {return numItems==maxSize;}

void STACKpush(Item item)

{
if (Stackfull()) ERROR(“Stack is full”);
else
{ s[numItems] = item;
numItems++;
}
}
Item STACKpop()
{
if (STACKempty()) ERROR(“Stack is empty”)
else
{
numItems--;
return s[numItems+1];
}
}
Array Implementation Summary
• Advantages
– Easy to implement
– best performance: push and pop can be performed in O(1) time
• Disadvantage
– fixed size: the size of the array must be initially specified because
• The array size must be known when the array is created and is fixed, so that the right
amount of memory can be reserved
• Once the array is full no new items can be inserted
• If the maximum size of the stack is not known (or is much larger than the expected
size) a dynamic array (an array created with malloc()) can be used
– But occasionally push will take O(n) time

…
S
0 1 2 numItems maxSize
maxSize: maximum number of elements in the array
Implementing a Stack: using linked list
• Store the items in the stack in a linked list
• The top of the stack is the head node, the bottom of the stack is the end
of the list
• push by adding to the front of the list O(1)
• pop by removing from the front of the list O(1)
4.1 2.4 8.9 2.3 NULL

top
3.3
3.3 4.1 2.4 8.9 2.3 NULL
4.1
typedef struct {
2.4 top float item;
struct StackNode *next;
8.9 } StackNode;
typedef struct {
2.3 StackNode *top;
}Stack;
Operations
1. Init:
Stack *StackConstruct();
2. Check empty:
int StackEmpty(Stack* s);
3. Check full:
int StackFull(Stack* s);
4. Insert a new item into stack (Push): insert a new item at the top of stack
int StackPush(Stack* s, float* item);
5. Remove an item from stack (Pop): remove and return the item at the top of stack:
float pop(Stack* s);
6. Print out all items of stack
void Disp(Stack* s);
Initialize stack
Stack *StackConstruct() {
Stack *s;
s = (Stack *)malloc(sizeof(Stack));
if (s == NULL) {
return NULL; // No memory
}
s->top = NULL;
return s;
}

/**** Destroy stack *****/

void StackDestroy(Stack *s) {
while (!StackEmpty(s)) {
StackPop(s);
}
free(s);
}
84
/*** Check empty ***/
int StackEmpty(const Stack *s) {
return (s->top == NULL);
}

/*** Check full ***/

int StackFull() {
printf("\n NO MEMORY! STACK IS FULL");
return 1;
}

85
Push
Need to do the following steps:
(1) Create new node: allocate memory and assign data for new node
(2) Link this new node to the top (head) node
(3) Assign this new node as top (head) node
int StackPush(Stack *s, float item) {
StackNode *node;
node = (StackNode *)malloc(sizeof(StackNode)); //(1)
if (node == NULL) {
StackFull(); return 1; // overflow: out of memory
}
node->item = item; //(1)
node->next = s->top; //(2)
s->top = node; //(3)
return 0;
}
Pop
1. Check whether the stack is empty
2. Memorize address of the current top (head) node
3. Memorize data of the current top (head) node
4. Update the top (head) node: the top (head) node now points to its next node
5. Free the old top (head) node
6. Return data of the old top (head) node

float StackPop(Stack *s) {

float data;
StackNode *node;
if (StackEmpty(s)) //(1)
return NULL; // Empty Stack, can't pop
node = s->top; //(2)
data = node->item; //(3)
s->top = node->next; //(4)
free(node); //(5)
return data; //(6)
}
Contents
2.1. Array
2.2. Record
2.3. Linked List
2.4. Stack
2.5. Queue

88
Queues
• What is a queue?
– A sequential data structure where homonegeous items are inserted only at one end
and removed at the other end.

Back/rear/tail Queue Front/head

Elements enter 4 3 2 1 Elements exit

no changes of order
Example: A line at the supermarket
• Operations on queues:
– Enqueue - Add an item to the queue
– Dequeue - Remove an item from the queue
• A queue is called a FIFO (First in-First out) data structure.

Add/ (Remove/Dequeue)
Enqueue
Back/Rear Front/Head
Queue specification
Definitions: (provided by the user)
– maxSize: Max number of items that might be on the queue
– ItemType: Data type of the items on the queue
Operations:
• Q = init(); initialize empty queue Q
• isEmpty(Q); returns "true“ if queue Q is empty
• isFull(Q); returns "true“ if Q is full, indicates that we already use the maximum memory for
queue; otherwise returns “false”
• frontQ(Q); returns the item that is in front (head) of queue Q or returns error if queue Q is
empty.
• enqueue(Q,x); inserts item x into the back (rear) of queue Q. If before making insertion, the
queue Q is full, then give the notification about that.
• x = dequeue(Q); deletes the element at the front (head) of the queue Q, then returns x which
is the data of this element. If the queue Q is empty before dequeue, then give the error notification.
• print(Q); gives the list of all elements in the queue Q in the order from the front to the back.
• sizeQ(Q); returns the number of elements currently in the queue Q.
Implementing a Queue
• Just like a stack, we can implementing a queue in two ways:
– Using an array
– Using a linked list
Implementing a Queue: using Array
• Using an array to implement a queue is significantly harder than using an array
to implement a stack.
– A stack: we add and remove at the same end,
– A queue: we add to one end and remove from the other.

QUEUE
Array implementation of queues

• An array “Q” of size n

• Two pointers each representing one end of the queue
– front: the end side where items are removed from the queue
– rear: the end side where items are added to the queue

0 1 2 3 4 5 6
7
Q: 17 23 97 44

front = 0 rear = 3

• Enqueue(Q,x): put item x in the queue

– rear++; Q[rear] = x
• Dequeue(Q): remove item x from the queue
– Dequeue Q[front]; front++;
93
Array implementation of queues

front = 0 rear = 3

Initial queue: 17 23 97 44

After insertion: 17 23 97 44 333

After deletion: 23 97 44 333

front = 1 rear = 4

• Notice the content of the array moves to the right as items

are inserted and deleted
• This will be a problem after a while!
94
Circular arrays

• We can treat the array holding the queue elements as a circular

array

• An array is circular when the first element is next of the last element

• modulo arithmetic is used to

compute each next entry in an
array
• Let n be the size of an array
• Next to element i, next(i), is
computed as i+1 modulo n
• The modulo operation in C is
represented by %
• next(i) = (i+1)%n

95
 Queues with circular arrays

• Elements were added to this queue in the order 11, 22, 33, 44, 55, and will be
removed in the same order

0 1 2 3 4 5 6
7
Q: 44 55 11 22 33

rear = 1 front = 5
• The Dequeue and Enqueue operations are now defined
as follow
– Dequeue(Q) : Dequeue Q[front]; front = (front + 1)
% n;
– Enqueue(Q,x): rear = (rear + 1) % n; Q[rear] = x;
96
 Queue full or empty
• If the queue become completely full, it would look like this:

0 1 2 3 4 5 6
Q: 7
44 55 66 77 88 11 22 33

rear = 4 front = 5
• If we remove all eight items, making the queue completely
empty, it will look like this:
0 1 2 3 4 5 6
7
Q:

rear = 4 front = 5
• Can’t tell whether the queue is full or empty 97
Queues full or empty: solutions
• Solution 1: Keep an additional variable count which
stores the current number of items in the queue
0 1 2 3 4 5 6
7
Q: 44 55 66 77 88 11 22 33

count = 8 rear = 4 front = 5

• Solution 2: Keep a gap between elements: consider
the queue full when it has n-1 elements

0 1 2 3 4 5 6
7
Q: 44 55 66 77 11 22 33

rear = 3 front = 5
98
 Implementation of solution 1:
• Solution 1: Keep an additional variable

0 1 2 3 4 5 6
7
Q: 44 55 66 77 88 11 22 33

count = 8 rear = 4 front = 5

• Dequeue(Q) :
if (count == 0) return ‘queue is empty’;

else Dequeue Q[front]; front = (front + 1) % n;

count--;
• Enqueue(Q,x):
if (count == n) return ‘queue is full’;
else rear = (rear + 1) % n; Q[rear] = x; count++;
99
 Implementation of solution 2:
• Solution 2: the front pointer always point to the gap entry in the
array
0 1 2 3 4 5 6
7
Q: 44 55 66 77 11 22 33

rear = 3 front = 4
• Dequeue(Q) :
if (rear == front) return ‘queue is empty’;

else front = (front + 1) % n; Dequeue

Q[front];
• Enqueue(Q,x):
if (rear+1 == front) return ‘queue is full’;
else rear = (rear + 1) % n; Q[rear] = x; 100
Implementing a Queue: using Array
• Circular queue
Solution 2: Make front point to the element preceding the front element in the queue (one
memory location will be wasted).
• The initial values for front and rear :
front = rear = maxSize – 1;
• Q[front+1]: the first item of the queue
• Q[rear]: the last item of the queue
• Add item to the Q (Enqueue):
– rear+=1; if (rear == maxSize) rear = 0;
– Q[rear]=item
• Remove item from Q (Dequeue):
– front = (front + 1) % maxSize;
– then remove Q[front] from queue
• Detect queue is empty: rear == front
• Detect queue is full: (rear + 1) % maxSize == front
ke front point to the element preceding the front element in the queue (one memory
location will be wasted).
Solution 2: Make front point to the element preceding the front element in the queue
(one memory location will be wasted)
init(int max) //initialize empty queue Q
{ maxSize = max;
front = maxSize – 1;
rear = maxSize – 1;
Q = new ItemType[maxSize];
}
int sizeQ(Q) //returns the number of elements currently in the queue Q
{ int size = (maxSize – front + rear) % maxSize;
return size;
}

0 1 2 3 4 5 6
7
Q: 44 55 66 77 11 22 33

rear = 3 front = 4
102
Solution 2: Make front point to the element preceding the front element in the queue
(one memory location will be wasted)
isEmpty(Q) // returns "true“ if queue Q is empty
{
if (rear == front) return true;
else return false;
}
isFull(Q) /*returns "true“ if Q is full, indicates that we already use the maximum memory for queue;
otherwise returns “false” */
{
if ((rear + 1) % maxSize == front) return true;
else return false;
}
frontQ(Q) //returns the item that is in front (head) of queue Q or returns error if queue Q is empty.
{
return Q[front + 1];
}

103
Solution 2: Make front point to the element preceding the front element in the queue
(one memory location will be wasted)
enqueue(Q,x) /*inserts item x into the back (rear) of queue Q. If the queue is full before making insertion, then give the
notification about that*/
{
if (isFull(Q)) ERROR(“Queue is FULL”);
else
{ rear ++;
if (rear == maxSize) rear = 0;
Q[rear] = x;
}
}
enqueue(Q,x)
{
if (isFull(Q)) ERROR(“Queue is FULL”);
else
{ rear = (rear + 1) % maxSize;
Q[rear] = x;
}
} 104
Solution 2: Make front point to the element preceding the front element in the queue
(one memory location will be wasted)
dequeue(Q) /*deletes the element at the front (head) of the queue Q, then returns x which is the data of this element. If the queue Q is empty
before dequeue, then give the error notification*/
{
if (isEmpty(Q)) ERROR(“Queue is EMPTY”);
else
{ front = (front + 1);
if (front == maxSize) front = 0;
return Q[front];
}
}
dequeue(Q)
{ if (isEmpty(Q)) ERROR(“Queue is EMPTY”);
else
{ front = (front + 1) % maxSize;
return Q[front];
}
}

105
Implementing a Queue: using a linked list
typedef struct {
DataType element;
struct node *next;
} node;
typedef struct {
node *front;
node *rear;
} queue;
where DataType is data type of the object need to store in the queue;
DataType need to be declared before declaring the queue.
• Implementing a queue using a linked list:
– 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.
Example -
Given the sequence of operations on queue Q as following. Determine the output and the data
on the queue Q after each operation:

Operation Output Queue Q

1 enqueue(Q,5) - (5)
2 enqueue(Q,3) - (5, 3)
3 dequeue(Q) 5 (3)
4 enqueue(Q,7) - (3, 7)
5 dequeue(Q) 3 (7)
6 front(Q) 7 (7)
7 dequeue(Q) 7 ()
8 dequeue(Q) error ()
9 isEmpty(Q) true ()
10 size(Q) 0 ()
11 enqueue(Q,9) - (9)
12 enqueue(Q,7) - (9, 7)
13 enqueue(Q,3) - (9, 7, 3)
14 enqueue(Q,5) - (9, 7, 3, 5)
15 dequeue(Q) 9 (7, 3, 5)