Data structure &
Programming ii
Stack data structure
1
Stack
2
Outline
❑ A Brief of Outline
▪ What is Stack?
▪ What are Stack operations?
▪ How to implement Stack in C++
▪ Examples
3
What is Stack?
❑ Definition
▪ Stack is a data structure that stores data in such a way that the element
stored last will be retrieved first
▪ This method is also called LIFO (Last In First Out)
Examples:
➢ A stack of copies
▪ The first copy put in the stack is the last one to be removed
▪ Similarly, the last copy put in stack is the first one to be
removed
➢ Stack of plates
➢ Stack of chairs 4
Applications of Stack
▪ Undo operation (browser, Ms. Word, …)
▪ Remembering completed task
▪ Design compilers and interpreters
▪ etc.
5
Queue Vs. Stack
❑ Differences
push(‘A’) pop()
top
enqueue(‘F’)
dequeue()
rear
front
Stack Queue
6
Stack Operations
❑ Operation
▪ A stack is controlled by two main operations which implement the LIFO method
▪ Insertion pop()
push(‘A’)
▪ Add element to the stack (add to the top)
▪ This method is called push top
▪ Deletion
▪ Remove element from the stack (remove from the top)
▪ This method is called pop
▪ The variable TOP is used to keep track of the top element in the stack
7
Stack Operations
❑ More operations
▪ push(): Add element to top of stack
▪ pop(): Remove element from top of stack
▪ isEmpty(): Check if stack is empty
▪ isFull(): Check if stack is full
▪ peek(): Get the value at the top of stack without removing it
8
Stack Implementation
❑ Implementation
top
➢ Stack can be implemented in two ways: push(10)
top
push(5) top push(16)
top=0 top=1 top=2
1. As an Array
1. Stack as Array
▪ An array to store data
▪ An integer type variable called TOP which stores the index of the top element of the stack
2. As a Linked List
▪ A linked list to store data
▪ A pointer variable called TOP which points to the top element of the list
9
2. Stack as Linked List
Stack as Linked List
➢ Dynamic
▪ It can grow or shrink at runtime
10
Stack Implementation
❑ Stack as a Linked List
11
Stack Implementation
❑ Stack as a Linked List
▪ Implementing stack as a linked list is just like implementing a linked list with some choices
Choice 1
▪ Element is added to the first of the list (push operation)
▪ Element can be only removed from the beginning of the list (pop operation)
Choice 2
▪ Element is added to the end of the list (push operation)
▪ Element can be only removed from end of the list (pop operation)
Remark: Choice 1 is recommended.
12
Stack as Array Vs. Stack as Linked list
❑ When to use?
➢ When we use array to implement stack?
▪ Must know exact size of the stack and it is small
➢ When we use Linked list to implement stack?
▪ Do not know the size of the stack.
▪ If the stack can be bigger and bigger, Linked list will be good to implement it.
13
Stack Implementation: Examples
❑ Stack as a Linked List
How to implement this Stack?
Demo coding in class push(‘A’) pop()
top
14
Q and A
15
Homework
❑ Reading: Sorting Algorithms
1. What is Sorting algorithm?
2. Give as many sorting algorithms as you can.
3. Provide an example on how to implement one of those sorting algorithms in C++?
1. Give an example of a program implementing a sorting algorithm
16
Example 1: Class activity
❑ Stack as Array void push(int item){
if(isFull()){
cout<<"\n\tStack overflow! can't add";
}else{
▪ Modify code at Part 3 to obtain the same output below //your code
}
#include<iostream> bool isEmpty(){ }
using namespace std; if(top==-1){ void pop(){
const int SIZE=3; return true; if(isEmpty()){
int stack[SIZE]; } cout<<"\n\tStack underflow! can't remove";
int top=-1; return false; }else{
} //your code
bool isEmpty(); bool isFull(){ }
bool isFull(); if(top==SIZE-1){ }
void push(int item); return true; void display(){
void pop(); } cout<<"\n";
return false; cout<<"Display data in stack from top: ";
void display();
}
Part 2 if(!isEmpty()){
int main(){ //your code
push(2); }else{
push(5); cout<<" Stack is empty\n";
push(7); }
push(1); } Part 3
display();
pop();
pop();
pop();
pop();
display(); 17
}
Part 1 Expected Output
Example 1: SOLUTION
❑ Stack as Array void pop(){
if(isEmpty()){
cout<<"\n\tStack underflow! can't remove";
▪ Suppose we have program as follow
#include<iostream>
}else{
cout<<"\n\t"<<stack[top]<<" is removed from
using namespace std; bool isEmpty(){ stack";
const int SIZE=3; if(top==-1){ stack[top]=0;
int stack[SIZE]; return true; top=top-1;
int top=-1; } }
return false; }
bool isEmpty(); } int peek(){
bool isFull(); bool isFull(){ if(isEmpty()){
void push(int item); if(top==SIZE-1){ cout<<"\n\tStack is empty\n";
void pop(); return true; }else{
int peek(); } return stack[top];
void display(); return false; }
} }
int main(){ void push(int item){ void display(){
push(2); if(isFull()){ cout<<"\n";
push(5); cout<<"\n\tStack overflow! cout<<"Display data in stack from top: ";
push(7); can't add"; if(!isEmpty()){
push(1); }else{ for(int i=top; i>=0; i--){
display(); top=top+1; cout<<stack[i]<<" ";
pop(); stack[top]=item; }
pop(); cout<<"\n\t"<<item<<" is }else{
pop(); added to stack"; cout<<" Stack is empty\n";
pop(); } }
display(); } Part 2
//cout<<"\n"; Part 3
} Part 1 } 18
Queue
❑ Implementation
➢ ----
19
Attendance record
• Attendance submit:
forms.gle/J3XzFbw3cMe1uBrf6
• Student review & QA: 3:10 – 3:40pm
• Quiz about Queue: 3:45 – 4:00pm (on Moodle)
• Stack lecture 20
