Transcript Introduction to Data Structure

Data Structure: Chapter 3
Min Chen
School of Computer Science and Engineering
Seoul National University


Definition of Stacks
Operators for Stacks
 Push
 Pop
 Peek

Applications for Stacks
 Reversing a Word
 Delimiter Matching

Array-based Stack

A stack is a Last-In-First-Out(LIFO) abstract data
structure.
Top
Bottom

In a stack, access to a element is restricted: only
the top item can be read or removed at one time
Fig1. Bullets Clip: A Typical Stack

You can only eat the top apple first
Fig.2 An Apple Stack

Push: insert a data item to the top of the
stack
Item 6
Item 5
Top
Item 4
Item 3
Item 2
Item 1
Fig2. Push Operator in Stacks
Bottom

Pop: get a data item on the top of the stack
and remove it from the stack
Item 6
Program
Top
Item 5
Item 4
Item 3
Item 2
Item 1
Fig2. Pop Operator in Stacks
Bottom

Peek: get a data item on the top of the stack
and do not remove it from the stack
Item 6
Program
Top
Item 5
Item 4
Item 3
Item 2
Item 1
Fig2. Pop Operator in Stacks
Bottom


Stacks are typically small, temporal data
structures.
Can be calculated by the top pointer and the
bottom pointer

Reversing a Word
 “Avatar” -> “ratavA”
r
a
t
a
v
Output
A
Input
Top
Bottom

In processing programs and working with
computer languages there are many
instances when symbols must be balanced
{},[],()
A stack is useful for checking symbol balance.
When a closing symbol is found it must match the
most recent opening symbol of the same type.
Algorithm?
11


Make an empty stack
read symbols until end of file
 if the symbol is an opening symbol push it onto the
stack
 if it is a closing symbol do the following
▪ pop the stack. If the symbol popped does not match the
closing symbol report an error

At the end of the file if the stack is not empty
report an error
12

Delimiter Matching
(9+1)*(6+2)
= 80
Stack:
)
2
+)
(9+1)=10
1
6
(6+2)=8
10*8=80
+
8(
9*
10
80
(

Items can be both pushed and popped from a
stack in constant O(1) time
 We have no choices but just operate on the
particular item (top item)

Very Quick

How is stack implemented?
 Initiate an array
 Use variables to indentify the position of the top
of the stack
A[10]
top=-1
top=0
top=1
3
1
8
Push(3)
Pop()
Push(1)
Push(8)
Pop()
A simple way of
implementing the
Stack uses an array
• We add elements
from left to right
• A variable keeps
track of the index of
the top element
•
Algorithm size()
return t + 1
Algorithm pop()
if isEmpty() then
throw EmptyStackException
else
t  t  1
return S[t + 1]
…
S
0
1
2
Elementary Data Structures
t
16
•
•
The array storing the
stack elements may
become full
A push operation will
then throw a
FullStackException
 Limitation of the array-
Algorithm push(o)
if t = S.length  1 then
throw FullStackException
else
t  t + 1
S[t]  o
based implementation
 Not intrinsic to the Stack
…
S
0
1
2
Elementary Data Structures
t
17
•
•
In a push operation, when the
array is full, instead of throwing
an exception, we can replace the
array with a larger one
How large should the new array
be?
• incremental strategy: increase the
size by a constant c
• doubling strategy: double the size
Elementary Data Structures
Algorithm push(o)
if t = S.length  1
then
A  new array of
size …
for i  0 to t do
A[i]  S[i]
S  A
t  t + 1
S[t]  o
18


Definition of Stacks
Operators for Stacks
 Push
 Pop
 Peek

Applications for Stacks
 Reversing a Word
 Delimiter Matching

Array-based Stack