§ 1 The Stack ADT
1,ADT
1
2
3
4
5
6
65
6
5
A stack is a Last-In-First-Out (LIFO) list,that is,
an ordered list in which insertions and deletions
are made at the top only.
Objects,A finite ordered list with zero or more elements.
Operations:
Int StackEmpty( Stack S );
Int StackFull( Stack S );?
Stack InitStack( );
MakeEmpty( Stack S );
Push( ElementType X,Stack S );
ElementType GetTop( Stack S );
Pop( Stack S );
Note:A Pop (or GetTop) on
an empty stack is an error in
the stack ADT.
Push on a full stack is
an implementation error but
not an ADT error.
CHAPTER 4 Stacks and Queues
2,Implementations
Linked List Implementation
typedef int StackData;
typedef struct node {
StackData data; //结点
struct node *link; //链指针
} StackNode;
typedef struct {
StackNode *top; //栈顶指针
} LinkStack;
Basic operation of Linked List Implementation
Create
void InitStack ( LinkStack *S ) {
S->top = NULL;
}
Push
int Push ( LinkStack *S,StackData x ) {
StackNode *p = ( StackNode * ) malloc
( sizeof ( StackNode ) );
p->data = x; p->link = S->top;
S->top = p; return 1;
}
StackEmpty
int StackEmpty (LinkStack *S) {
return S->top == NULL;
}
Pop
int Pop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
StackNode * p = S->top;
S->top = p->link;
x = p->data;
free (p);
return 1;
}
GetTop
int GetTop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
x = S->top->data;
return 1;
}
MakeEmpty
int MakeEmpty ( LinkStack *S) {
While(S->top!=NULL){
StackNode * p = S->top;
S->top = S->top ->link;
free(p);
}
}
Array Implementation
#define STACK_INIT_SIZE 100；
#define STACKINCREMENT 10；
typedef char StackData;
typedef struct { //顺序栈定义
StackData *base; //栈底指针
StackData *top; //栈顶指针
int stacksize； //当前已分配的存储空间
} SeqStack；
Note,?The stack model must be well encapsulated,That is,no
part of your code,except for the stack routines,can
attempt to access the Array or TopOfStack variable.
Error check must be done before Push or Pop (Top).
Basic operation of Array Implementation
Create stack
void InitStack ( SeqStack *S) { //置空栈
S->base=( StackData *)malloc(STACK_INIT_SIZE *
sizeof(StackData));
if (!S->base) exit(OVERFLOW);
S->top = S->base ;
S->stacksize= STACK_INIT_SIZE ;
Return ok;
}
StackEmpty
int StackEmpty (SeqStack *S) {
if( S->top == S->base ) return 1 //判栈空,空则返回 1
else return 0; //否则返回 0
}
MakeEmpty
void MakeEmpty(Stack s)
{S->top == S->base ;}
Push
int Push (SeqStack *S,StackData x) {
//插入元素 x为新的栈顶元素
if ( StackFull (S) ){
S->base=( StackData *)malloc(S->base,
(S->stacksize+ STACKINCREMENT) *
sizeof(StackData));
if(! S->base)exit(overflow);
S->top= S->base+ S->stacksize;
S->stacksize+= STACKINCREMENT; //追加存储空间
}
*(S->top)=x;
（ S->top） ++;
Return ok
}
Pop
int pop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素退出到 x并返回 1
if ( StackEmpty(S) ) return 0;
--(S->top);
x = *(S->top);
return 1;
}
Gettop
int Gettop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素读到 x并返回 1
if ( StackEmpty(S) ) return 0;
(S->top)--;
x = *(S->top);
return 1;}
3,Applications
Balancing Symbols
Check if parenthesis ( ),brackets [ ],and braces { } are balanced.
Algorithm {
Make an empty stack S;
while (read in a character c) {
if (c is an opening symbol)
Push(c,S);
else if (c is a closing symbol) {
if (S is empty) { ERROR; exit; }
else { /* stack is okay */
if (Top(S) doesn’t match c) { ERROR,exit; }
else Pop(S);
} /* end else-stack is okay */
} /* end else-if-closing symbol */
} /* end while-loop */
if (S is not empty) ERROR;
}
T( N ) = O ( N )
where N is the length
of the expression.
This is an
on-line algorithm.
N = (N div d)× d + N mod d
Example,（ 1348)10 = (2504)8,the Computing
process is as follows：
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
Out
pu
t o
rder
Order
of
co
mpu
tat
ion
digital conversion
void conversion () {
InitStack(S);
scanf ("%d",N);
while (N) {
Push(S,N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d",e );
}
} // conversion
when users input a line of characters,line editor allows to input wrong
characters,and it can correct errors timely.
Create a input buffer to store a line of characters of users input,and then
store to data storage area line by line,Suppose?#‘ to backspace and?@‘ to
denote cancelling a line of input.
Assume that editor accept two lines of characters from the terminal,
whli##ilr#e（ s#*s)
outcha@putchar(*s=#++);
The editor should store：
while (*s)
putchar(*s++);
Line editor
Void LineEdit(){
InitStack(s);
ch=getchar();
while (ch != EOF) { //EOF为全文结束符
while (ch != EOF && ch != '\n') {
switch (ch) {
case '#',Pop(S,c); break;
case '@',ClearStack(S); break;
// 重置 S为空栈
default,Push(S,ch); break;
}
ch = getchar(); // 从终端接收下一个字符
}
Send the characters which is from base to top to
the processing data storage area;
ClearStack(S); // 重置 S为空栈
if (ch != EOF) ch = getchar();
}
DestroyStack(s);
}
Maze solving
Common method is exhaust algorithm
# # # # # # # # # #
# # $ $ $ # #
#? # $ $ $ # #
# $ $ # # #
#? # # # # #
# # # #
# # # #
# # # # #? # # #
# #
# # # # # # # # # #
The basic idea of maze solving
When the current position is feasible,
then store the path,go ahead;
When the current position is unfeasible,
then go back and change directions.
If all directions are unfeasible,delete the
current position from the path.
set the initial value of current position as entry position;
do｛
if the current position is feasible，
then｛ push the current position to stack；
if this position is exit position,the algorithm end；
else set the box east of current position as the new
current position.
｝
else {
………..
｝
｝ while (stack is not empty）；
If stack is not empty and the top position has other
directions not be exploited.
Then set the new current position,find the next
adjacent box of the top position along the clockwise
rotation;
If stack is not empty and all directions are unfeasible.
then｛
delete the top of stack； // 从路径中删去该通道块
if stack is not empty,then test the new top position,
until find an adjacent reachable box or stack is
empty;
｝
Postfix Evaluation
〖 Example〗 An infix expression,a? b? c? d? e
A prefix expression, a? b c? d e
A postfix expression,a b c d e
operand operatoroperator with the highest
precedence〖 Example〗 6 2? 3? 4 2 =? 8
top
Get token,6 ( operand )
top6
Get token,2 ( operand )
top2
Get token,? ( operator )
2?6 = 3top
top
3
Get token,3 ( operand )
3
Get token,? ( operator )
33? = 00
Get token,4 ( operand )
top4 Get token,2 ( operand )
top2
Get token,? ( operator )
24? = 8
8
Get token,? ( operator )
80? = 8
8 Pop,8
Reverse Polish notation
T( N ) = O ( N ),No need to know precedence rules.
Infix to Postfix Conversion
〖 Example〗 a? b? c? d =? a b c d?
Note:
The order of operands is the same in infix and postfix.
Operators with higher precedence appear before those with lower precedence.
Output:
top
Get token,a (operand)
a
Get token,? (plus)
top
Get token,b (operand)
b
Get token,? (times)
top?
Get token,c (operand)
c
Get token,? (minus)
top
Get token,d (operand)
d?
(
〖 Example〗 a? ( b? c )? d =? a b c d?
top
Output:
Get token,a (operand)
a
Get token,? (times)
top
Get token,( (lparen)
(?top(
Get token,b (operand)
b
Get token,? (plus)
top+
Get token,c (operand)
c
Get token,) (rparen)
top
Get token,? (divide)
Get token,d (operand)
d?
T( N ) = O ( N )
Solutions:
Never pop a ( from the stack except when processing a ),
Observe that when ( is not in the stack,its precedence is the highest; but
when it is in the stack,its precedence is the lowest,Define in-stack
precedence and incoming precedence for symbols,and each time use the
corresponding precedence for comparison,
Note,a – b – c will be converted to a b – c –,However,2^2^3 ( ) must be
converted to 2 2 3 ^ ^,not 2 2 ^ 3 ^ since exponentiation associates
right to left.322
Function Calls -- System Stack
Return Address
Stack Frame s p
Local Variables
Return Address
s p
s pOld Frame Pointer s p
f p
f p
f p
void PrintList ( List L )
{
if ( L != NULL ) {
PrintElement ( L->Element );
PrintList( L->next );
}
} /* a bad use of recursion */
tail recursion
void PrintList ( List L )
{
top,if ( L != NULL ) {
PrintElement ( L->Element );
L = L->next;
goto top; /* do NOT do this */
}
} /* compiler removes recursion */
Recursion can always be completely removed.
Non recursive programs are generally faster than
equivalent recursive programs.
However,recursive programs are in general
much simpler and easier to understand.
§ 2 The Queue ADT
1,ADT
A queue is a First-In-First-Out (FIFO) list,that is,an
ordered list in which insertions take place at one end
and deletions take place at the opposite end.
2
3
4
1
1
1
2
2
Objects,A finite ordered list with zero or more elements.
Operations:
int IsEmpty( Queue Q );
Queue CreateQueue( );
DisposeQueue( Queue Q );
MakeEmpty( Queue Q );
Enqueue( ElementType X,Queue Q );
ElementType Front( Queue Q );
Dequeue( Queue Q );
Job 3
2,Implementation of Queues
Array
struct QueueRecord {
int Capacity ; /* max size of queue */
int Front; /* the front pointer */
int Rear; /* the rear pointer */
int Size; /* Optional - the current size of queue */
ElementType *Array; /* array for queue elements */
} ;
〖 Example〗 Job Scheduling in an Operating System
Rear Front
Enqueue Job 1 Enqueue Job 2 Enqueue Job 3 Dequeue Job 1
Enqueue Job 4 Enqueue Job 5 Enqueue Job 6 Dequeue Job 2
Enqueue Job 7 Enqueue Job 8
Job 1 Job 2
Rear RearFront Rear
Job 4
Rear
Job 5
Rear
Job 6
Front Rear
Job 7
0 1 2 3 4 5 6
2,Implementation of Queues
Linked list
data next
front
rear
frontrea
r
x ^ x enqueue
frontrea
r
x ^ y ^ y dequeue
frontrear x ^^ y x dequeue
frontrear ^ empty^ frontrear NULL empty
Linked list queues‘ definition
typedef int QueueData;
typedef struct node {
QueueData data; //队列结点数据
struct node *link; //结点链指针
} QueueNode;
typedef struct {
QueueNode *rear,*front;
} LinkQueue;
Basic operation
Initial
void InitQueue ( LinkQueue *Q ) {
Q->rear = Q->front = NULL;
}
Empty
int QueueEmpty ( LinkQueue *Q ) {
return Q->front == NULL;
}
Get Front element
int GetFront ( LinkQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->front->data; return 1;
}
EnQueue
int EnQueue ( LinkQueue *Q,QueueData x ) {
QueueNode *p = ( QueueNode * ) malloc
( sizeof ( QueueNode ) );
p->data = x; p->link = NULL;
if ( Q->front == NULL )
//空,创建第一个结点
Q->front = Q->rear = p;
else Q->rear->link = p; //入队
Q->rear =p;
return 1;
}
DeQueue
int DeQueue ( LinkQueue *Q,QueueData &x) {
//删去队头结点，并返回队头元素的值
if ( QueueEmpty (Q) ) return 0; //判队空
QueueNode *p = Q->front;
x = p->data; //保存队头的值
Q->front= Q->front->link; //新队头
free (p);
return 1;
}
Are you kidding?
Of course I do!
Do you have
a better idea?
[ 0 ]
[ 1 ]
[ 2 ][ 3 ]
[ 4 ]
[ 5 ]
Enqueue Job 1
Enqueue Job 2
Enqueue Job 3
Dequeue Job 1
Enqueue Job 4
Enqueue Job 5
Enqueue Job 6
Enqueue Job 7
Job
1
Job
2
Job
3
Job
4
Job
5
Job
6
The queue
is full
Question:
Why is the queue
announced full
while there is
still a free
space left?
Circular Queue:
Rear
Front
Rear
Rear
Front
Rear
Rear Rear
Note,Adding a Size field can avoid wasting one empty space to
distinguish,full” from,empty”,Do you have any other
ideas?
2,Implementation of Circular Queue
Array
Front and rear pointer add1,use modular arithmetic
Front pointer add 1,front = (front+1) %maxsize;
Rear pointer add 1,rear = (rear+1) % maxsize;
Initial Queue,front = rear = 0;
Empty Queue‘s condition,front == rear;
Full Queue‘s condition,(rear+1) % maxsize == front;
0
1
23
4
5
6 7
Circular Queue
front
rear
Maxsize-1
Circular Queue‘s definition
#define MAXSIZE 100
Typedef struct{
QueueData *data;
int front;
int rear;
} SeqQueue
Basic operation of Circular Queue
Initial
void InitQueue ( SeqQueue *Q ) {
//构造空队列
Q->data=(QueueData *)malloc(MAXSIZE
*sizeof(QueueData));
If(! Q->data)exit(OVERFLOW);
Q->rear = Q->front = 0;
Return ok
}
QueueEmpty
int QueueEmpty ( SeqQueue *Q ) {
return Q->rear == Q->front;
}
QueueFull
int QueueFull ( SeqQueue *Q ) {
return (Q->rear+1) % QueueSize == Q->front;
}
EnQueue
int EnQueue ( SeqQueue *Q,QueueData x ) {
if ( QueueFull (Q) ) return 0;
Q->data[Q->rear] = x;
Q->rear = ( Q->rear+1) % MAXSIZE;
return 1;
}
DeQueue
int DeQueue ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[Q->front];
Q->front = ( Q->front+1) % MAXSIZE;
return 1;
}
GetFront
int GetFront ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[(Q->front+1) % MAXSIZE];
return 1;
}
1 1 i = 1
1 2 1 2
1 5 5 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
Queue application
—print the coefficient of the binomial (a + b)i expansion
Pascal‘s triangle(杨辉三角 )
Analyze the relation between the ith elements
and the (i+1)th elements
Conclusion,we can compute the next line
numbers from the above line numbers.
compute and store the next line
numbers from the above line numbers
void YANGVI ( int n ) {
Queue q; //队列初始化
q.MakeEmpty ( );
q.EnQueue (1); q.EnQueue (1);//预放入第一行的两个系数
int s = 0;
for ( int i=1; i<=n; i++ ) { //逐行处理
cout << endl;
q.EnQueue (0);
for ( int j=1; j<=i+2; j++ ) { //处理第 i行的 i+2个系数
int t = q.DeQueue ( );//读取系数
q.EnQueue ( s+t );//计算下一行系数，并进队列
s = t;
if ( j != i+2 ) cout << s <<? ‘;//打印一个系数，第 i+2个为 0
}
}
}
Def,If an object partly contains itself,or is defined
by itself,this object is recursive;
If a process calls itself directly or indirectly,
this process is a recursive process.
3 recursive conditions
A recursive definition
A recursive data structure
A recursive solution of the problem
§ 3 Recursion
A recursive definition
A recursive algorithm to solve factorial function:
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
Eg1,Factorial function
1,i f 0
!
( 1 ) !,i f 1
n
n
n
nn
Process to solve n!
Main Program main,fact(4)
Parameter 4 Calc,4*fact(3) return 24
Parameter 3 Calc,3*fact(2) return 6
Parameter 2 Calc,2*fact(1) return 2
Parameter 1 Calc,1*fact(0) return 1
Parameter 0 Direct value = 1 return 1
Ca
ll r
ec
urs
ive
ly
Pa
ss
pa
rame
ter
s
Re
tur
n r
es
ults
Re
tur
n f
or
va
lue
Recursive process and recursive
work stack
Recursive process needs to call itself during
implementation.
A top-down recursion and an opposite order
when quitting:
Recursive call
n! (n-1)! (n-2)! 1! 0!=1
Order when returning
Outer Call when main calls recursion for the
first time;
Inner call when recursion calls itself.
Recursive work stack
Every recursive call needs new storage for
parameters &local variables.
Allocated storages form recursive work records
organized by last-in-first-out stack.
Local variables
Returning addr.
parameters
Action recording
framework
Recursive
work stack
Action records in recursions
……………….
<next direction>
Function(<parameter list>)
……………….
<return>
Calling block
Function block
Return addr.(next direction) local variables parameters
long Factorial ( long n ) {
int temp;
if ( n == 0 ) return 1;
else temp = n * Factorial (n-1);
RetLoc2
return temp;
}
void main ( ) {
int n;
n = Factorial (4);
RetLoc1
}
Contents of action records when calc,
Fact
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
Para,Ret addr,Directions when returning
RetLoc1 return 4*6 //return 24
RetLoc2 return 3*2 //ret,6
RetLoc2 return 1 //ret.1
RetLoc2 return 1*1 //ret.1
RetLoc2 return 2*1 //ret.2
Re
cu
rsiv
e c
all
se
qu
en
ce
Change recursion to non-recursion
Recursion,simple,easy for coding &
understanding;
Recursion,low efficient,too many repeats;
Change to non-recursion to improve efficency;
One-way or end recursion can directly use iteration
to realize non-cirection;
Others needs stack to realize non-recursion.
A recursive data structure
List with several nodes
E.g,nodes of a list
f?
f?
List with one node
Eg1.Search for the last node in a list and
print its value
void Search ( ListNode *f ) {
if ( f ->link == NULL )
printf (―%d \n‖,f ->data );
else Search ( f ->link );
}
f
f f f f
a0 a1 a2 a3 a4
Find the end node recursively
Eg2,Search a node with an equivalent
value to a fixed value and print it
void Search ( ListNode *f,ListData& x ) {
if ( f != NULL )
if ( f -> data == x )
printf (“%d\n”,f ->data );
else Search ( f -> link,x );
}
f
f f f
Recursively find a node with value x
x
E.g,Solution to the Tower of Hanoi
if n=1,move a plate from pillar A to C.
Otherwise,do the following 3 steps:
① Making use of pillar C,move (n-1) plates
in A to B;
② Move the last plate in A to C directly;
③ Making use of pillar A,move (n-1) plates
in B to C;
A recursive solution of the problem
Algorithm:
#include <iostream.h>
#include "strclass.h”
void Hanoi (int n,String A,String B,String C) {
//Algorithm of the Tower of Hanoi
if ( n == 1 ) printf (" move %s",A," to %s,C);
else { Hanoi ( n-1,A,C,B );
printf (" move %s",A," to %s,C);
Hanoi ( n-1,B,A,C );
}
}
Calc,Fibonacci function Fib(n)
Recursive algorithm of Fibonacci function
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
e.g,F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
Recursive calling tree for Fib(5)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(4)
Fib(1) Fib(0)
Fib(2)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(5)
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
Stack node n tag
tag = 1,left recursion；
tag = 2,right recursion
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2
4 1
n=1
sum=1+1
4 2
n=4-2
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
long Fibnacci ( long n ) {
Stack<Node> S; Node *w; long sum = 0;
//Repeat till all data of end node being accumulated
do {
while ( n > 1 ) {
w->n = n; w->tag = 1; S.push ( w );
n--;
} //left-recursion to the end while putting nodes into stack
sum = sum + n; //calculate for sum
while ( !S.IsEmpty( ) ) {
w = S.getTop( ); S.Pop( );
if ( w->tag == 1 ) { //change to right-recursion
w->tag = 2; S.push ( w );
n = w->n – 2; //F(n-2) is in the right side of F(n)
break;
}
}
} while ( !S.IsEmpty( ) );
return sum;
}
Recursion and backtracking
n-queen problem:
In a chess board with n rows and n
columns,attack occurs if two queens stand in
the same row,the same column,the same
diagonal line,n-queen problem needs to find a
layout without attacks.
1#primary diagonal
0#secondary diagonal
1#secondary diagonal
5#secondary diagonal
0#primary diagonal
4#primary diagonal
6#primary diagonal
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
3#secondary diagonal
2#secondary diagonal
4#secondary diagonal
6#secondary diagonal
3#primary diagonal
5#primary diagonal
2#primary diagonal
Solution
When placing a queen in row i,need to try column 0~n-
1 ( j = 0,…,n -1 )
When placing a queen in column j:
If exists other queens in column,primary diagonal
,secondary diagonal,cancel the queen in column j
due to an attack.
If exists no attack,maintain the position of queen in
column j,and place a queen in row i+1 recursively.
Set 4 arrays
col [n],col[i] marks whether queens
are in column I;
md[2n-1],md[k] marks whether
queens are in primary diagonal k;
sd[2n-1],sd[k] marks whether queens
are in secondary diagonal k;
q[n],q[i] records column number of a
queen in row i.
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( no attack in row i&column j) {
place a queen in row i&column j;
if ( i == n-1 ) output a layout；
else Queen ( i+1 );
cancel queen in row I&column j;
}
}
}
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( !col[j] && !md[n+i-j-1] && !sd[i+j] )
{ /*no attack in row i&columnj */
col[j] = md[n+i-j-1] = sd[i+j] = 1;
q[i] = j; /*place a queen in row i&column j;*/
if ( i == n-1 ) { /*output a layout*/
for ( int k = 0; k < n; k++ )
cout << q[k] <<?,‘;
cout << endl;
}
else Queen ( i+1 );
col[j] = md[n+i-j-1] = sd[i+j] = 0;
q[i] = 0; /*cancel queen in row I&column j*/
}
}
}
1,ADT
1
2
3
4
5
6
65
6
5
A stack is a Last-In-First-Out (LIFO) list,that is,
an ordered list in which insertions and deletions
are made at the top only.
Objects,A finite ordered list with zero or more elements.
Operations:
Int StackEmpty( Stack S );
Int StackFull( Stack S );?
Stack InitStack( );
MakeEmpty( Stack S );
Push( ElementType X,Stack S );
ElementType GetTop( Stack S );
Pop( Stack S );
Note:A Pop (or GetTop) on
an empty stack is an error in
the stack ADT.
Push on a full stack is
an implementation error but
not an ADT error.
CHAPTER 4 Stacks and Queues
2,Implementations
Linked List Implementation
typedef int StackData;
typedef struct node {
StackData data; //结点
struct node *link; //链指针
} StackNode;
typedef struct {
StackNode *top; //栈顶指针
} LinkStack;
Basic operation of Linked List Implementation
Create
void InitStack ( LinkStack *S ) {
S->top = NULL;
}
Push
int Push ( LinkStack *S,StackData x ) {
StackNode *p = ( StackNode * ) malloc
( sizeof ( StackNode ) );
p->data = x; p->link = S->top;
S->top = p; return 1;
}
StackEmpty
int StackEmpty (LinkStack *S) {
return S->top == NULL;
}
Pop
int Pop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
StackNode * p = S->top;
S->top = p->link;
x = p->data;
free (p);
return 1;
}
GetTop
int GetTop ( LinkStack *S,StackData &x ) {
if ( StackEmpty (S) ) return 0;
x = S->top->data;
return 1;
}
MakeEmpty
int MakeEmpty ( LinkStack *S) {
While(S->top!=NULL){
StackNode * p = S->top;
S->top = S->top ->link;
free(p);
}
}
Array Implementation
#define STACK_INIT_SIZE 100；
#define STACKINCREMENT 10；
typedef char StackData;
typedef struct { //顺序栈定义
StackData *base; //栈底指针
StackData *top; //栈顶指针
int stacksize； //当前已分配的存储空间
} SeqStack；
Note,?The stack model must be well encapsulated,That is,no
part of your code,except for the stack routines,can
attempt to access the Array or TopOfStack variable.
Error check must be done before Push or Pop (Top).
Basic operation of Array Implementation
Create stack
void InitStack ( SeqStack *S) { //置空栈
S->base=( StackData *)malloc(STACK_INIT_SIZE *
sizeof(StackData));
if (!S->base) exit(OVERFLOW);
S->top = S->base ;
S->stacksize= STACK_INIT_SIZE ;
Return ok;
}
StackEmpty
int StackEmpty (SeqStack *S) {
if( S->top == S->base ) return 1 //判栈空,空则返回 1
else return 0; //否则返回 0
}
MakeEmpty
void MakeEmpty(Stack s)
{S->top == S->base ;}
Push
int Push (SeqStack *S,StackData x) {
//插入元素 x为新的栈顶元素
if ( StackFull (S) ){
S->base=( StackData *)malloc(S->base,
(S->stacksize+ STACKINCREMENT) *
sizeof(StackData));
if(! S->base)exit(overflow);
S->top= S->base+ S->stacksize;
S->stacksize+= STACKINCREMENT; //追加存储空间
}
*(S->top)=x;
（ S->top） ++;
Return ok
}
Pop
int pop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素退出到 x并返回 1
if ( StackEmpty(S) ) return 0;
--(S->top);
x = *(S->top);
return 1;
}
Gettop
int Gettop (SeqStack *S,StackData &x) {
//若栈空返回 0,否则栈顶元素读到 x并返回 1
if ( StackEmpty(S) ) return 0;
(S->top)--;
x = *(S->top);
return 1;}
3,Applications
Balancing Symbols
Check if parenthesis ( ),brackets [ ],and braces { } are balanced.
Algorithm {
Make an empty stack S;
while (read in a character c) {
if (c is an opening symbol)
Push(c,S);
else if (c is a closing symbol) {
if (S is empty) { ERROR; exit; }
else { /* stack is okay */
if (Top(S) doesn’t match c) { ERROR,exit; }
else Pop(S);
} /* end else-stack is okay */
} /* end else-if-closing symbol */
} /* end while-loop */
if (S is not empty) ERROR;
}
T( N ) = O ( N )
where N is the length
of the expression.
This is an
on-line algorithm.
N = (N div d)× d + N mod d
Example,（ 1348)10 = (2504)8,the Computing
process is as follows：
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
Out
pu
t o
rder
Order
of
co
mpu
tat
ion
digital conversion
void conversion () {
InitStack(S);
scanf ("%d",N);
while (N) {
Push(S,N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d",e );
}
} // conversion
when users input a line of characters,line editor allows to input wrong
characters,and it can correct errors timely.
Create a input buffer to store a line of characters of users input,and then
store to data storage area line by line,Suppose?#‘ to backspace and?@‘ to
denote cancelling a line of input.
Assume that editor accept two lines of characters from the terminal,
whli##ilr#e（ s#*s)
outcha@putchar(*s=#++);
The editor should store：
while (*s)
putchar(*s++);
Line editor
Void LineEdit(){
InitStack(s);
ch=getchar();
while (ch != EOF) { //EOF为全文结束符
while (ch != EOF && ch != '\n') {
switch (ch) {
case '#',Pop(S,c); break;
case '@',ClearStack(S); break;
// 重置 S为空栈
default,Push(S,ch); break;
}
ch = getchar(); // 从终端接收下一个字符
}
Send the characters which is from base to top to
the processing data storage area;
ClearStack(S); // 重置 S为空栈
if (ch != EOF) ch = getchar();
}
DestroyStack(s);
}
Maze solving
Common method is exhaust algorithm
# # # # # # # # # #
# # $ $ $ # #
#? # $ $ $ # #
# $ $ # # #
#? # # # # #
# # # #
# # # #
# # # # #? # # #
# #
# # # # # # # # # #
The basic idea of maze solving
When the current position is feasible,
then store the path,go ahead;
When the current position is unfeasible,
then go back and change directions.
If all directions are unfeasible,delete the
current position from the path.
set the initial value of current position as entry position;
do｛
if the current position is feasible，
then｛ push the current position to stack；
if this position is exit position,the algorithm end；
else set the box east of current position as the new
current position.
｝
else {
………..
｝
｝ while (stack is not empty）；
If stack is not empty and the top position has other
directions not be exploited.
Then set the new current position,find the next
adjacent box of the top position along the clockwise
rotation;
If stack is not empty and all directions are unfeasible.
then｛
delete the top of stack； // 从路径中删去该通道块
if stack is not empty,then test the new top position,
until find an adjacent reachable box or stack is
empty;
｝
Postfix Evaluation
〖 Example〗 An infix expression,a? b? c? d? e
A prefix expression, a? b c? d e
A postfix expression,a b c d e
operand operatoroperator with the highest
precedence〖 Example〗 6 2? 3? 4 2 =? 8
top
Get token,6 ( operand )
top6
Get token,2 ( operand )
top2
Get token,? ( operator )
2?6 = 3top
top
3
Get token,3 ( operand )
3
Get token,? ( operator )
33? = 00
Get token,4 ( operand )
top4 Get token,2 ( operand )
top2
Get token,? ( operator )
24? = 8
8
Get token,? ( operator )
80? = 8
8 Pop,8
Reverse Polish notation
T( N ) = O ( N ),No need to know precedence rules.
Infix to Postfix Conversion
〖 Example〗 a? b? c? d =? a b c d?
Note:
The order of operands is the same in infix and postfix.
Operators with higher precedence appear before those with lower precedence.
Output:
top
Get token,a (operand)
a
Get token,? (plus)
top
Get token,b (operand)
b
Get token,? (times)
top?
Get token,c (operand)
c
Get token,? (minus)
top
Get token,d (operand)
d?
(
〖 Example〗 a? ( b? c )? d =? a b c d?
top
Output:
Get token,a (operand)
a
Get token,? (times)
top
Get token,( (lparen)
(?top(
Get token,b (operand)
b
Get token,? (plus)
top+
Get token,c (operand)
c
Get token,) (rparen)
top
Get token,? (divide)
Get token,d (operand)
d?
T( N ) = O ( N )
Solutions:
Never pop a ( from the stack except when processing a ),
Observe that when ( is not in the stack,its precedence is the highest; but
when it is in the stack,its precedence is the lowest,Define in-stack
precedence and incoming precedence for symbols,and each time use the
corresponding precedence for comparison,
Note,a – b – c will be converted to a b – c –,However,2^2^3 ( ) must be
converted to 2 2 3 ^ ^,not 2 2 ^ 3 ^ since exponentiation associates
right to left.322
Function Calls -- System Stack
Return Address
Stack Frame s p
Local Variables
Return Address
s p
s pOld Frame Pointer s p
f p
f p
f p
void PrintList ( List L )
{
if ( L != NULL ) {
PrintElement ( L->Element );
PrintList( L->next );
}
} /* a bad use of recursion */
tail recursion
void PrintList ( List L )
{
top,if ( L != NULL ) {
PrintElement ( L->Element );
L = L->next;
goto top; /* do NOT do this */
}
} /* compiler removes recursion */
Recursion can always be completely removed.
Non recursive programs are generally faster than
equivalent recursive programs.
However,recursive programs are in general
much simpler and easier to understand.
§ 2 The Queue ADT
1,ADT
A queue is a First-In-First-Out (FIFO) list,that is,an
ordered list in which insertions take place at one end
and deletions take place at the opposite end.
2
3
4
1
1
1
2
2
Objects,A finite ordered list with zero or more elements.
Operations:
int IsEmpty( Queue Q );
Queue CreateQueue( );
DisposeQueue( Queue Q );
MakeEmpty( Queue Q );
Enqueue( ElementType X,Queue Q );
ElementType Front( Queue Q );
Dequeue( Queue Q );
Job 3
2,Implementation of Queues
Array
struct QueueRecord {
int Capacity ; /* max size of queue */
int Front; /* the front pointer */
int Rear; /* the rear pointer */
int Size; /* Optional - the current size of queue */
ElementType *Array; /* array for queue elements */
} ;
〖 Example〗 Job Scheduling in an Operating System
Rear Front
Enqueue Job 1 Enqueue Job 2 Enqueue Job 3 Dequeue Job 1
Enqueue Job 4 Enqueue Job 5 Enqueue Job 6 Dequeue Job 2
Enqueue Job 7 Enqueue Job 8
Job 1 Job 2
Rear RearFront Rear
Job 4
Rear
Job 5
Rear
Job 6
Front Rear
Job 7
0 1 2 3 4 5 6
2,Implementation of Queues
Linked list
data next
front
rear
frontrea
r
x ^ x enqueue
frontrea
r
x ^ y ^ y dequeue
frontrear x ^^ y x dequeue
frontrear ^ empty^ frontrear NULL empty
Linked list queues‘ definition
typedef int QueueData;
typedef struct node {
QueueData data; //队列结点数据
struct node *link; //结点链指针
} QueueNode;
typedef struct {
QueueNode *rear,*front;
} LinkQueue;
Basic operation
Initial
void InitQueue ( LinkQueue *Q ) {
Q->rear = Q->front = NULL;
}
Empty
int QueueEmpty ( LinkQueue *Q ) {
return Q->front == NULL;
}
Get Front element
int GetFront ( LinkQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->front->data; return 1;
}
EnQueue
int EnQueue ( LinkQueue *Q,QueueData x ) {
QueueNode *p = ( QueueNode * ) malloc
( sizeof ( QueueNode ) );
p->data = x; p->link = NULL;
if ( Q->front == NULL )
//空,创建第一个结点
Q->front = Q->rear = p;
else Q->rear->link = p; //入队
Q->rear =p;
return 1;
}
DeQueue
int DeQueue ( LinkQueue *Q,QueueData &x) {
//删去队头结点，并返回队头元素的值
if ( QueueEmpty (Q) ) return 0; //判队空
QueueNode *p = Q->front;
x = p->data; //保存队头的值
Q->front= Q->front->link; //新队头
free (p);
return 1;
}
Are you kidding?
Of course I do!
Do you have
a better idea?
[ 0 ]
[ 1 ]
[ 2 ][ 3 ]
[ 4 ]
[ 5 ]
Enqueue Job 1
Enqueue Job 2
Enqueue Job 3
Dequeue Job 1
Enqueue Job 4
Enqueue Job 5
Enqueue Job 6
Enqueue Job 7
Job
1
Job
2
Job
3
Job
4
Job
5
Job
6
The queue
is full
Question:
Why is the queue
announced full
while there is
still a free
space left?
Circular Queue:
Rear
Front
Rear
Rear
Front
Rear
Rear Rear
Note,Adding a Size field can avoid wasting one empty space to
distinguish,full” from,empty”,Do you have any other
ideas?
2,Implementation of Circular Queue
Array
Front and rear pointer add1,use modular arithmetic
Front pointer add 1,front = (front+1) %maxsize;
Rear pointer add 1,rear = (rear+1) % maxsize;
Initial Queue,front = rear = 0;
Empty Queue‘s condition,front == rear;
Full Queue‘s condition,(rear+1) % maxsize == front;
0
1
23
4
5
6 7
Circular Queue
front
rear
Maxsize-1
Circular Queue‘s definition
#define MAXSIZE 100
Typedef struct{
QueueData *data;
int front;
int rear;
} SeqQueue
Basic operation of Circular Queue
Initial
void InitQueue ( SeqQueue *Q ) {
//构造空队列
Q->data=(QueueData *)malloc(MAXSIZE
*sizeof(QueueData));
If(! Q->data)exit(OVERFLOW);
Q->rear = Q->front = 0;
Return ok
}
QueueEmpty
int QueueEmpty ( SeqQueue *Q ) {
return Q->rear == Q->front;
}
QueueFull
int QueueFull ( SeqQueue *Q ) {
return (Q->rear+1) % QueueSize == Q->front;
}
EnQueue
int EnQueue ( SeqQueue *Q,QueueData x ) {
if ( QueueFull (Q) ) return 0;
Q->data[Q->rear] = x;
Q->rear = ( Q->rear+1) % MAXSIZE;
return 1;
}
DeQueue
int DeQueue ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[Q->front];
Q->front = ( Q->front+1) % MAXSIZE;
return 1;
}
GetFront
int GetFront ( SeqQueue *Q,QueueData &x ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[(Q->front+1) % MAXSIZE];
return 1;
}
1 1 i = 1
1 2 1 2
1 5 5 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
Queue application
—print the coefficient of the binomial (a + b)i expansion
Pascal‘s triangle(杨辉三角 )
Analyze the relation between the ith elements
and the (i+1)th elements
Conclusion,we can compute the next line
numbers from the above line numbers.
compute and store the next line
numbers from the above line numbers
void YANGVI ( int n ) {
Queue q; //队列初始化
q.MakeEmpty ( );
q.EnQueue (1); q.EnQueue (1);//预放入第一行的两个系数
int s = 0;
for ( int i=1; i<=n; i++ ) { //逐行处理
cout << endl;
q.EnQueue (0);
for ( int j=1; j<=i+2; j++ ) { //处理第 i行的 i+2个系数
int t = q.DeQueue ( );//读取系数
q.EnQueue ( s+t );//计算下一行系数，并进队列
s = t;
if ( j != i+2 ) cout << s <<? ‘;//打印一个系数，第 i+2个为 0
}
}
}
Def,If an object partly contains itself,or is defined
by itself,this object is recursive;
If a process calls itself directly or indirectly,
this process is a recursive process.
3 recursive conditions
A recursive definition
A recursive data structure
A recursive solution of the problem
§ 3 Recursion
A recursive definition
A recursive algorithm to solve factorial function:
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
Eg1,Factorial function
1,i f 0
!
( 1 ) !,i f 1
n
n
n
nn
Process to solve n!
Main Program main,fact(4)
Parameter 4 Calc,4*fact(3) return 24
Parameter 3 Calc,3*fact(2) return 6
Parameter 2 Calc,2*fact(1) return 2
Parameter 1 Calc,1*fact(0) return 1
Parameter 0 Direct value = 1 return 1
Ca
ll r
ec
urs
ive
ly
Pa
ss
pa
rame
ter
s
Re
tur
n r
es
ults
Re
tur
n f
or
va
lue
Recursive process and recursive
work stack
Recursive process needs to call itself during
implementation.
A top-down recursion and an opposite order
when quitting:
Recursive call
n! (n-1)! (n-2)! 1! 0!=1
Order when returning
Outer Call when main calls recursion for the
first time;
Inner call when recursion calls itself.
Recursive work stack
Every recursive call needs new storage for
parameters &local variables.
Allocated storages form recursive work records
organized by last-in-first-out stack.
Local variables
Returning addr.
parameters
Action recording
framework
Recursive
work stack
Action records in recursions
……………….
<next direction>
Function(<parameter list>)
……………….
<return>
Calling block
Function block
Return addr.(next direction) local variables parameters
long Factorial ( long n ) {
int temp;
if ( n == 0 ) return 1;
else temp = n * Factorial (n-1);
RetLoc2
return temp;
}
void main ( ) {
int n;
n = Factorial (4);
RetLoc1
}
Contents of action records when calc,
Fact
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
Para,Ret addr,Directions when returning
RetLoc1 return 4*6 //return 24
RetLoc2 return 3*2 //ret,6
RetLoc2 return 1 //ret.1
RetLoc2 return 1*1 //ret.1
RetLoc2 return 2*1 //ret.2
Re
cu
rsiv
e c
all
se
qu
en
ce
Change recursion to non-recursion
Recursion,simple,easy for coding &
understanding;
Recursion,low efficient,too many repeats;
Change to non-recursion to improve efficency;
One-way or end recursion can directly use iteration
to realize non-cirection;
Others needs stack to realize non-recursion.
A recursive data structure
List with several nodes
E.g,nodes of a list
f?
f?
List with one node
Eg1.Search for the last node in a list and
print its value
void Search ( ListNode *f ) {
if ( f ->link == NULL )
printf (―%d \n‖,f ->data );
else Search ( f ->link );
}
f
f f f f
a0 a1 a2 a3 a4
Find the end node recursively
Eg2,Search a node with an equivalent
value to a fixed value and print it
void Search ( ListNode *f,ListData& x ) {
if ( f != NULL )
if ( f -> data == x )
printf (“%d\n”,f ->data );
else Search ( f -> link,x );
}
f
f f f
Recursively find a node with value x
x
E.g,Solution to the Tower of Hanoi
if n=1,move a plate from pillar A to C.
Otherwise,do the following 3 steps:
① Making use of pillar C,move (n-1) plates
in A to B;
② Move the last plate in A to C directly;
③ Making use of pillar A,move (n-1) plates
in B to C;
A recursive solution of the problem
Algorithm:
#include <iostream.h>
#include "strclass.h”
void Hanoi (int n,String A,String B,String C) {
//Algorithm of the Tower of Hanoi
if ( n == 1 ) printf (" move %s",A," to %s,C);
else { Hanoi ( n-1,A,C,B );
printf (" move %s",A," to %s,C);
Hanoi ( n-1,B,A,C );
}
}
Calc,Fibonacci function Fib(n)
Recursive algorithm of Fibonacci function
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
e.g,F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
Recursive calling tree for Fib(5)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(4)
Fib(1) Fib(0)
Fib(2)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(5)
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
Stack node n tag
tag = 1,left recursion；
tag = 2,right recursion
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2
4 1
n=1
sum=1+1
4 2
n=4-2
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
long Fibnacci ( long n ) {
Stack<Node> S; Node *w; long sum = 0;
//Repeat till all data of end node being accumulated
do {
while ( n > 1 ) {
w->n = n; w->tag = 1; S.push ( w );
n--;
} //left-recursion to the end while putting nodes into stack
sum = sum + n; //calculate for sum
while ( !S.IsEmpty( ) ) {
w = S.getTop( ); S.Pop( );
if ( w->tag == 1 ) { //change to right-recursion
w->tag = 2; S.push ( w );
n = w->n – 2; //F(n-2) is in the right side of F(n)
break;
}
}
} while ( !S.IsEmpty( ) );
return sum;
}
Recursion and backtracking
n-queen problem:
In a chess board with n rows and n
columns,attack occurs if two queens stand in
the same row,the same column,the same
diagonal line,n-queen problem needs to find a
layout without attacks.
1#primary diagonal
0#secondary diagonal
1#secondary diagonal
5#secondary diagonal
0#primary diagonal
4#primary diagonal
6#primary diagonal
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
3#secondary diagonal
2#secondary diagonal
4#secondary diagonal
6#secondary diagonal
3#primary diagonal
5#primary diagonal
2#primary diagonal
Solution
When placing a queen in row i,need to try column 0~n-
1 ( j = 0,…,n -1 )
When placing a queen in column j:
If exists other queens in column,primary diagonal
,secondary diagonal,cancel the queen in column j
due to an attack.
If exists no attack,maintain the position of queen in
column j,and place a queen in row i+1 recursively.
Set 4 arrays
col [n],col[i] marks whether queens
are in column I;
md[2n-1],md[k] marks whether
queens are in primary diagonal k;
sd[2n-1],sd[k] marks whether queens
are in secondary diagonal k;
q[n],q[i] records column number of a
queen in row i.
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( no attack in row i&column j) {
place a queen in row i&column j;
if ( i == n-1 ) output a layout；
else Queen ( i+1 );
cancel queen in row I&column j;
}
}
}
void Queen( int i ) {
for ( int j = 0; j < n; j++ ) {
if ( !col[j] && !md[n+i-j-1] && !sd[i+j] )
{ /*no attack in row i&columnj */
col[j] = md[n+i-j-1] = sd[i+j] = 1;
q[i] = j; /*place a queen in row i&column j;*/
if ( i == n-1 ) { /*output a layout*/
for ( int k = 0; k < n; k++ )
cout << q[k] <<?,‘;
cout << endl;
}
else Queen ( i+1 );
col[j] = md[n+i-j-1] = sd[i+j] = 0;
q[i] = 0; /*cancel queen in row I&column j*/
}
}
}
