Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 4: Ngăn xếp và hàng đợi - Đỗ Tuấn Anh

: value = left / right;
break;
case '^': value = pow(left, right);
break;
}
return value;
}
int postfixEval(string expression)
{
// expValue lưu kết quả của biểu thức
int left, right, expValue;
char ch;
// Tạo một stack lưu trữ toán hạng
IntStack* stack = CreateStack(MAX);
// Duyệt từng ký tự cho đến khi hết xâu
for (int i=0; i < expression.length(); i++)
{
// đọc một ký tự
ch = expression[i];
// nếu ch là toán hạng
if (isdigit(ch))
// đẩy toán hạng vào stack
PushStack(stack, ch - '0');
Hàm postfixEval()
// nếu ch là toán tử
else if (isOperator(ch)){ 
// rút stack 2 lần để lấy 2
// toán hạng left và right
PopStack(stack, &right);
PopStack(stack, &left);
// Tính "left op right" 
result = compute(left, right, ch);
// Đẩy result vào stack
PushStack(stack, temp);
}else //không phải toán hạng hoặc toán t
printf(“Bieu thuc loi”);
}
// Kết thúc tính toán, giá trị biểu thức 
// nằm trên đỉnh stack, đưa vào expValue
PopStack(stack, expValue);
return expValue;
}
Chuyển đổi trung tố→hậu tố
Toán hạng sẽ được ghi ngay vào xâu kết quả
Trong khi quét biểu thức số học:
Không cần sử dụng stack cho toán hạng.
Khi gặp toán tử hoặc dấu ngoặc, đẩy vào stack.
stack toán tử
Quản lý thứ tự ưu tiên giữa các toán tử
Xử lý các biểu thức con.
Hạng
Chỉ xét các toán tử hai ngôi.
Hạng.
1 nếu là toán hạng
-1 nếu là +, -, *, /, %, ^
0 nếu là (, ) 
Ví dụ 1
stack dùng để lưu trữ một cách tạm thời các toán tử trong 
khi chờ toán hạng 2 (phải) tương ứng.
a + b * c
+
Stack 
toán tử:
Xâu hậu tố: a cb +*
*
* có mức ưu tiên cao hơn + 
⇒ Thêm vào stack
Ví dụ 2
Sử dụng stack để xử lý các toán tử có cùng thứ tự
ưu tiên hoặc thấp hơn.
a * b / c + d
*
Stack toán tử:
Xâu hậu tố: a *b /c
/
* có cùng mức ưu tiên với / 
⇒ rút * và ghi nó vào xâu hậu tố
trước khi thêm / vào stack.
d
+
+
/ có mức ưu tiên cao hơn +
Ví dụ 3
Sử dụng giá trị mức ưu tiên để xử lý ^ (tính lũy thừa).
a ^ b ^ c
^
Stack toán tử:
Xâu hậu tố: a cb ^^
^ thứ 2 có mức ưu tiên là 4 nhưng
^ thứ 1 có mức ưu tiên là 3
⇒ ^ thứ 2 được đẩy tiếp vào stack
(do đó nó sẽ được rút ra trước ^ thứ 1)
Mức ưu tiên đầu vào: 4 khi ^ là đầu vào.
Mức ưu tiên tại stack: 3 khi ^ nằm trong stack. 
^
Ví dụ 4
Hai mức ưu tiên cho dấu ngoặc trái (
a * ( b + c )
*
Stack toán tử:
Xâu hậu tố: a cb *+
( có mức ưu tiên là 5 ⇒
đưa vào stack.
Mức ưu tiên đầu vào: 5 cao hơn bất kỳ toán tử nào.
(tất cả các toán tử trong stac phải giữ nguyên vì có một biểu thức con mới.)
Mức ưu tiên tại stack: -1 thấp hơn của bất kỳ toán tử nào.
(không toán tử nào trong biểu thức con được xóa cho đến khi gặp dấu ngoặc mở)
(
+ ( hiện có mức ưu tiên là -1 ⇒
tiếp tục ở trong stack.
Mức ưu tiên đầu vào và tại Stack
Mức ưu tiên
đầu vào
Mức ưu tiên
tại stackToán tử
+ - 1 1 -1
* / % 2 2 -1
^ 4 3 -1
( 5 -1 0
) 0 0 0
Hạng
Các quy luật đánh giá
Ghi ký tự vào xâu hậu tố nếu nó là toán hạng.
Nếu ký tự là một toán tử hoặc (, so sánh mức ưu tiên của nó
với mức ưu tiên của toán tử tại đỉnh stack.
Rút phần tử đỉnh stack nếu mức ưu tiên của phần tử tại stack
là cao hơn hoặc bằng và ghi tiếp nó vào xâu hậu tố.
Lặp cho đến khi toán tử tại đỉnh stack có hạng thấp hơn,
đẩy ký tự vào stack.
Nếu ký tự là ), rút tất cả các toán tử ra khỏi stack cho đến khi 
gặp ( và ghi các toán tử vào xâu hậu tố. Rút ( ra khỏi stack.
Khi kết thúc biểu thức trung tố, rút tất cả các toán tử ra khỏi stack
và ghi vào xâu hậu tố.
Ví dụ
3 * (4 – 2 ^ 5) + 6 
Stack toán tử
Hậu tố 3
* [2]
3
( [-1]
* [2]
3
( [-1]
* [2]
3 4
( [-1]
* [2]
- [1]
3 4
( [-1]
* [2]
- [1]
3 4 2
( [-1]
* [2]
- [1]
^ [3]
3 4 2
( [-1]
* [2]
- [1]
^ [3]
3 4 2 5
( [-1]
* [2]
3 4 2 5 ^ -
cont’d
* [2]
3 4 2 5 ^ -
Pop (
+ [1]
3 4 2 5 ^ - * 3 4 2 5 ^ - * 6 
+ [1]
3 4 2 5 ^ - * 6 + 
3 * (4 – 2 ^ 5) + 6 
Stack
typedef struct Operator {
char symbol; // toán tử
// mức ưu tiên đầu vào của toán tử op
int inputPrecedence; 
// mức ưu tiên trong stack của toán tử op
int stackPrecedence; 
}Operator;
typedef struct OpStack {
Operator * stackAry;
.
} OpStack ;
Xây dựng một stack cho phép lưu trữ các toán tử và mức ưu tiên của nó.
Output Stack Symbols
Rút các toán tử trong stack có stack precedence ≥ input precendence
của ký tự đang đọc.
void PopHigherOrEqualOp(OpStack* stack, Operator& op
string& postfix)
{
Operator op2;
while(!IsEmpty(stack) && 
(op2 = Top(stack)).stackPrecedence >= 
op.inputPrecedence)
{
Pop(stack);
postfix += op2.symbol;
}
}
Hàm chuyển đổi trung tố - hậu tố
Ghi toán hạng ra xâu hậu tố.
Gọi outputHigherOrEqual() nếu gặp toán tử.
Infix2Postfix() thực hiện những công việc sau:
Gọi outputHigherOrEqual() nếu gặp ).
Kết thúc khi đọc hết biểu thức
string Infix2Postfix ( string infix) {
string postfix; // lưu xâu biểu thức hậu tố
OpStack* stack = CreateStack( MAX); // tạo stack
// Duyệt từng ký tự của biểu thức
for (i=0; i < infix.length(); i++) {
ch = infix [i];
//****** Trường hợp toán hạng ************
if (isdigit(ch))
// ghi toán hạng vào biểu thức hậu tố
postfix += ch;
//******* Trường hợp toán tử hoặc '(' *****
else if (isOperator(ch) || ch == '(')
{
// rút các toán tử có mức ưu tiên cao hơn 
// ra khỏi stack
Operator op = createOperator(ch);
PopHigherOrEqualOp(stack, op, postfix);
// đẩy toán tử hiện tại vào stack
Push(stack, op);
}
//******** Trường hợp ‘)' *************
else if (ch == ‘)’)
{
// tạo một biến Operator cho ')‘
Operator op = CreateOperator(ch);
// Rút tất cả toán tử của biểu thức con 
// cho đến khi gặp '('
PopHigherOrEqualOp(stack, op, postfix);
// Rút '(' ra khỏi stack
Pop(stack); 
}
} // end for
// Rút các toán tử còn lại trg stack, ghi vào xâu
while (!IsEmpty(stack)) {
op = Pop(stack);
postfix += op.symbol;
}
return postfix;
}
4. Định nghĩa Queue
zQueue: là danh sách mà thêm phải được 
thực hiện tại một đầu còn xóa phải thực 
hiện tại đầu kia.
Thêm
(Enqueue)
Xóa
(Dequeue) CuốiĐầu
Figure 5-1
• Queue là một kiểu cấu trúc FIFO: First In First 
Out
Ví dụ của Queue trong thực tế
Các thao tác cơ bản với Queue
z Enqueue – Thêm một phần tử vào cuối queue
zTràn Overflow
z Dequeue – Xóa một phần tử tại đầu queue
zQueue rỗng?
z Front – Trả lại phần tử tại đầu queue
zQueue rỗng?
z End – Trả lại phần tử tại cuối queue
zQueue rỗng
Figure 5-2
Enqueue
Figure 5-3
Dequeue
Figure 5-4
Queue Front
Figure 5-5
Queue Rear
Lưu trữ Queue
zTương tự như Stack, có 2 cách lưu trữ:
{Lưu trữ kế tiếp: sử dụng mảng
{Lưu trữ móc nối: sử dụng danh sách móc nối
Figure 5-15
5. Lưu trữ kế tiếp với Queue
Figure 5-16
Queue tăng hết mảng
• Do đó cần sử dụng một mảng rất lớn?
Queue dạng vòng
A
B
front
rear
A
BC
front
rear
A
BC
D
front
rear
D
B
C
rear
front
D
BC
E
front
rear
Queue thực hiện trên mảng
11 37 22 15 3 -7 1
queueAry maxsize count front rear
front rear
7 4 1 5
Định nghĩa cấu trúc Queue
typedef struct intqueue {
int *queueAry;
int maxSize;
int count;
int front;
int rear;
}IntQueue;
Tạo Queue
IntQueue* CreateQueue (int max) {
IntQueue *queue;
queue = (IntQueue *)malloc(sizeof(IntQueue));
/* Cấp phát cho mảng */
queue->queueAry = malloc(max * sizeof(int));
/* Khởi tạo queue rỗng */
queue->front = -1;
queue->rear = -1;
queue->count = 0;
queue->maxSize = maxSize;
return queue;
} /* createQueue */
Enqueue
int enqueue (struct intqueue *queue, int datain) {
if (queue->count == queue->maxSize)
return 0; /* queue is full */
(queue->rear)++;
if (queue->rear == queue->maxSize)
/* Queue wraps to element 0 */
queue->rear = 0;
queue->queueAry[queue->rear] = datain; 
if (queue->count == 0) {
/* Inserting into null queue */
queue->front = 0;
queue->count = 1;
} /* if */
else (queue->count)++;
return 1;
Dequeue
int dequeue (struct intqueue *queue, int *dataOutPtr) {
if (!queue->count)
return 0;
*dataOutPtr = queue->queueAry[queue->front];
(queue->front)++;
if (queue->front == queue->maxSize)
/* queue front has wrapped to element 0 */
queue->front = 0;
if (queue->count == 1)
/* Deleted only item in queue */
queue->rear = queue->front = -1;
(queue->count)--;
return 1;
queueFront
int queueFront (struct intqueue *queue,
int *dataOutPtr) { 
if (!queue->count) 
return 0;
else { 
*dataOutPtr = queue->queueAry[queue->front];
return 1;
} /* else */
} /* queueFront */
queueRear
int queueRear (struct intqueue *queue,
int *dataOutPtr) {
if (!queue->count) 
return 0;
else { 
*dataOutPtr = queue->queueAry[queue->rear];
return 1;
} /* else */
} /* queueRear */
emptyQueue and fullQueue
int emptyQueue (struct intqueue *queue) 
{
return (queue->count == 0);
} /* emptyQueue */
int fullQueue (struct intqueue *queue ) 
{
return ( queue->count == queue->maxSize);
} /* fullQueue */
destroyQueue
struct intqueue *destroyQueue (struct intqueue
*queue) 
{
if (queue)
{
free (queue->queueAry); 
free (queue);
} /* if */
return NULL;
} /* destroyQueue */
6. Lưu trữ móc nối với Stack
Các cấu trúc của head và node
link link
Khai báo stack
typedef struct node 
{
int data ;
struct node *link ;
} STACK_NODE;
typedef struct stack
{
int count ; 
STACK_NODE *top ; 
} STACK;
createStack
static STACK *createStack ()
{
STACK *stack ;
stack = (STACK *) malloc( sizeof (STACK) ) ;
if (stack)
{
stack->top = NULL ;
stack->count = 0;
} /* if */
return stack ;
} /* createStack */
Push
zGiống như Thêm một phần tử mới vào
danh sách trước phần tử đầu
pushStack
static int pushStack(STACK *stack, int dataIn) {
STACK_NODE *newPtr;
newPtr = (STACK_NODE *) malloc(sizeof( 
STACK_NODE));
if (newPtr == NULL)
return 0; /* no more space */
newPtr->data = dataIn; 
newPtr->link = stack->top; 
stack->top = newPtr; 
( stack->count )++; 
return 1;
} /* pushStack */
7. Lưu trữ móc nối với Queue
zBài tập về nhà: Xây dựng Queue móc nối