Stack
NGĂN XẾP
Stack in Java
Object
Abstract Collection
AbstractList
AbstractSequentialList
LinkedList
ArrayList
Vector
Stack
What is Stack ?
Input Output
Harry Potter
XMen
Spider Men
Definition of Stack
Items are added to and removed from the top of the pile.
Consider the pile of papers on your desk. Suppose you add
papers only to the top of the pile or remove them only from
the top of the pile. At any point in time, the only paper that is
visible is the one on top. What you have is a stack.
stack is a last-in, first-out or LIFO data structure
Application of Stack
Example 6.1: Internet Web browsers store the addresses of recently
visited sites on a stack. Each time a user visits a new site, that site’s
address is “pushed” onto the stack of addresses. The browser then
allows the user to “pop” back to previously visited sites using the
“back” button.
Example 6.2: Text editors usually provide an “undo” mechanism that
cancels recent editing operations and reverts to former states of a
document. This undo operation can be accomplished by keeping text
changes in a stack.
How to build Stack
Array ?
Linked List?
Implement Stack with
Singly Linked List
Implement Stack with
Array
Using Stack in Java
Create a Stack
import [Link];
….
Stack s = new Stack();
Put element in Stack
[Link](“learn Stack”);
[Link](“practise Stack”);
Remove top element in Stack
[Link]();
Methods of Stack
The Stack interface extends the Container
interface defined in Program . Hence, it
comprises all of the methods inherited from
Container plus the three methods peek(),
push(), and pop().
Meaning of methods:
✓ empty() return true if no element in stack.
✓ peek() , firstElement() return top element of stack
but not delete top element in stack.
✓ pop() return top element of stack and delete top
element in stack
✓ push(Object obj), add(Object obj) push the
element in stack
✓ elements() return iterator of elements
✓ size() return the size of stack
Methods of Stack (cont)
✓ search(Object obj) return index of element in stack
….
3 c
2 b
1 a [Link](“a”) →1
✓ add (int position, Object obj)
c 3
c 2 b 2
b 1 a 1
d a d 0
0
[Link](0,“d”)
Methods of Stack (cont)
remove(int position) remove an object at input
position.
remove(Object obj) remove an object in Stack
that equal input object.
removeAllElements() return a empty Stack
Try to test
Stack<Integer> test = new Stack<>();
[Link](2);
[Link](4);
[Link](5);
[Link](7);
[Link](test);
[Link]();
[Link](test);
[Link]();
[Link](test);
Predict the result of code
Stack<Integer> test1 = new Stack<>();
[Link](0);
[Link]();
[Link](1);
[Link](-1);
[Link]();
[Link](2);
[Link](test1);
Application of Stack
Ha Noi tower game
A B C
How to move 3 disks from A column to C column with minimum of steps?
How to implement Stack
Solution
A B C
Application of Stack
How to program this game?
1. Each column is a Stack
2. Using push, pop, peek to add and remove disk
Small exercises
1. Reverse an array by using Stack (pg 234)
Small exercises
1. Matching Parentheses and HTML Tags(pg 234)
(Check each opening symbol must match its corresponding closing symbol.)
Symbol:
Parentheses: “(” and “)”
Braces: “{” and “}”
Brackets: “[” and “]”
An Algorithm for Matching Delimiters
We can use a stack to perform this task with a single left-to-right scan of the original
string.
Each time we encounter an opening symbol, we push that symbol onto the stack, and each
time we encounter a closing symbol, we pop a symbol from the stack (assuming it is not
empty) and check that these two symbols form a valid pair.
If we reach the end of the expression and the stack is empty, then the original expression
was properly matched. Otherwise, there must be an opening delimiter on the stack without
a matching symbol. If the length of the original expression is n, the algorithm will make at
most n calls to push and n calls to pop
Small exercises
2. Matching Parentheses(pg 234)
(Check each opening symbol must match its corresponding closing symbol.)
Symbol:
Parentheses: “(” and “)”
Braces: “{” and “}”
Brackets: “[” and “]”
An Algorithm for Matching Delimiters
We can use a stack to perform this task with a single left-to-right scan of the original
string.
Each time we encounter an opening symbol, we push that symbol onto the stack, and each
time we encounter a closing symbol, we pop a symbol from the stack (assuming it is not
empty) and check that these two symbols form a valid pair.
If we reach the end of the expression and the stack is empty, then the original expression
was properly matched. Otherwise, there must be an opening delimiter on the stack without
a matching symbol. If the length of the original expression is n, the algorithm will make at
most n calls to push and n calls to pop
Small exercises
Small exercises
3. Matching Tags in a Markup Language(pg 236)
Small exercises
3. Matching Tags in a Markup Language(pg 236)
• We make a left-to-right pass through the raw string, using index j to trackour progress.
• The indexOf method of the String class, which optionally accepts a starting index as a
second parameter, locates the '<' and '>' characters that define the tags.
• Method substring, also of the String class, returns the substring starting at a given
index and optionally ending right before another given index.
Queue
HÀNG ĐỢI
Queues
A queue is a pile in which items are added an one
end and removed from the other. In this respect, a
queue is like the line of customers waiting to be
served by a bank teller. As customers arrive, they join
the end of the queue while the teller serves the
customer at the head of the queue. As a result, a
queue is used when a sequence of activities must be
done on a first-come, first-served basis.
a queue is a first-in, first-out or FIFO data structure.
Queues (cont)
enqueue(e): Adds element e to the back of queue.
dequeue( ): Removes and returns the first element from the queue
(or null if the queue is empty).
first( ): Returns the first element of the queue, without removing it
(or null if the queue is empty).
size( ): Returns the number of elements in the queue.
isEmpty( ): Returns a boolean indicating whether the queue is
empty.
Applications of Queue
Implementing a Queue with an
Array (pg 261)
Implementing a Queue with a
Singly Linked List (pg 263)
Implementing a Queue with a
Circularly Linked List (pg
264)
Queue in Java
The [Link] Interface in
Java
Using Queue in Java
Queue<Integer> q = new LinkedList<>();
[Link](9);
[Link](1);
[Link](3);
[Link](q);
[Link]();
[Link](q);
[Link]();
[Link](q);
[Link]();
[Link](q);
Double-Ended
Queues
DEQUE
READING BOOK PG 266