CS3334 Data Structures

Lec-2 Stacks
Lecturers & Instructors
• Lecture Instructor:
• Dr. Junqiao QIU, Assist. Prof. at CS, YEUNG Y7708
• Email: junqiqiu@[Link]
• Office Hours: Friday 14:00 - 15:00 or by appointment

• Lab/Tutorial Instructor:
• R11:00 - 11:50 QIU Junqiao
• W13:00 - 13:50 LI Xinyao
• T12:00 - 12:50 HUANG Jiacheng
• F12:00 - 12:50 HUANG Lianming

• Post your questions on Canvas for quick response

• Canvas => Discussions
Assessment Pattern

Bonus: Maximum 3 points to coursework

Quiz (written & programming based) (15%)

Assignment Qs (OJ+Proj) (20+5%)

Exam (60%)

Compulsory: coursework >= 40

Compulsory: exam mark >= 30
Assignment questions

• Total 16 questions (20%):

• Mapping number of questions x in the assignment to the

assignment score
f(x)= 4 + 7x if x<8
f(x)= 12 + 6x if 8<=x<12
f(x)= 36 + 4x if 12<=x<=16
• The last minute is the worst minute!
• [Link]

• One Project (to be released in around Week 8)

• Must pursue your studies with academic honesty
• Copy-paste from AI tool is NOT ALLOWED
Generating and Solving Maze
Review about Linked Lists
• Abstract Data Types
• Pointers and References
• Singly Linked List
• Circular Lists
• Doubly Linked Lists
• Applications
Review: Abstract Data Type
/*Octopus.h*/ Some advanced data types are very useful.
class Octopus
People tend to create modules that group
{ together the data types and the functions for
private: handling these data types. (~ Modular Design)
float value;
Person p; They form very useful toolkits for programmers.
Credit_Card_No n;
float Rewards;
…
When one search for a “tool”, he/she
looks at what the tools can do. i.e.
public:
He/she looks at the abstract data
void Increase_value (..);
types (ADT).
void Increase_credit(..);
void Pay_Transaction(..); He/She needs not know how the
bool Identity_Verify(..); tools have been implemented.
void accumulate(); menu

…
};
 Review: Abstract Data Type

The set ADT consists of 2 parts: Value:

1. Definition of values involves A set of elements
• definition Condition: elements are distinct.
• condition (optional) Operations for Set *s:
1. void Add(ELEMENT e)
2. Definition of operations postcondition: e will be added to *s
each operation involves 2. void Remove(ELEMENT e)
precondition: e exists in *s
• header postcondition: e will be removed from *s
• precondition (optional) 3. int Size( )
• postcondition postcondition: the no. of elements in *s will be returned.
…
 Review: Passing Arguments
Pass by Value Pass by Pointer Pass by Reference
int SquareByV(int a) void SquareByP(int *cptr) void SquareByR(int &cRef)
{ { {
Return a * a;
*cptr *= *cptr; cRef *=cRef;
}
} }
int main()
int main() int main()
{
{ {
int x =2;
SquareByV(x); int y =2; int z =2;
} SquareByP(&y); SquareByR(z);
} }

int * p : (int *) p
*p: dereference (the data pointed by p)
*: multiplication
&a: the address of a
A[]: array variable is a pointer
Review: List

A Linear List (or a list, for short)

• is a sequence of n nodes {x1, x2, .., xn} whose essential structural
properties involve only the relative positions between items as
they appear in a line.

• can be implemented as
• Arrays: statically allocated or dynamically allocated
• Linked Lists: dynamically allocated
• A list can be sorted or unsorted.
Review: Singly Linked List
• Each item in the list is a node

data next
• Linear Structure

first a0 a1 a2 a3 a4 Ù

• Node can be stored in memory consecutively /or not (logical

order and physical order may be different)

a0 a2 a1

first
Review: Singly Linked List
// List.h
#include <string>
using namespace std; class List
{
class ListNode public:
{ List( String );
public: List();
ListNode( int ); //various member functions
ListNode( int, ListNode *);
private:
ListNode *get_Next()
{ ListNode *first;
return next; string name;
} }
…
private:
int data;
ListNode *next;
};
Review: Singly Linked List

• Operations:
• InsertNode: insert a new node into a list
• RemoveNode: remove a node from a list
• SearchNode: search a node in a list
• CountNodes: compute the length of a list
• PrintContent: print the content of a list
• …
• All the variables are defined to be “int”, how about when we want to use
“double”?
• Write a different class of list for “double”? Or…
Review: Search for a node
Use a pointer p to traverse the list
• If found: return the pointer to the node,
• otherwise: return NULL.

//[Link]
ListNode* List::Search(int data)
{
ListNode *p=first;
while (p!=NULL)
p
{
if (p->getData()==data)
return p; first ……
p=p->getNext();
}
return NULL;
}
Review: Insert a node
• Data comes one by one, and we want to keep them sorted, how?
• Do search to locate the position
• Insert the new node
• Why is this correct?

• We will encounter three cases of insert position

• Insert before the first node
• Insert in the middle
• Insert at the end of the list
• One important case missing: Empty List
Void List::InsertNode(ListNode* newnode)
{
if (first==NULL)
first=newnode;
else if (newnode->getData() < first->getData() )
…
}
Review: Insert a node: Case 1

• Insert before the first node

• newnode->next=first
• first=newnode

newnode newnode
first

first …… ……

before insert after insert

Review: Insert a node: Case 2 & 3

• Insert in the middle or at the end of the list

• newnode->next = p->next
• p->next = newnode
Review: Insert a node: Complete Solution
Void List::InsertNode(ListNode* newnode)
{
if (first == NULL)
first = newnode;
else if (newnode->data < first->data) {
newnode->next = first;
first = newnode;
}
else {
ListNode* p=first;
while(p->next != NULL && newnode->data > p->next->data)
p = p->next;
//p will stop at the last node or at the node
//after which we should insert the new node
//note that p->next might be NULL here
newnode->next = p->next;
p->next = newnode;
}
}
Review: Remove a node

• Some data become useless and we want to remove them, how?

• Search the useless node by data value
• Remove this node
• We will encounter two cases
• Removing a node at the beginning of the list
• Removing a node not at the beginning of the list
Review: Remove a node: Case 1

• Remove a node at the beginning of the list

ØCurrent status: the node pointed by “first” is unwanted
ØThe action we need: q=first; first=q->next

first …… before remove

…… after remove
first
Review: Remove a node: Case 2
• Remove a node not at the beginning of the list
Current status: q == p->next and the node pointed by q is unwanted
The action we need: p->next=q->next

p q

…… …… before remove

p q

…… …… after remove
Review: Dummy Header Node
• So many cases with Insert and Remove operations
• We want simpler implementations!
• What are the special cases? Why are they different?
• One way to simplify:
• keep an extra node at the front of the list

first ……

Dummy Header node Data nodes

We don’t care about the The value of these nodes
value of this node. are our data
Review: Dummy Header Node
• One case remaining for insert

newnode newnode

p p

…… …… ……

before insert after insert

 Review: Insert a node: With Dummy Header
Void List::InsertNode(ListNode* newnode)
{
if (first==NULL)
first=newnode;
else if (newnode->data<first->data) {
newnode->next=first;
first=newnode;
}
else {
ListNode* p=first;
while(p->next!=NULL && newnode->data>p->next->data)
p=p->next;
//p will stop at the last node or at the node
//after which we should insert the new node
//note that p->next might be NULL here
newnode->next=p->next;
p->next=newnode;
}
}
Review: Dummy Header Node
• One case remaining for remove

before remove
p q

…… ……

p q

…… ……

after remove
Review: Remove a node: With Dummy
Header

Void List::RemoveNode(ListNode* q)
{
//remove at the beginning of a list
if (q==first)
first=first->next;
else
//remove not at the beginning
{
ListNode* p=first;
while(p->next!=q)
p=p->next;
p->next=q->next;
}
}
Review: Circular Lists

• Suppose we are at the node a4 and want to reach a1, how?

first a0 a1 a2 a3 a4 Ù

• If one extra link is allowed:

first a0 a1 a2 a3 a4
Review: Circular Lists

• Dummy header node can also be added to make the implementation

easier

first a0 a1 a2 a3

Dummy Header node

We don’t care about the
value of this node.
first
Review: Doubly Linked List
• Problem with singly linked list
ØWhen at a4, we want to get a3
ØWhen deleting node a3, we need to know the address of node a2
ØWhen at a4, it is difficult to insert between a3 and a4

first a0 a1 a2 a3 a4 Ù

• If allowed to use more memory spaces, what to do?

Lnext Data Rnext

Review: Doubly Linked List
• To insert a node after an existing node pointed by p

p newnode

p newnode
DoublyLinkedList::InsertNode(ListNode *p, ListNode *newnode)
{
newnode->Lnext=p;
newnode->Rnext=p->Rnext;
if(p->Rnext!=NULL) p->Rnext->Lnext=newnode;
p->Rnext=newnode;
}
Review: Doubly Linked List

• To delete a node, we only need to know a pointer pointing to the node

DoublyLinkedList::RemoveNode(ListNode *p)
{
if(p->Lnext!=NULL) p->Lnext->Rnext=p->Rnext;
if(p->Rnext!=NULL) p->Rnext->Lnext=p->Lnext;
}
Review: Advantages / Disadvantages of
Linked List
Linked allocation: Stores data as individual units and link them by pointers.
Advantages of linked allocation:
• Efficient use of memory
Facilitates data sharing
No need to pre-allocate a maximum size of required memory
No vacant space left

• Easy manipulation To delete or insert an item

To join 2 lists together
To break one list into two lists
• Variations Variable number of variable-size lists
Multi-dimensional lists
(array of linked lists, linked list of linked lists, etc.)
• Simple sequential operations (e.g. searching, updating) are fast
Disadvantages:
• Take up additional memory space for the links
• Accessing random parts of the list is slow. (need to walk sequentially)
 Past Exercise
Swap two adjacent elements by adjusting only the links (and not
the data) using singly linked lists
struct ListNode {
int data;
ListNode * next;
};

void swapAdjacentSingly(ListNode*& first) {

...
}

first 1 2 3 4 …… before

first 2 1 4 3 …… after
 Exercise 1
Given a singly linked list, find the middle of the linked list.
• For example, if the given linked list is 1->2->3->4->5, then the output
should be 3.
• If there are even nodes, then there would be two middle nodes, we need
to print the second middle element. For example, if the given linked list is
1->2->3->4->5->6, then the output should be 4.

class ListNode class List

{ int List::returnMiddle()
{
public:
ListNode( int ); public: {
ListNode( int, ListNode *); List( String ); // Your codes
ListNode *get_Next(); List(); ...
int get_Data(); }
private: int returnMiddle();
int data; private:
ListNode *next; ListNode *first;
}; string name;
}
Exercise 1
class ListNode
void List::returnMiddle() {
{ public:
ListNode( int );
if (first!=NULL) ListNode( int, ListNode *);
{ ListNode *get_Next()
int len = 0; int get_Data();
ListNode *p=first; private:
while (p!=NULL) { int data;
ListNode *next;
p=p->getNext();
};
len++;
}
class List
ListNode * temp = first; {
public:
// traverse till we reached half of length List( String );
int midIdx = len / 2; List();
while (midIdx--) private:
temp = temp-> get_Next(); ListNode *first;
string name;
}
return temp->get_Data();
}
}
 Exercise 2
Given a pointer to the head node of a linked list, the task is to reverse the
linked list. We need to reverse the list by changing the links between nodes.
• E.g., Input: the following linked list 1->2->3->4->NULL
Output: Linked list should be changed to 4->3->2->1->NULL

class ListNode class List

{ {
public:
ListNode( int ); public:
ListNode( int, ListNode *); List( String ); void List::reverse()
ListNode *get_Next() List(); {
void set_Next(ListNode *); // Your codes
private:
void reverse();
...
int data; private:
ListNode *next; }
ListNode *first;
}; string name;
}
Exercise 2 class ListNode
{
void List::reverse () public:
{ ListNode( int );
// Initialize current, previous and next pointers ListNode( int, ListNode *);
Node* current = first; ListNode *get_Next();
void set_Next(ListNode *);
Node *prev = NULL, *next = NULL;
private:
int data;
while (current != NULL) { ListNode *next;
// Store next };
next = current->get_Next();
// Reverse current node's pointer
current->set_Next(prev); class List
// Move pointers one position ahead. {
prev = current; public:
current = next; List( String );
} List();
first = prev; void reverse();
} private:
ListNode *first;
string name;
}
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 full yet.
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?

(Leftmost is the first one to be printed out)
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; void Stack::push(Item x) {
int size; 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 Stack::find_and_Remove_max_val()
{ {
public class Stack ...
{ }
public:
Stack( 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 1 int find_and_Remove_max_val()
{
find and remove the if (isEmpty()) {
cout << "Stack is empty" << endl; return -1;
largest element in a stack. }

int maxElement = INT_MIN;

Stack temp;
while (!isEmpty()) {
int element = pop();
if (element > maxElement) {
maxElement = element;
}
[Link](element);
}

while (![Link]()) {
int element = [Link]();
if (element != maxElement)
push(element);
}
return maxElement;
}
Exercise 2
Given string str, we need to print the reverse of individual words.
// MyStack.h
#include “stdlib.h” void printReverseWords (string str)
{ {
public class Stack Stack st;
{ ...
public: }
Stack( 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;
};
}
 void printReverseWords (string str)
Exercise 2 {
Stack st;

Given string str, we need to print for (int i = 0; i < [Link](); ++i)
the reverse of individual words. {
if (str[i] != ' ')
[Link](str[i]);
else {
while ([Link]() = = false) {
cout << [Link]();
}
cout << " ";
}
}

// there may not be space after last word

while ([Link]() = = false) {
cout << [Link]();
}
}
Application1: Backtracking
Generating a maze
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

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 priority of the top of the stack is greater
than or equal to the priority 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 * * * * * * * * Ö
# # # # # # # # # # #
Exercise 1
Evaluating the following postfix expressions.

2 3 1 * + 9 –
 Exercise 2
Remove all duplicate adjacent characters from a string using Stack
// Stack.h
Example
#include “stdlib.h”
Input: str= “azxxzy”
{
Output: ay
public class Stack
{
Input: “aaccdd” public:
Output: Empty String
Stack(int size);
bool IsEmpty();
bool IsFull();
void push(char);
char pop();
string removeDup(string str1){ char top();
Stack st; private:
. . . // insert your codes here char* data;
} int top;
int MAXSize;
};
}
 string removeDup(string str1){

Exercise 2 Stack st;

int i = 0;
while (i < [Link]()) {
if ([Link]() || str1[i] != [Link]()) {
Remove all duplicate [Link](str1[i]);
adjacent characters from i++;
}
a string using Stack else {
[Link]();
i++;
}
}
if ([Link]())
return ("Empty String");
else
{
string short_string = "";
while (![Link]()) {
short_string = [Link]() +
short_string;
[Link]();
}
return (short_string);
}
}
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