Simple Data Structures -1
Arrays, Stacks and Queues
Y.N. Srikant
Visiting Professor
Chanakya University
(Formerly) Professor
Computer Science and Automation
Indian Institute of Science
Bangalore 560 012
Y.N. Srikant Array-Stack-Queue
Abstract Data Type and Data Structure
Abstract data type (ADT)
A mathematical model with a collection of operations
defined on the data inside that model.
Operations have well defined properties and affect only
local data inside the ADT model.
The data in the model can be accessed only with the
operations defined in the ADT.
ADT can be used to prove properties of an implementation.
In practice, they guide implementations.
Data Structure
A collection of variables of different types connected in
various ways.
Used to represent the data part of the mathematical model
of an ADT.
Operations and the data structure together form an
implementation of an ADT.
Y.N. Srikant Array-Stack-Queue
Array ADT
1 An array is a set of pairs of the form (index, value).
2 No two pairs of this set have the same index.
3 The operations supported on an array are the following.
CREATE(A) - creates an empty array A.
STORE(A,i,x) - Adds the pair (i,x) to A. Overrides the old
pair if one already exists.
RETRIEVE(A,i) - Retrieves and returns the value at index i
in array A.
4 An array is usually a primitive data type in most
programming languages.
5 Each value in an array can itself be an array.
6 Arrays are usually of fixed size.
7 Arrays are used extensively in numerical computation to
store and manipulate matrices and tensors (higher
dimensional matrices).
Y.N. Srikant Array-Stack-Queue
Array Mapping in C and Numpy - 1
Arrays in Numpy and C are of fixed size.
Assume that A[n1 , n2 , n3 ] is a 3-D array of integers and that
B[n1 ∗ n2 ∗ n3 ∗ 4] is a 1-D array of bytes, both of the same
capacity. B corresponds to memory. Each integer is assumed
to take 4 bytes. Assume row-major ordering.
Size of each slice is n2 ∗ n3 ∗ 4 bytes, size of each row is
n3 ∗ 4 bytes and size of each element is 4 bytes.
A[i, j, k ] is mapped to the address
B[i ∗ n2 ∗ n3 ∗ 4 + j ∗ n3 ∗ 4 + k ∗ 4].
For efficient computation, this can be written as
B[(((i ∗ n2 ) + j) ∗ n3 + k ) ∗ 4]
Y.N. Srikant Array-Stack-Queue
Array Mapping in C and Numpy - 2
Y.N. Srikant Array-Stack-Queue
Homework: Not to be submitted
Find an efficient mapping to a 1-D array for the following types
of matrices.
1 A diagonal 2-D matrix a[n, n] (all elements other than the
diagonal are zero). 1-D array should not use more than n
elements.
2 Lower diagonal 2-D matrix (a[i, j] = 0 for i = 0, ..., n − 1,
and j = i + 1, ..., n − 1). 1-D array should not use more
than (n2 + n)/2 elements.
3 Similarly, consider upper diagonal, and band matrices.
Y.N. Srikant Array-Stack-Queue
Tensor Mapping in TensorFlow - An Example
Video data is stored as a 5-dimensional tensor in
TensorFlow - (batch, frames, height, width, channels).
Batch(B): Number of videos to be processed.
Frames(F): Number of frames in each video. Each frame is
essentially an image frozen in time.
Height(H), Width(W): Each frame has height x width
number of pixels (i.e., rows x columns).
Channels(C): The number of colors in each pixel. Usually,
each color requires one byte or one float (4 bytes). For
example, for RGB (#channels = 3), each of R,G, and B
require one byte to store the intensity.
Embeddings used in deep learning are also stored as
multi-dimentional tensors with hundreds of dimensions.
Homework: Study embeddings in detail.
Y.N. Srikant Array-Stack-Queue
Tensor Mapping in TensorFlow - An Example
This meta data, a 5-tuple of the form (B,F,H,W,C), (example
- (5,10,8,10,3)), is stored separately from the raw data.
The raw data of a video tensor is stored as one large
contiguous memory buffer (see next slide).
Batches are slices of this buffer, frames are slices of each
batch, rows are slices of each frame, etc.
Homework: For a video tensor access vt[b,f,h,w,c], where, b, f,
h, w, and c are the batch number, frame number, row number,
column number, and color number (assume R=0, G=1, and
B=2), write down the mapping function just like in the array
mapping case. Assume that each color in a pixel requires 4
bytes (instead of one byte that was mentioned earlier).
Y.N. Srikant Array-Stack-Queue
Video Tensor Mapping in TensorFlow
Y.N. Srikant Array-Stack-Queue
List Mapping in Python
Lists in Python can change size dynamically.
Y.N. Srikant Array-Stack-Queue
List Mapping in Python
Lists in Python can change size dynamically.
Y.N. Srikant Array-Stack-Queue
List Mapping in Python
Y.N. Srikant Array-Stack-Queue
Sparse Matrix and Tensor Representations
1 Coordinate format (COO): Used for tensors in TensorFlow.
Generally not used for matrices.
2 Compressed Sparse Row format (CSR): Most commonly
used format for matrices and internally in TensorFlow.
3 Compressed Sparse Column format (CSC): Popular in
scripting languages. It is the default format for sparse
matrices in the languages Julia and Matlab.
We discuss COO and CSR formats. CSC is similar to CSR and
is not discussed (for self study).
Y.N. Srikant Array-Stack-Queue
Sparse COO Format
Y.N. Srikant Array-Stack-Queue
Sparse COO-Sorted Format
Y.N. Srikant Array-Stack-Queue
Sparse CSR Format
Y.N. Srikant Array-Stack-Queue
Stack ADT
A stack is a last-in-first-out structure.
A stack ADT is a collection of elements with the following
operations:
1 void MAKENULL(S) - Make an empty stack, S
2 eletype TOP(S) - Return the top element of S
3 eletype POP(S) - Return and delete the top element of S
4 void PUSH(x,S) - Insert the element x at the top of S
5 boolean EMPTY(S) - True if S is empty, else false
Why is a is_FULL(S) operation not defined? That is because
abstract stacks never become full! But, implementations must
deal with this issue.
Y.N. Srikant Array-Stack-Queue
Y.N. Srikant Array-Stack-Queue
Stacks in Python -1
class Stack: |
def __init__(self): | s = Stack()
[Link] = [] | [Link](’Hello!’)
| [Link](’How are you?’)
def Empty(self): | print([Link]())
return [Link]==[] |
| Push() and Pop()
def push(self, item): | both require O(1)
[Link](item)| time.
|
def pop(self): |
return [Link]()
def top(self):
return [Link][len([Link])-1]
Y.N. Srikant Array-Stack-Queue
Stacks in Python -2
class Stack: |
def __init__(self): | s = Stack()
[Link] = [] | [Link](’Hello!’)
| [Link](’How are
def Empty(self): | you?’)
return [Link] == [] | print([Link]())
|
def push(self, item): | Push() and Pop()
[Link](0,item) | both require O(n)
| time!
def pop(self): |
return [Link](0)
def top(self):
return [Link][0]
Y.N. Srikant Array-Stack-Queue
Stacks in C
struct stack {int elements[50]; int top; };
int inf = 999999;
void MAKENULL(struct stack* s)
{s->top = 50;}
int EMPTY(struct stack* s)
{if (s->top == 50) return 1; else return 0; }
int TOP(struct stack* s)
{if(EMPTY(s)){printf("empty stack");return inf;}
else return (s->elements[s->top]); }
int POP(struct stack* s)
{if(EMPTY(s)){printf("empty stack");return inf;}
else return (s->elements[s->top++]); }
void PUSH(int x, struct stack* s)
{if (s->top == 0) printf("stack is full");
else {s->elements[--s->top] = x; }}
Y.N. Srikant Array-Stack-Queue
Stacks in C
int main(){
struct stack s; int i, x;
MAKENULL(&s);
for(i=0; i<10; i++)
{PUSH(i, &s); printf("%d", i); }
printf("\n");
while (!EMPTY(&s))
printf("%d", POP(&s));
printf("\n");
}
Homework: Not to be submitted
Write a program in C to implement two stacks in a single array.
Try to utilize the space efficiently.
Y.N. Srikant Array-Stack-Queue
Applications of Stacks
1 Support for function calls with recursion.
Runtime memory management (activation records).
Storing return addresses.
2 Stack machine implementation.
Java Virtual Machine (JVM), Python Virtual Machine.
3 Postfix, prefix, and infix expression evaluation.
4 Sorting(?) with a stack.
Y.N. Srikant Array-Stack-Queue
Code and Data Area in Memory
• Most programming languages distinguish between
code and data
• Code consists of only machine instructions and
normally does not have embedded data
• Code area normally does not grow or shrink in size as
execution proceeds
• Unless code is loaded dynamically or code is produced
dynamically
• As in Java – dynamic loading of classes or producing classes and
instantiating them dynamically through reflection
• Memory area can be allocated to code statically
• We will not consider Java further in this lecture
• Data area of a program may grow or shrink in size
during execution
Y.N. Srikant Array-Stack-Queue
Static Versus Dynamic Storage
Allocation
• Static allocation
• Compiler makes the decision regarding storage allocation by
looking only at the program text
• Dynamic allocation
• Storage allocation decisions are made only while the program
is running
• Stack allocation
• Names local to a procedure are allocated space on a stack
• Heap allocation
• Used for data that may live even after a procedure call returns
• Ex: dynamic data structures such as symbol tables
• Requires memory manager with garbage collection
Y.N. Srikant Array-Stack-Queue
Static Data Storage Allocation
• Compiler allocates space for all Main program
variables (local and global) of all variables
procedures at compile time
• No stack/heap allocation; no Procedure P1
overheads variables
• Ex: Fortran IV and Fortran 77
• Variable access is fast since Procedure P2
addresses are known at compile time variables
• No recursion
Procedure P4
variables
Main memory
Y.N. Srikant Array-Stack-Queue
Dynamic Data Storage Allocation
• Compiler allocates space only for global variables at
compile time
• Space for variables of procedures will be allocated at
run-time
• Stack/heap allocation
• Ex: C, C++, Java, Fortran 8/9
• Variable access is slow (compared to static allocation)
since addresses are accessed through the stack/heap
pointer
• Recursion can be implemened
Y.N. Srikant Array-Stack-Queue
Dynamic Stack Allocation in C
Stack of activation
records
Main
Calling sequence:
For accessing Main à R à Q à R
variables of R
Main
Base
R
Currently active
Next procedure
Y.N. Srikant Array-Stack-Queue
Activation Record Structure
Return address
Note:
Access and Control link
The position of the fields of
(Address of) function result the activation record as
shown are only notional.
Actual parameters
Implementations can choose
different orders;
Local variables e.g., function result could be
after local var.
Temporaries
Saved machine status
Space for local arrays
Y.N. Srikant Array-Stack-Queue
Basics of the Java Virtual Machine (JVM) - 1
Java bytecode is the instruction set of the JVM.
Each instruction consists of one byte of opcode and zero
or more bytes of operands.
Java bytecode is designed to run on most common
platforms, such as desktops, laptops, phones, tablets, etc.
The bytecode comprises data manipulation, control
transfer, object creation and manipulation, and method
invocation instructions.
The frame (activation record) of a method call in JVM has
both an operand stack and a set of registers.
Operand stack: used for computations, such as addition,
multiplication, etc.
Registers: used to store local variables and method
arguments.
Y.N. Srikant Array-Stack-Queue
JVM Frames
Y.N. Srikant Array-Stack-Queue
Basics of the Java Virtual Machine (JVM) - 2
Java program
x = 10; Java byte code defines
x = 25-x; several types of “load
c = x * 80; constant”, “load”, “store”,
-------------------- arithmetic, and “branch”
Byte code: instructions.
stack=2, locals=2
For example, iconst_<i>,
0: ldc 10
dconst_<d>,
1: istore 1
fconst_<f>, bipush,
2: ldc 25
sipush, and ldc are all
3: iload 1
different types of “load
4: isub
constant” instructions.
5: istore 1
6: iload 1 We consider only one type of
7: ldc 80 these instructions in the
8: imul example shown beside.
9: istore 2
10: return
Y.N. Srikant Array-Stack-Queue
JVM Byte Code Execution
Y.N. Srikant Array-Stack-Queue
Postfix and Prefix Expression Evaluation
Postfix expression evaluation
Example: ab+cd-*ef/+ and 1 2 + 3 4 - * 10 5 / + (= -1).
1 Scan the input from left to right.
2 Push operands into a stack until an operator is met.
3 Pop the required number of operands for that operator from
the stack.
4 Evaluate the operator and push the result into the stack.
5 Repeat this procedure until the input is empty.
6 The stack at this point must have just the final result.
Prefix Expression Evaluation
Example: +*+ab-cd/ef and + * + 1 2 - 3 4 / 10 5 (= -1).
Scan the input from RIGHT to LEFT. Do exactly as in
postfix evaluation.
Infix Expression Evaluation See second slide from the
current slide (self reading).
Y.N. Srikant Array-Stack-Queue
Y.N. Srikant Array-Stack-Queue
Y.N. Srikant Array-Stack-Queue
Homework: Not to be submitted
1 Write programs in C/Python to perform infix and postfix
expression evaluations. Consider as many operators as
you can.
2 Write a program in C/Python to convert an infix expression
to postfix.
Y.N. Srikant Array-Stack-Queue
Micro-project -1
1 Implement a simulator for a small and simple subset of Java byte
code in C. Assume maximum sizes of the operand stack and
register set (local variables) to be 10 each (you may a larger
size, if you need it).
The subset of the instruction set that you need to simulate
consists of {ldc, iload, istore, iadd, isub, imul, idiv, ifeq, iflt, ifgt},
and two special instructions, {read, print}, that are not available
in Java byte code. read reads an integer from the keyboard, and
pushes it onto the operand stack. Similarly, print prints the
integer on the top of the stack on the console. You need to
implement the ldc instruction for integers only.
Supply a set of non-trivial programs in this subset of Java byte
code that you have tested the simulator with. You may learn
details of the byte codes from the URL:
[Link]
[Link]
Y.N. Srikant Array-Stack-Queue
Sorting with a Stack (Knuth’s Algorithm, self-reading)
1 Initialize an empty stack.
2 For each input value x do:
While the stack is nonempty and x is larger than the top
item on the stack, pop the stack to the output
Push x onto the stack
3 While the stack is nonempty, pop it to the output
This algorithm correctly sorts some input sequences, and
fails to sort others.
Sequence 3,2,1 is sorted correctly, but 2,3,1 is not sorted
correctly.
If the algorithm fails to sort an input, then that input cannot
be sorted with a single stack.
Y.N. Srikant Array-Stack-Queue
Queue ADT
A Queue is a FIRST-IN-FIRST-OUT structure.
A Queue is a collection of elements with the following
operations:
1 MAKENULL(Q) - Makes a null queue, Q
2 FRONT(Q) - Returns first element of Q
3 ENQUEUE(x,Q) - Inserts x at the end of Q
4 DEQUEUE(Q) - Deletes first element of Q
Another version: DEQUEUE(Q,x) - Deletes first element of
Q and assigns it to x
5 EMPTY(Q) - True if Q is empty, else false
A flat array is not a good candidate for implementing a queue.
Y.N. Srikant Array-Stack-Queue
Queues in Python
class Queue:
def __init__(self):
[Link] = []
def Empty(self):
return [Link] == []
def enqueue(self, item):
[Link](0,item)
def dequeue(self):
return [Link]()
q=Queue()
[Link](15)
[Link](’Welcome!’)
print([Link]())
Enqueue requires O(n) time and Dequeue O(1) time!
Y.N. Srikant Array-Stack-Queue
Circular Queues - 1
Y.N. Srikant Array-Stack-Queue
Circular Queues - 2
Y.N. Srikant Array-Stack-Queue
Circular Queue Implementation in C
struct Q{int elements[11]; int front,rear;};
int addone( int i ){ return((i+1) % 11);}
void makenull( struct Q *queue )
{ queue->front =0; queue->rear =10;}
int empty( struct Q *queue )
{ if (addone(queue->rear) == queue->front)
return 1;
else return 0;
}
void enqueue( int x, struct Q *queue )
{ if (addone(addone(queue->rear))
== queue->front)
printf("queue is full\n");
else{ queue->rear = addone(queue->rear);
(queue->elements)[queue->rear]=x;};
}
Y.N. Srikant Array-Stack-Queue
Circular Queue Implementation in C
void dequeue( struct Q *queue )
{ if (empty(queue)) printf("queue is empty\n");
else queue->front = addone(queue->front);
}
int front( struct Q *queue )
{ if (empty(queue))
{printf("queue is empty\n");return 999999;}
else return (queue->elements)[queue->front];
}
main() { struct Q queue; int a,b;
makenull(&queue);
for (b=0;b<11;b++) enqueue(b,&queue);
for(b=0;b<10;b++)
{printf("%d",front(&queue));dequeue(&queue);}
printf("\n");dequeue(&queue);
}
Y.N. Srikant Array-Stack-Queue
Circular Queue Implementation in C
int dequeue( struct Q *queue )
{ int x;
if (empty(queue)) {printf("queue is empty\n");
return 999999;}
else { x = (queue->elements)[queue->front];
queue->front = addone(queue->front);
return x;
}
}
main() { struct Q queue; int a,b;
makenull(&queue);
for (b=0;b<11;b++) enqueue(b,&queue);
for(b=0;b<10;b++)
{printf("%d",dequeue(&queue));}
printf("\n");a=dequeue(&queue);
}
Y.N. Srikant Array-Stack-Queue
Applications of Queues
1 Operating systems use print queues and task queues.
2 Railway reservation systems use queues to issue tickets.
3 Airport simulation.
4 In breadth-first search algorithm on graphs.
5 Image component labelling.
Homework: Not to be submitted
1 Modify the circular queue implementation to use two extra
variables to denote queue being full/empty. The array must
not have any empty locations when full.
2 Modify the circular queue implementation to use one extra
variable along with other conditions to denote queue being
full/empty. The array must not have any empty locations
when full.
Y.N. Srikant Array-Stack-Queue
Image Component Labeling
Y.N. Srikant Array-Stack-Queue
Image Component Labeling
for each row r do {//Component id=1 initially
for each column c in row r do {
if (pixel[r,c]==1) //new component id
{ pixel[r,c]=++id; [Link]=r; [Link]=c;
do { for each neighbor NBR of HERE do {
//in up,down,left,right directions
//by one pixel only
if (pixel[[Link],[Link]]==1){
pixel[[Link],[Link]]=id;
enqueue(Q,NBR);
}
}
if(empty(Q)) break;HERE=dequeue(Q);
} while(TRUE);
}
}
}// Time complexity is O(#rows*#cols)
Y.N. Srikant Array-Stack-Queue
Image Component Labeling in Python: Results
Input image Output with comp labels
------------------- -----------------------
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 1 0 0 0 0 2 2 0 0 3 3 0
0 0 0 0 1 0 1 0 1 0 0 0 0 0 2 0 4 0 3 0
0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 5 0 6 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0 0 5 5 5 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 5 0 0 0 0
0 0 1 1 1 0 0 1 1 0 0 0 7 7 7 0 0 8 8 0
0 0 1 1 0 1 1 1 1 0 0 0 7 7 0 8 8 8 8 0
0 0 0 1 0 0 0 1 0 0 0 0 0 7 0 0 0 8 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Y.N. Srikant Array-Stack-Queue
Double Ended Queue (Deque)
A Deque is a generalized version of stack and queue. Deques
are already available in Python. It is a collection of elements
with the following operations:
1 MAKENULL(Q) - Makes a null deque, Q (Q = deque()).
2 ENQUEFRONT(x,Q) - Inserts x at the front of Q
([Link]()).
3 DEQUEFRONT(Q) - Deletes and returns the element at
the front of Q ([Link]()).
4 ENQUEREAR(x,Q) - Inserts x at the rear of Q
([Link]()).
5 DEQUEREAR(Q) - Deletes and returns the element at the
rear of Q ([Link]()).
6 EMPTY(Q) - True if Q is empty, else false (not directly
available).
7 SIZE(Q) - Returns the number of elements in Q (len(Q)).
Python deques are very efficient. All enqueue and dequeue
operations require only O(1) time!
Y.N. Srikant Array-Stack-Queue
Homework (Not for Submission)
1 Implement a deque in C.
2 Show how to implement a stack and a queue using a
deque in C.
3 Implement a palindrome checker in C using a deque.
4 Implement a fixed size deque of strings in C, which
automatically removes an item from the front or rear (the
element of greater size is removed) when the number of
elements in the deque is exceeded during enqueue
operations.
Y.N. Srikant Array-Stack-Queue
