CS3334 Data Structures

Lec-2 Stacks
Objective

• Stack Abstract Data Type

• Sequential Allocation
• Linked Allocation
• Applications
Stack
• Stack is a list with the restriction that insertions and
deletions (usually all the accesses) can only be
performed at one end of the list
• Also known as: Last-in-first-out (LIFO) list
ADT of Stack
Value:
A sequence of items that belong to some data type ITEM_TYPE
Operations for a stack s:
1. Boolean IsEmpty()
Postcondition: If the stack is empty, return true, otherwise return false
2. Boolean IsFull()
Postcondition: If the stack is full, return true, otherwise return false
3. ITEM_TYPE Pop() /*take away the top one and return its value*/
Precondition: s is not empty
Postcondition: The top item in s is removed from the sequence and returned
4. ITEM_TYPE top() /*return the top item’s value*/
Precondition: s is not empty
Postcondition: The value of the top item in s is returned
5. Void Push(ITEM_TYPE e) /*add one item on top of the stack*/
Precondition: s is ______
not full
Postcondition: e is added to the sequence as the top one
Array Implementation of Stack
// MyStack.h // [Link]
#include “stdlib.h”
{ #include “MyStack.h”
public class MyStack MyStack::MyStack(int size)
{ {
public: data=new int[size];
MyStack( int ); top=-1;
bool IsEmpty(); MAXSize=size;
bool IsFull(); }
void push(int ); bool MyStack::IsEmpty()
int pop(); {
int top(); return (top==-1);
private: }
int* data; bool MyStack::IsFull()
int top; {
int MAXSize; return (top==MAXSize-1);
}; }
}
Array Implementation of Stack
Top
Item E
// [Link]
#include “MyStack.h” Item D
int main() Item C
{ Item B
MyStack* TS=new MyStack(100); Bottom Item A
}

In computer memory, Suppose L0 Slot #0: Item A Bottom of stack:

• Size of each item is k. L0+k Slot #1: Item B Always at first
L0+2k Slot #2: Item C slot (slot#0)
• Base address is L0. L0+3k Slot #3: Item D
L0+4k Slot #4: Item E
L0+5k Slot #5: Not yet filled Top of stack
(slot#4)
L0+6k Slot #6: Not yet filled
… …
L0+99k Slot #99: Not yet filled
Array Implementation of Stack

When the stack is empty, When the stack is FULL,

Top of stack Slot #0: filled

is undefined
Slot #1: filled
Slot #2: filled
Slot #0: Not yet filled
Slot #3: filled
Slot #1: Not yet filled
Slot #4: filled
Slot #2: Not yet filled
…
Slot #3: Not yet filled
Slot #99: filled
Slot #4: Not yet filled
…
Slot #99: Not yet filled Top of stack
is at slot #99
ie. Slot #(MAXSTACKSIZE-1)
Array Implementation of Stack: push
... To “push” an item onto the stack
private:
int* data; • Check whether not yet full.
int top; • Increase the top indicator (slot number)
int MAXSize;
of the stack.
void MyStack::push(int x)
{ • Copy the item to the top position
if (!IsFull() ) immediately.
{
top=top+1; Slot #0: filled
data[top] = x; Slot #1: filled
} Slot #2: filled
else
…. to be
Slot #3: not yetfilled
filled
} Slot #4: not yet filled Top of stack:
slot #2 => 3
…
Slot #99: not yet filled
Array Implementation of Stack: pop
... To “pop” an item from the stack (to take away
private: the top one and return its value)
int* data; • Check whether it is empty.
int top;
int MAXSize;
• Save the value of item at the top position
(to return it later)
• Decrease the top indicator (slot #)
int MyStack::pop( ) • Return the saved value.
{ int rtn_value;
if (!IsEmpty())
• No need to clear any slot.
{
rtn_value=data[top];
Slot #0: filled
top=top-1;
return rtn_value; Slot #1: filled
} Slot #2: filled
else to be popped
Slot #3: filled
Top of stack:
… Slot #4: not yet filled slot #3 => 2
} …
Slot #99: not yet filled
Array Implementation of Stack: top

... To return the value of an item from the

private: stack (the top item)
int* data; • Check whether it is empty.
int top; • Return the value of the item at the
int MAXSize; top position.
int MyStack::top( )
{
if (!IsEmpty()) Slot #0: filled
{ Slot #1: filled
return (data[top]); Slot #2: filled
} Slot #3: filled
to be returned
else Slot #4: not yet filled Top of stack: slot #3
… … (no change)
}
Slot #99: not yet filled
Exercise 1

Suppose an intermixed sequence of stack push and pop

operations are performed. The pushes push into the stack the
integers 0 through 9 in order; popped values are printed in the
order they are popped.
Which of the below sequences could occur as the printed
output?

a. 1 2 3 0 6 5 4 7 8 9
b. 2 3 4 5 6 7 8 9 0 1
c. 6 7 8 9 5 4 3 2 1 0
d. 7 8 9 6 5 4 2 3 1 0
Stacks: Use Dynamic Array

• How to choose the size of array data[]?

Ø As we insert more and more, eventually the array will be full

• Solution: Use a dynamic array

Ø Maintain capacity of data[]
Ø Double capacity when size=capacity (i.e. full)
Ø Half capacity when size £ capacity/4

• Question: What if we change capacity/4 to capacity/2 ?

ØE.g., initial cap is 4; I, I, I, I, I (expand; cap=8, size=5), D (shrink; cap=4,
size=4), I (expand; cap=8, size=5), D (shrink; cap=4, size=4), I (expand),
D (shrink), ….
(I means insertion; D means deletion)
Stacks: Another implementation
class Stack // An internal func. to support resizing of array
{ void Stack::realloc(int newCap) {
public: if (newCap < size) return;
Stack(int initCap=100); //oldarray “point to” data
Item *oldarray = data;
Stack(const Stack& rhs);
~Stack();
//create new space for data with size newCap
data = new Item[newCap];
void push(Item x); for (int i=0; i<size; i++)
void pop(Item& x); data[i] = oldarray[i];
cap = newCap;
private: delete [] oldarray;
void realloc(int newCap); }
Item* data;
int size; void Stack::push(Item x) {
if (size==cap) realloc(2*cap);
int cap;
array[size++]=x;
}; }
Stacks: Another implementation
void Stack::pop(Item& x)
{
// assume EmptyStack is a special value
if (size==0)
x=EmptyStack;
else
{
x=array[--size];
if (size <= cap/4)
realloc(cap/2);
}
}
Linked Implementation of Stack
Address T
Top Item E
Top of
Item D e Slot #4: Item E d stack
Item C (slot#4)
Item B
Bottom Item A
d Slot #3: Item D c

Stack can also be implemented

with linked list.
c Slot #2: Item C b
• Typically, a pointer points to the
top of the stack. (T)
b Slot #1: Item B a
• When the stack is empty, this Bottom of
pointer will be NULL. stack:
• Each slot is allocated only when a Always
Slot #0: Item A NULL
links to
it is needed to store an item. NULL
___
__
__
Linked Implementation of Stack
// MyStack.h // ListNode.h

#include “stdlib.h”
#include “stdlib.h” {
#include “ListNode.h” class ListNode
{ {
public:
class MyStack
ListNode( int );
{ ListNode( int, ListNode *);
public: ListNode *get_Next()
MyStack( ); {
Pop(); return next;
IsEmpty(); }
Push(int ); …
… private:
private: int data;
ListNode *Top; ListNode *next;
}; };
}
}
Linked Implementation of Stack: push
Push: To insert new information onto Address
the top of the stack p Slot #5: new item e
• Allocate memory for an auxiliary Top
pointer p
e Slot #4: Item E d
• Put new item into p->data
• p->next = T
d Slot #3: Item D c
• T=p

void MyStack::Push (int new_item) c Slot #2: Item C b

{
ListNode* p;
p=new ListNode(new_item, Top); b Slot #1: Item B a
// p->data = new_item;
// p->next = Top;
a Slot #0: Item A NULL
Top = p;
___
__
} __
 Linked Implementation of Stack: pop
Pop: To take away (and delete) the top item Top Item
and return its value. (value to be returned)
• Check whether the stack is empty. p
Address
• Store the value of the item so that we can f Slot #5: Top Item e
return it later.
Top
• Update the T pointer to point to the next item. e Slot #4: Item E d
• Return the value of the top item.
d Slot #3: Item D c
int MyStack::Pop () {
ListNode* p; //a pointer to point to original top node
int rtn_value; //the value of the item to be returned c Slot #2: Item C b
if (IsEmpty()) //check whether the stack is empty
{ //Exception handling } b Slot #1: Item B a
rtn_value=Top->data; //save the value to be returned
Top= Top->next; //update the T pointer a Slot #0: Item A NULL

return (rtn_value); //return the original top node value ___

__
} __
Anything missed?
Linked Implementation of Stack: pop

int MyStack::Pop () {
ListNode* p; //a pointer to point to original top node
int rtn_value; //the value of the item to be returned
if (IsEmpty()) //check whether the stack is empty
{ //Exception handling }
rtn_value=Top->data; //save the value to be returned
ListNode* temp = Top;
Top= Top->next; //update the T pointer
delete temp;
return (rtn_value); //return the original top node value
}
Exercise 1
find and remove the largest element in a stack.
// MyStack.h
#include “stdlib.h” int MyStack::find_and_Remove_max_val()
{ {
public class MyStack ...
{ }
public:
MyStack( int );
bool IsEmpty();
bool IsFull(); Input: a stack with 5 2 7 4 (4 is at top)
void push(int ); Output: a stack with 5 2 4 and return 7
int pop();
int top();
private:
int* data;
int top;
int MAXSize;
};
}
Exercise 2
Given string str, we need to print the reverse of individual words.
// MyStack.h
#include “stdlib.h” void reverseWords (string str)
{ {
public class MyStack stack st ([Link]());
{ ...
public: }
MyStack( int size);
bool IsEmpty();
bool IsFull(); Input: Hello World
void push(char); Output: olleH dlroW
char pop();
char top();
private:
char* data;
int top;
int MAXSize;
};
}
 Application1: Backtracking
Generating a maze
Start (0, 0) Using stacks (simplest way)
1. Start from the entrance cell
2. Randomly select an unvisited
neighbor cell of the stack top and
break the wall, then push the new
cell onto the stack
3. If all the neighbors are already
visited, then go back by popping
cells from the stack
4. Until the exit is reached

End (width-1, heigh-1)

Try by yourself on a 10*10 maze!

Constructing a 10*10 maze

• Variables needed
• An array memorizing whether a room is visited or not
• A stack
• An array memorizing whether a wall is broken or not

• How to solve a maze?

Application 2: Balancing Symbols
• When writing programs, we use
Ø () parentheses [] brackets {} braces
• A lack of one symbol may cause the compiler to emit a
hundred lines without identifying the real error
• Using stack to check the balance of symbols
Ø [ ( ) ] is correct while [ ( ] ) is incorrect

• Read the code until end of file

ØIf the character is an opening symbol: ( [ {, then push it
onto the stack
ØIf the character is a closing symbol: ) ] }, then pop one (if
the stack is not empty) from the stack to see whether it is
the correct correspondence
ØOutput error in other cases
Application 3 Evaluation of Postfix Expression
n Infix Expression Example: (A+B)*((C-D)*E+F)
We need to add “(“ and “)” in many cases.

n Postfix Expression Example: AB+CD-E*F+*

Each operator follows the two operands.
The order of the operators (left to right) determines
the actual order of operations in evaluating the
expression.

n Prefix expression Example : *+AB+*-CDEF

Each operator precedes the two operands.
 Application 3 Evaluation of Postfix Expression
6 2 + 3 1 - 4 * 7 + *
=8 3 1 - 4 * 7 + *
=8 2 4 * 7 + *
=8 8 7 + *
- * +
=8 15 * + *
1 4 7
= 120 2 3 2 2 8 8 15 15
6 8 8 8 8 8 8 8 8 120

The method:
n Scan the expression from left to right.
n For each symbol, if it is an operand, we store them for later operation (LIFO) push
n If the symbol is an operator, take out the latest 2 operands stored and compute
with the operator. pop pop
Treat the operation result as a new operand and store it. push
n Finally, we can obtain the result as the only one operand stored. pop
Application 3 Evaluation of Postfix Expression
//check whether the parameter symbol is a digit
bool IsDigit(char symbol)
{
if (symbol >= '0' && symbol <= '9’) return true;
return false;
}
int Compute(char operator, int operand1, int operand2)
{
switch (operator)
{ case '+' : return (operand1 + operand2);
case '-' : return (operand1 - operand2);
case '*' : return (operand1 * operand2);
case '/' : return (operand1 / operand2);
}
}
Application 3 Evaluation of Postfix Expression
…
using namespace MyStack
BOOL IsDigit(char symbol) { .. }
int Compute(char operator, int operand1, int operand2) { .. }
void main()
{
int i, operand1, operand2, computed_value
String * exp;
wchar_t c;
//Input of expression: exp
Console::Write(S"Enter the expression (no space in-between): ");
exp=Console::ReadLine();
//Compute the expression
Stack *S=new Stack();
for (i=0; i<exp->GetLength(); i++)
{
c=exp->get_Chars(i);
if (IsDigit(c))
[Link]( (c-'0'));
else
{ operand2=[Link]();
operand1=[Link]();
computed_value=Compute(c,operand1,operand2);
[Link](computed_value);
}
}
//Output the answer
Console::Write(S”Answer: {0}”, [Link]());
}
Application 4 Infix expression->postfix expression

Define the precedence relation Operators priority no.

of some of the operators:
# 0
# is the special symbol to denote the ( 1
bottom of stack. + or - 2
* or / 3

When encountering an operator:

• While the stack is not empty and the precedence of the top of the stack is
greater than or equal to the precedence of the current operator:
o Pop operators from the stack and add them to the postfix expression.
• Push the current operator onto the stack.

Example:(1+3)*((2-4)+5*7) => 1 3 + 2 4 - 5 7 * + *
 Application 4 Infix expression->postfix expression

Define the precedence relation Operators priority no.

of some of the operators:
# 0
# is the special symbol to denote the ( 1
bottom of stack. + or - 2
* or / 3

Example:(1+3)*((2-4)+5*7) => 1 3 + 2 4 - 5 7 * + *
1 3 + 2 4 - 5 7 * + *

4 ) 7 )
2 5 *
- - Ö * * Ö
3 ) ( ( ( x + + + + Ö
1 + + Ö ( ( ( ( ( ( ( x
( ( ( x * * * * * * * * Ö
# # # # # # # # # # #
Application 5: Identify the boundary of lines

• Given several lines, identify which parts of the lines can been
seen if you look from the above
Application 5: Identify the boundary of lines

• Algorithm:
Sort the lines according to their slopes l1,l2,…ln
Construct a stack and push the first two lines l1,l2 into it
For k=3 to n
{
Pop two lines from the stack and store them in A and B (A stores the first popped line)
While the intersection point of A and B is below lk
{
A=B
Pop a line from the stack and store it in B
}
Push B, A, lk into the stack in this order
}
Identify the boundary of lines
l1

l2

l3

A l23
l4 B l21
• Example:

Processing l3 Processing l4
l3 l4
l2 l2 l2
l1 l1 l1 l1
# # # # # #
Note:
When we use a stack ADT, we should not do anything specific to the internal data
structure. All accesses to the stacks must be made through stack member
functions.
Only the member functions may access the internal data of stacks directly.
Do not access the internal data of stacks in other parts of the programs.

(This note applies also to queue ADT that will be taught in next topic)
Learning Objectives
1. Explain the concepts of Stack
2. Understand the three functions of Stack
3. Able to use the three functions to generate and solve a maze
4. Fully understand how stack is used in Application 2

D:1; C:1,2; B:1,2,3; A:1,2,3,4

Exercise 1

Given a balanced expression that can contain opening and closing

parenthesis, check if it contains any duplicate parenthesis or not.

Examples:
Input: ((x+y))+z
Output: true

Input: (x+y) bool findDuplicateparenthesis(string str)

Output: false {
. . . // using stack
}
Exercise 1 bool findDuplicateparenthesis(string str)
{
stack<char> Stack;
for (char ch : str) {
if (ch == ')’) {
char top = [Link]();
int elementsInside = 0;
while (top != '(') {
elementsInside++;
top = Stack. pop();
}
if(elementsInside < 1)
return true;
}
else
[Link](ch);
}
return false;
}
Exercise 2

Given a non-negative integer num represented as a string,

remove k digits from the number so that the new number is the
smallest possible.
Examples:
Input: num = "1432219", k = 3
Output: "1219”

Input: num = "10200", k = 1

Output: "200" NOT just finding the max
1324 (remove 4) -> 132
1324 (remove 3) -> 124
int removeKdigits(string num, int k)
{ From MSB to LSB
. . . // using stack check it is worthwhile to delete
}
 int removeKdigits(string num, int k) {

Exercise 2 if ([Link]() == k)
return "0";

stack <char> S;
int n = k, idx = 0;
for (int idx = 0; idx < [Link](); idx++ ) { // From MSB to LSB
int curBit = num[idx] - '0';
while(n > 0 && ![Link]() && ([Link]()-'0') > curBit) {
n--;
[Link](); // remove this bit
}
[Link](curBit);
}

while(n>0) {
[Link]();
n--;
}

// transform the contents in stack into the final result

string result;
while (![Link]())
result += [Link]();
reverse([Link](), [Link]());
int number = stringToDigit(result);
return number;
}