Stack
CSE 2215 - Lecture 8 - Summer 2023
Instructor : Fahmid Al Rifat, Lecturer, Dept. of CSE , UIU
fahmid@cse.uiu.ac.bd 1
Stack and Queue
A stack is a last in, first out (LIFO) data structure
Items are removed from a stack in the reverse order from the way they were
inserted.
A queue is a first in, first out (FIFO) data structure
Items are removed from a queue in the same order as they were inserted.
2 2
Stack: Last In First Out
A stack is a list with the restriction that insertions and deletions can be
performed in only one position, namely, the top of the stack.
The operations: push (insert) and pop (delete)
3 3
Application of Stack
Direct applications
Page-visited history in a Web browser
Undo sequence in a text editor
Saving local variables when one function calls another, and this one
calls another, and so on.
Indirectapplications
Auxiliary data structure for algorithms
Component of other data structures
4 4
Array Implementation of Stack
To implement a stack, items are inserted and removed at the same end (called the
top)
To use an array to implement a stack, you need both the array itself and an
integer
The integer tells you either:
Which location is currently the top of the stack, or
How many elements are in the stack
5 5
Stacks by Array: Push and Pop
If the bottom of the stack is at location 0, then an empty stack is represented
by
top = -1 or count = 0
To add (push) an element, either:
Increment top and store the element in stk[top], or
Store the element in stk[count] and increment count
To remove (pop) an element, either:
Get the element from stk[top] and decrement top, or
Decrement count and get the element in stk[count]
6 6
Stacks by Array: After Popping
When you pop an element, do you just leave the “deleted” element sitting in
the array?
The surprising answer is, “it depends”
If this is an array of primitives, or if you are programming in C or C++,
• then doing anything more is just a waste of time
If you are programming in Java, and the array contains objects, you should
set the “deleted” array element to null
Why? To allow it to be garbage collected!
7
Stacks by Array: Error Checking
There are two stack errors that can occur:
Underflow: trying to pop (or peek at) an empty stack
Overflow: trying to push onto an already full stack
For underflow, you should throw an exception
You could create your own, more informative exception
For overflow, you could do the same things
Or, you could check for the problem, and copy everything into a
new, larger array
8
Stacks by Array: PUSH() & POP()
void push(int x){ int pop() {
if(top >= n-1) int y;
printf("\n STACK over flow"); if(top <= -1)
else { printf("\n Stack under
top++; flow");
stk[top] = x; else {
} y = stk[top];
} top--;
return y;
}
}
9
Stack
• Sample Question:
Show the status of a STACK implemented by an array of size, m=5 for
the operations: push(10), push(20), pop(), push(30),push(40), pop(), pop(),
pop().
Initial stack, top = -1 Pop() , top = 0 Pop() , top = 1
10 10 30
Push(10) , top = 0 Push(30) , top = 1 Pop() , top = 0
10 10 30 10
Push(20) , top = 1 Push(40) , top = 2 Pop() , top = -1
10 20 10 30 40
10
Linked List Implementation of Stack
Since all the actions happen at the top of a stack, a singly-linked list (SLL) is a
fine way to implement it
The header of the list points to the top of the stack
Pushing is inserting an element at the front of the list
Popping is removing an element from the front of the list
11
Linked List Implementation of Stack
With a linked-list representation, overflow will not happen (unless
you exhaust memory, which is another kind of problem)
Underflow can happen, and should be handled the same way as for
an array implementation
When a node is popped from a list, and the node references an object,
the reference (the pointer in the node) need to be set to
null.
12
Push() Implementation – Linked List
struct Node {
int value;
struct Node* next;
};
struct Node* top;
void push(int data) {
struct Node* temp;
temp = (struct Node *)malloc(sizeof(struct
Node));
// Check if memory(heap) is full.
if (!temp){
cout << "\n Heap Overflow";
exit(1);
}
temp->value = data;
temp->next = top; 13
top = temp;
Pop() Implementation – Linked List
int pop(){
struct Node* temp;
int data;
if (top == NULL) {
cout << "\n Stack Underflow" << endl;
exit(1);
}
else {
data = top->value;
temp = top;
top = top->next;
free(temp);
return data;
}
}
14
QUEUE
15
Queue: First In First Out
A Queue is an ordered collection of items from which items may be removed at one
end (called the front of the queue) and into which items may be inserted at the other
end (the rear of the queue).
The operations: enqueue (insert) and dequeue (delete)
16
Queue
• Sample Question:
Show the status of a QUEUE for the following operations, where the QUEUE is implemented
by an array of size, m=3. Enqueue(164), Enqueue(83), Dequeue(), Enqueue(80), Enqueue(75),
Dequeue()
Initial queue, front=rear = -1 Dequeue(), front =1, rear =1 Dequeue(), front =2, rear =2
83 80
Enqueue(164), front =0, rear =0 Enqueue(80), front =1, rear =2
164 83 80
Enqueue(83), front =0, rear =1 Enqueue(75), overflow!
164 83 83 80
17
Thank You
18
