Cấp bậc tác giả:

JAVA

Stack và Queue

Được viết bởi webmaster ngày 11/05/2015 lúc 10:37 PM
Hướng dẫn cài đặt Stack và Queue
  • 0
  • 2490

Stack và Queue

Loading...

I. Stack(ngăn xếp)
1. Nguyên tắc hoạt động: LIFO
2. Cài đặt: Có thể sử dụng mảng hoặc danh sách liên kết đơn hoặc kép
* Bổ sung(PUSH) và lấy ra(POP) đều thực hiện trên 1 đầu gọi là đỉnh(TOP)
3. Các thao tác cơ bản:
a. Khởi tạo Stack = 0
b. Bổ sung 1 phần tử vào Stack
    PUSH(x, Stack);
c. Lấy 1 phần tử ra khỏi Stack
    x = POP(Stack);
4. Ứng dụng của Stack:
a. Khử đệ quy
VD: Biểu diễn nhị phân của số nguyên dương n
void Bin(int n)
{
  Stack s= 0;
  while(n>0)
  {
    PUSH(n%2,s);
    n=n/2;
  }
  while(s!=0)
  printf(POP(s));
}

#include <iostream.h>
void PUSH(int x, int &Top, int Stack[])
{
  Top++;
  Stack[Top]=x;
}
int POP(int &Top, int Stack[])
{
  int x = Stack[Top];
  Top--;
  return x;
}
void BIN(int n)
{
  int Top=0, S[100];
  while(n>0)
  {
    PUSH(n%2,Top,S);
    n=n/2;
  }
  while(S!=0)
  printf(POP(Top,s));
}

b. Biểu diễn biểu thức theo ký pháp nghịch đảo Balan
Biểu thức:
- Trung tố
- Tiền tố
- Hậu tố

VD: (6-2)*(3+4) -> Trung tố
=> * - 6 2 + 3 4 -> Tiền tố(toán tử đứng trước toán hạng)
=> 6 2 - 3 4 + * -> Hậu tố(toán tử đứng sau toán hạng)

* 2 công đoạn:
Stack
1. Chuyển từ dạng trung tố sang hậu tố
2. Tính giá trị biểu thức hậu tố

  posfix             stack
6 2 - 3 4 + *       0
   2 - 3 4 + *       6
      - 3 4 + *      6  2
        3 4 + *         4
           4 + *         4 3
              + *         4 3 4
                 *         4   7
                 0           28
II - Queue(hàng đợi)
1. Nguyên tắc: FIFO
2. Cài đặt:
- Bổ sung(PUSH) ở 1 đầu
- Lấy ra(POP) ở đầu kia

Nguồn bài viết: DOTNET.VN

BÌNH LUẬN BÀI VIẾT

Bài viết mới nhất

Loading...

LIKE BOX

Bài viết được xem nhiều nhất

HỌC HTML