Scribd
Upload
3 views

CENG205-Lecture5

Uploaded by

kaankocahsp
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views

CENG205-Lecture5

Uploaded by

kaankocahsp
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 42

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

You might also like