CENG 205
Data structures
Lecture 5:
Stacks and Queues
Stacks
• A list on which insertion and deletion can be performed.
• Based on Last-in-First-out (LIFO)
• Stacks are used for a number of applications:
• Converting a decimal number into binary
• Program execution
• Parsing
• Evaluating postfix expressions
• Towers of Hanoi
…
Stacks
A stack is an ordered lists in which insertions and deletions are made at one end
called the top.
Stacks
top
C top
top
B B B
top
A A A A
Towers of Hanoi
Object of the game is to move all the disks (animals) over to Tower 3.
But you cannot place a larger disk onto a smaller disk.
Towers of Hanoi
Towers of Hanoi
Towers of Hanoi
Towers of Hanoi
Towers of Hanoi
Towers of Hanoi
Towers of Hanoi
Towers of Hanoi
Stack Operations
1. Pop()
2. Push(x)
3. Top()
4. IsEmpty()
• An insertion (of, say x) is called push operation and removing the
most recent element from stack is called pop operation.
• Top returns the element at the top of the stack.
• IsEmpty returns true if the stack is empty, otherwise returns false.
All of these take constant time - O(1)
Example
• Push(2)
• Push(10)
• Pop()
• Push(7)
• Push(5)
• Top(): 5
• IsEmpty(): False
Array implementation of stack (pseudocode)
int A[10]
top -1 //empty stack
Push(x)
{
top top + 1
A[top] x
}
Pop()
{
top top – 1
}
For an empty stack, top is set to -1.
In push function, we increment top.
In pop, we decrement top by 1.
Array implementation of stack (pseudocode)
Top()
{
return A[top]
}
IsEmpty()
{
if(top == -1)
return true
else
return false
}
Stack
Data Structure
#define MAX_STACK_SIZE 100
typedef struct{
int VALUE;
}element;
element stack[MAX_STACK_SIZE];
int top=-1;
Push Stack
// adds the given item to stack if not full
void push (element item)
{
if(top >= MAX_STACK_SIZE-1){ //is full
return;
}
stack[++top]=item;
}
Pop Stack
// removes and returns the item
// some pop implementations only removes
element pop()
{
if(top==-1)
return empty_stack(); //empty
return stack[top--];
}
Implementation of Stacks Using Arrays
3
More array implementation
Queues
• A queue is an ordered list on which
• all insertions take place at one end called the rear/back and
• all deletions take place at the opposite end called the front.
• Based on First-in-First-out (FIFO)
Comparison of Queue and Stack
Queues
rear
C
rear B
B
rear
A A A
front,rear front front
front
Queue is a list with the restriction that insertion can be made at one end (rear)
And deletion can be made at other end (front).
Built-in Operations for Queue
Enqueue(x) or Push(x)
Dequeue() or Pop()
Front(): Returns the element in the front without removing it.
IsEmpty(): Returns true or false as an answer.
IsFull()
Each operation takes constant time, therefore has O(1) time complexity.
Example
Enqueue(2)
Enqueue(5)
Enqueue(3)
Dequeue()→ 2
Front()→ 5
IsEmpty()→ False
Applications:
• Printer queue
• Process scheduling
Array implementation of queue (Pseudocode)
int A[10]
front -1
rear -1
IsEmpty(){
if (front == -1 && rear == -1)
return true
else
return false}
Enqueue(x){
if IsFull()
return
else if IsEmpty()
front rear 0
else
rear rear+1
A[rear] x
}
Array implementation of queue (Pseudocode)
Dequeue(){
if IsEmpty(){
return
else if (front == rear)
front rear -1
else{
front front+1
}
At this stage, we cannot Enqueue an element anymore.
Queue
Data Structure
#define MAX_QUEUE_SIZE 100
typedef struct{
int value;
}element;
element queue[MAX_QUEUE_SIZE];
int front = -1;
int rear = -1;
Add Queue
void enqueue(element item)
{
if(rear == MAX_QUEUE_SIZE-1){ //is full
return;
}
else if(front == -1) //is empty
front = 0;
queue[++rear]=item;
}
Delete Queue
element dequeue()
{
if(front == -1) //is empty
return empty_queue(); //empty
element data = queue[front];
if(front == rear) //is only one item
front = rear = -1;
else
front++;
return data;
}
Circular Queue
• More efficient queue representation
• When the queue is full
(the rear index equals to MAX_QUEUE_SIZE)
• We should move the entire queue to the left
• Recalculate the rear
Shifting an array is time-consuming!
• O(MAX_QUEUE_SIZE)
Circular Queue
Enqueue for circular array (Pseudocode)
Current position = i
Next position = (i+1)% N
previous position = (i+N-1)%N
Enqueue(x){
if (rear+1)%N == front
return
else if IsEmpty()
front rear 0
else
rear (rear+1)%N
A[rear] x
}
Dequeue for circular array (Pseudocode)
Dequeue(x){
if IsEmpty()
return
else if(front == rear)
front rear -1
else
front (front+1)%N
}
Add Circular Queue
void enqueueCircular(element item)
{
if((rear+1) % MAX_QUEUE_SIZE == front) //if full
return; //queue full
if(front == -1) //is empty
front = 0;
rear = (rear+1) % MAX_QUEUE_SIZE;
queue[rear]=item;
}
Delete Circular Queue
element dequeueCircular()
{
if(front == -1) //is empty
return empty_queue(); //empty
element data = queue[front];
if(front == rear) //is only one item
front = rear = -1;
else
front = (front+1) % MAX_QUEUE_SIZE;
return data;
}
References
• http://www.mycodeschool.com/videos
