DATA STRUCTURES &
ALGORITHMS
Chapter 4: Stacks
Le Van Vinh, PhD
Faculty of Information Technology
University of Technology and Education
Outline
I. Stack ADT
II. Implement Stack
III. Applications of Stack
IV. Excercises
Chapter 4 – Stacks 2 Lê Văn Vinh - CNTT - SPKT
A garage
Input gate Output gate
Chapter 4 – Stacks 3 Data structures & algorithms
A pile of CDs
Chapter 4 – Stacks 4 Lê Văn Vinh - CNTT - SPKT
I. Stack ADT
Stack is a list with insertions and deletions
permitted at one end, called the top of the
Stack.
Property
LIFO (last in – first out)
FILO (first in – last out)
Chapter 4 – Stacks 5 Lê Văn Vinh - CNTT - SPKT
I. Stack ADT
Operations
Initialize stack (InitStack)
Insert a new item into stack (Push)
Remove a item on the top of stack (Pop)
Get the information of the item on the top of stack
(Top)
Check whether stack is empty or not (IsEmptyStack)
Check whether stack is full or not (IsFullStack)
Chapter 4 – Stacks 6 Lê Văn Vinh - CNTT - SPKT
Outline
I. Stack ADT
II. Implement Stack
III. Applications of Stack
IV. Excercises
Chapter 4 – Stacks 7 Lê Văn Vinh - CNTT - SPKT
I. Stack ADT
Operations
Chapter 4 – Stacks 8 Lê Văn Vinh - CNTT - SPKT
II. Implement Stack
Using array data type (STACK)
Using pointer data type (LINKED STACK)
Chapter 4 – Stacks 9 Lê Văn Vinh - CNTT - SPKT
Outline
I. Stack ADT
II. Implement Stack
III. Applications of Stack
IV. Excercises
Chapter 4 – Stacks 10 Lê Văn Vinh - CNTT - SPKT
Outline
I. Stack ADT
II. Implement Stack
III. Applications of Stack
IV. Excercises
Chapter 4 – Stacks 11 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
Function calls
Simulation recursion
Reversing a list
Evaluating of arithmetic expressions
Chapter 4 – Stacks 12 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
Chapter 4 – Stacks 13 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
Simulation recursion
int Compute(int n)
{
if(n<3)
return 1;
return Compute(n-1) +
Compute(n-3);
}
Chapter 4 – Stacks 14 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
Simulation recursion
int Compute(int n)
{
STACK mS;
InitStack(mS);
Push(mS, n);
int kq=0;
while(IsEmptyStack(mS) != 1)
{
int v=Pop(mS);
if(v<3)
kq=kq + 1;
else
{
Push(mS, v-1);
Push(mS, v-3);
}
}
return kq;
}
Chapter 4 – Stacks 15 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
int Compute(int n)
{
if(n<3)
return 2;
return Compute(n-1) * Compute(n-3);
}
int Compute(int a, int b)
{
if(a<2 && b<3)
return 2;
return Compute(a-2, b-2) + Compute(a-3, b-3);
}
Chapter 4 – Stacks 16 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
Quick Sort
void QuickSort(int a[], int left, int right)
{
int i, j;
int x;
x = a[(left + right)/2];
i=left; j=right;
do{
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j)
{
HoanVi(a[i], a[j]);
i++; j--;
}
}while(i < j)
if(left < j) QuickSort(a, left, j);
if(i < right) QuickSort(a, i, right);
}
Chapter 4 – Stacks 17 Lê Văn Vinh - CNTT - SPKT
void QuickSort(int a[], int left, int right)
{
STACK mS;
InitStack(mS);
Push(mS, left);
Push(mS, right);
while(IsEmptyStack(mS) != 1)
{
int rr=Pop(mS);
int ll=Pop(mS);
int i, j;
int x;
x = a[(ll + rr)/2];
i=ll; j=rr;
do{
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j)
{
HoanVi(a[i], a[j]);
i++; j--;
}
}while(i < j)
if(ll< j){ Push(mS, ll); Push(mS, j)}
if(i < rr) { Push(mS, rr); Push(mS, i);}
}
}
Chapter 4 – Stacks 18 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
Evaluating of arithmetic expressions
Q=a*(b+c)-d^5
P=a, S=Ø P=a b c + *, S= Ø
P=a, S=* P=a b c + *, S=-
P=a, S=* ( P=a b c + * d, S=- ^
P=a b , S=* ( P=a b c + * d 5, S=- ^
P=a b, S=* ( + P=a b c + * d 5 ^, S=-
P=a b c, S=* ( + P=a b c + * d 5 ^ -
P=a b c +, S=* (
P=a b c +, S=*
Chapter 4 – Stacks 19 Lê Văn Vinh - CNTT - SPKT
[Link] of stack
Evaluating of arithmetic expressions
P=a b c + * d 5 ^ -
Push(a), Push(b), Push(c): S=a, b, c
Pop(b), Pop(c), bc=b+c, Push(bc): S=a, bc
Pop(bc), Pop(a), abc=bc*a, Push(abc): S=abc
Push(d), Push(5): S=abc, d, 5
Pop(5), Pop(d), d5=d^5, Push(d5), S=abc, d5
Pop(d5), Pop(abc): Kq=abc – d5
Chapter 4 – Stacks 20 Lê Văn Vinh - CNTT - SPKT