Cách cài đặt stack có sử dụng template

Bài viết hôm nay mình sẽ hướng dẫn các bạn cách cài đặt stack có sử dụng template trong ngôn ngữ c++. Nếu bạn chưa biết template là gì thì có thể xem lại tại đây.

Stack là gì: Stack là một cấu trúc dữ liệu thường dùng phổ biến trong các ngôn ngữ lập trình. Bạn có thể tưởng tượng stack như một đống sách vậy, cứ quyển sau bỏ vào thì sẽ nằm trên quyển trước. Vì vậy mới có một câu nói về stack đó là  “Vào sau ra trước ! “

Các hoạt động cơ bản trên stack

Stack hỗ trợ cho chúng ta các hoạt động sau:

  • Hoạt động Pop(): Xóa dữ liệu từ ngăn xếp
  • Hoạt động Push(): Thêm một phần tử từ ngăn xếp
  • Hoạt động isEmpty(): Kiểm tra xem ngăn xếp có rỗng hay không
  • Hoạt động isFull(): Kiểm tra xem ngăn xếp đã đầy hay chưa

Trong stack ta luôn phải để con trỏ Top trỏ tới phần tử cuối cùng được Push() vào. Sở dĩ con trỏ có tên là Top vì nó luôn trỏ đến phần tử cuối cùng của mảng.

Cách cài đặt stack sử dụng template

Chúng ta sẽ lần lượt cài đặt các hoạt động của stack như sau

Khai báo một lớp stack

Ở trên có các thuộc tính Size chính là số lượng phần tử của stack, Top chính là vị trí của con trỏ chỉ tới phần tử cuối cùng. Data chính là con trỏ dùng để lưu trữ dữ liệu.

Cài đặt construction cho stack

Nếu không truyền vào giá trị cho tham số n, thì mặc định con stack sẽ có 10 phần tử. Ta khởi tạo vị trí Top bằng -1 vì hiện tại stack đang trống.

Cài đặt destruction cho stack

Destruction chỉ có nhiệm vụ là xóa dữ liệu của con trỏ mà thôi.

Cài đặt hoạt động isEmpty()

Cài đặt hoạt động isFull()

Cài đặt hoạt động Push()

Đầu tiên ta kiểm tra xem ngăn xếp đã đầy chưa, nếu vẫn chưa đầy thì ta tiến hành tăng giá trị Top và thêm phần tử vào cuối stack. Hoạt động Push() sẽ trả về giá trị true nếu đã thêm được phần tử thành công.

Cài đặt hoạt động Pop()

Ta tiến hành kiểm tra xem ngăn xếp có rỗng hay không, nếu không rỗng thì sẽ lấy ra giá trị cuối cùng và giảm giá trị của Top. Hoạt động Pop() sẽ trả về giá trị true nếu phần tử đã được lấy ra từ stack thành công và ngược lại.

Chạy thử chương trình cài đặt stack

Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !

4 COMMENTS

  1. Nhow a hieu xem ho

    package excercise.on.spoij;

    import java.util.Scanner;

    public class ConvertToPostfix {

    private static Scanner inputScanner = new Scanner(System.in);
    private static char stack[] ;

    // phuong thuc chuyen doi ky tu thanh so
    public static int chuyenDoi(char element) {
    switch (element) {
    case ‘0’:
    return 0;
    case ‘1’:
    return 1;
    case ‘2’:
    return 2;
    case ‘3’:
    return 3;
    case ‘4’:
    return 4;
    case ‘5’:
    return 5;
    case ‘6’:
    return 6;
    case ‘7’:
    return 7;
    case ‘8’:
    return 8;
    case ‘9’:
    return 9;
    }
    //return element;
    return element;
    }

    public static void main(String args[]) {
    for(int testCase=1 ; testCase <= 10; testCase++) {

    // doc du lieu
    int n= inputScanner.nextInt();
    String string= inputScanner.next();
    char array1[] = new char[n+10];
    for(int i=1; i<= n ; i++)
    array1[i] = string.charAt(i-1);
    stack = new char[n+10];

    // xu ly du lieu
    int indexStack = 1;
    for(int index=1; index <= n;) {
    int openCheck= index-1;
    int closeCheck = index+1;
    // tim vi tri ngoac mo ma truoc toan tu
    if(array1[index-1] == 'x') {
    while( array1[openCheck] == 'x') {
    openCheck–;
    }
    openCheck++;
    }

    // tim vi tri ngoac dong sau toan tu
    if( array1[closeCheck] == 'x') {
    while( array1[closeCheck] == 'x')
    closeCheck++;
    closeCheck–;
    }
    if( array1[index] == '+' || array1[index] == '*') {

    if(array1[openCheck-1] == '(' && array1[closeCheck+1] == ')') {
    stack[ indexStack] = array1[ index+1];
    indexStack++;
    stack[ indexStack] = array1[ index];
    indexStack++;
    array1[index] = 'x';
    array1[openCheck-1] = 'x';
    array1[closeCheck] = 'x';
    array1[closeCheck+1] = 'x';
    index = index +3;
    }
    else {
    if(array1[index] == '*' && array1[openCheck] != ')' && array1[closeCheck] != '(') {
    if( array1[openCheck -1] == '*') {
    stack[indexStack] = '*';
    indexStack++;
    array1[openCheck-1] = 'x';
    }
    else {
    stack[indexStack] = array1[closeCheck];
    indexStack++;
    stack[indexStack] = array1[index];
    indexStack++;
    array1[index] = 'x';
    array1[closeCheck] = 'x';
    index = index +2;
    }
    }
    else {
    if(array1[index] == '+' && array1[openCheck] != ')' && array1[closeCheck] != '(') {
    if(array1[openCheck – 1] == '+' || array1[openCheck – 1] == '*') {
    stack[indexStack] = array1[openCheck – 1];
    indexStack++;
    array1[openCheck – 1]= 'x';
    }
    if(array1[closeCheck +1] == '+') {
    stack[indexStack] = array1[closeCheck];
    indexStack++;
    stack[indexStack] = array1[index];
    indexStack++;
    array1[index] = 'x';
    array1[closeCheck] = 'x';
    index += 2;
    }
    else {
    index++;
    }
    }
    else {
    index++;
    }
    }
    }

    }
    else {
    if(array1[index] == '(' || array1[index] == ')' ) {
    // tim den vi tri index la ')' roi in ra cac toan tu con sot lai trong cap ngoac
    if( array1[index] == ')' ) {
    int var1 = index;
    while(array1[var1] != '(' ) {
    if(array1[var1] == '+' || array1[var1] == '*') {
    stack[indexStack] = array1[var1] ;
    array1[var1] = 'x';
    indexStack++;
    }
    var1–;
    }
    array1[var1] = 'x';
    array1[index] = 'x';
    index++;
    }
    else {
    index++;
    }
    }
    else {
    // vi tri index la so
    stack[indexStack] = array1[index];
    array1[index] = 'x';
    index++;
    indexStack++;
    }
    }
    // for(int i=1; i<stack.length;i++)
    // System.out.print(stack[i]);
    // System.out.println();
    // for(int i=0; i<array1.length;i++)
    // System.out.print(array1[i]);
    // System.out.println();
    }
    for(int i=1; i<=n; i++)
    if( array1[i] == '+' || array1[i] == '*') {
    stack[indexStack] = array1[i];
    indexStack++;
    }
    // System.out.println();
    // for(int i=1; i<stack.length;i++)
    // System.out.print(stack[i]);
    // System.out.println();
    // for(int i=0; i<array1.length;i++)
    // System.out.print(array1[i]);
    // System.out.println();

    // thuc hien tinh
    int stackTotal[] = new int[n+10];
    int index2 =1;
    for(int i=1; i<= indexStack-1; i++) {
    if(stack[i] == '*' || stack[i] == '+') {
    // System.out.println(i +" ");
    if( stack[i] == '*') {
    stackTotal[index2-2] = stackTotal[index2-2] * stackTotal[index2-1];
    index2–;
    }
    else {
    stackTotal[index2-2] = stackTotal[index2-2] + stackTotal[index2-1];
    index2–;
    }
    }
    else {
    stackTotal[index2] = chuyenDoi(stack[i]);
    index2++;
    }
    }
    System.out.println("#"+testCase+ " "+stackTotal[1]);
    }
    }
    }

  2. Nhờ a H xem cho e e sai ở chỗ nào vs ạ, thank you a

    package thuat.toan;

    import java.util.Scanner;

    public class LaughingBomb {

    private static Scanner inputScanner = new Scanner(System.in);
    private static int queue[] = new int[40000];
    private static int map[][] = new int[110][110];
    private static int first, last, xBom, yBom, totalTime,rows, columns;

    public static void addInQueue(int element){
    if( last == 20000){
    // in ra tran queue
    }
    else {
    queue[last] = element;
    last++;
    }
    }

    public static void removeInQueue(){
    if( first == last ){
    // in ra queue rong
    }
    else {
    queue[first] = -1;
    first++;
    }
    }

    public static int takeInQueue() {
    return queue[first];
    }

    public static boolean isEmpty() {
    if( first >= last )
    return false;
    else {
    return true;
    }
    }

    // phuong thuc tinh thoi gian lay nhiem
    public static void layNhiem(int a, int b) {
    if(map[a+1][b] == 1){
    map[a+1][b] += map[a][b];
    totalTime = map[a+1][b];
    addInQueue(a+1);
    addInQueue(b);
    }
    if( map[a-1][b] ==1){
    map[a-1][b] += map[a][b];
    totalTime = map[a-1][b];
    addInQueue(a-1);
    addInQueue(b);
    }
    if( map[a][b+1] == 1 ){
    map[a][b+1] += map[a][b];
    totalTime = map[a][b+1];
    addInQueue(a);
    addInQueue(b+1);
    }
    if( map[a][b-1] == 1 ){
    map[a][b-1] += map[a][b];
    totalTime = map[a][b-1];
    addInQueue(a);
    addInQueue(b-1);
    }
    if( a == xBom && b == yBom){
    map[xBom][yBom]=0;
    }
    first += 2;
    if( first < last){
    layNhiem(queue[first], queue[first+1]);
    }
    }

    public static void main(String args[]){
    int number = inputScanner.nextInt();
    for(int testCase=1 ; testCase <= number ; testCase++ ){
    totalTime =1;
    // doc du lieu
    columns = inputScanner.nextInt();
    rows = inputScanner.nextInt();
    for(int x= 1 ; x<= rows ;x++ )
    for(int y=1 ; y<= columns ; y++)
    map[x][y]= inputScanner.nextInt();
    yBom = inputScanner.nextInt();
    xBom = inputScanner.nextInt();

    // xu ly du lieu
    last = 0;
    first = 0;
    addInQueue(xBom);
    addInQueue(yBom);
    layNhiem(xBom, yBom);
    System.out.println(totalTime);
    for(int x=1;x<= rows; x++)
    for(int y=0;y<= columns ; y++)
    map[x][y] = 0;
    }
    }
    }

  3. Nhờ a H xem cho e e sai ở chỗ nào vs ạ

    package thuat.toan;

    import java.util.Scanner;

    public class ValidateTheMaze {
    private static Scanner inputScanner= new Scanner(System.in);
    private static int entryX=0,entryY=0,exitX=0,exitY=0;
    private static boolean focus = false;
    private static char maze[][] = new char[30][30];
    private static int point[][] = new int[30][30];

    // check maze
    public static void checkMaze(int x,int y, boolean flagLeft, boolean flagRight, boolean flagUp, boolean flagDown){
    if(point[x][y] == 0){
    point[x][y] = 1;
    if( x == exitX && y == exitY ){
    focus = true;
    point[x][y] =0;
    return;
    }
    if( maze[x+1][y] == ‘.’ && focus == false ){// && flagUp == false){
    flagDown = true;
    flagLeft= false;
    flagRight = false;
    //System.out.println(x+ ” “+ y);
    checkMaze((x+1), y, flagLeft, flagRight, flagUp, flagDown);
    }
    if( maze[x-1][y] == ‘.’ && focus == false ){//&& flagDown == false){
    flagUp = true;
    flagLeft= false;
    flagRight = false;
    // System.out.println(x+ ” “+ y);
    checkMaze((x-1), y, flagLeft, flagRight, flagUp, flagDown);
    }
    if( maze[x][y+1] == ‘.’ && focus == false ){// && flagLeft == false){
    flagRight = true;
    flagUp= false;
    flagDown = false;
    // System.out.println(x+ ” “+ y);
    checkMaze(x, (y+1), flagLeft, flagRight, flagUp, flagDown);
    }
    if( maze[x][y-1] == ‘.’ && focus == false ){// && flagRight == false){
    flagLeft = true;
    flagUp= false;
    flagDown = false;
    // System.out.println(x+ ” “+ y);
    checkMaze(x, (y-1), flagLeft, flagRight, flagUp, flagDown);
    }
    point[x][y] = 0;
    }

    }

    public static void main(String args[]){
    int numberTestCase = inputScanner.nextInt();
    for(int testCase=1; testCase <= numberTestCase; testCase++){
    // for(int i=0; i<=29;i++)
    // for(int j=0;j<=29; j++)
    // point[i][j] =0;
    focus = false;
    // doc du lieu
    int rows = inputScanner.nextInt();
    int columns = inputScanner.nextInt();
    for(int x=1; x<= rows ; x++ ){
    String string1 = inputScanner.next();
    for(int y=1 ; y<= string1.length() ; y++)
    maze[x][y] = string1.charAt(y-1);
    }

    // tim vi tri loi vao va loi ra
    int countPoint=0;
    for( int x=1; x<= rows ; x++)
    if( maze[x][1] == '.' ){
    countPoint++;
    if(countPoint % 2 == 1){
    entryX = x;
    entryY = 1;
    }
    else {
    exitX = x;
    exitY = 1;
    }
    }
    for( int x=1; x<= rows ; x++)
    if( maze[x][columns] == '.' && columns != 1){
    countPoint++;
    if(countPoint % 2 == 1){
    entryX = x;
    entryY = columns;
    }
    else {
    exitX = x;
    exitY = columns;
    }
    }
    for( int y=2; y<= columns ; y++)
    if( maze[1][y] == '.' ){
    countPoint++;
    if(countPoint % 2 == 1){
    entryX = 1;
    entryY = y;
    }
    else {
    exitX = 1;
    exitY = y;
    }
    }
    for( int y=2; y<= columns ; y++)
    if( maze[rows][y] == '.' && rows != 1){
    countPoint++;
    if(countPoint % 2 == 1){
    entryX = rows;
    entryY = y;
    }
    else {
    exitX = rows;
    exitY = y;
    }
    }
    if(countPoint != 2){
    System.out.println(testCase+" invalid");
    continue;
    }

    // kiem tra xem maze co ton tai hay khong
    checkMaze(entryX, entryY, false, false, false, false);
    for(int i=0;i<= 29; i++){
    for(int j=0; j<=29; j++)
    System.out.print(point[i][j]);
    System.out.println();
    }
    if( focus == true)
    System.out.println(testCase+"valid");
    else {
    System.out.println(testCase+"invalid");
    }
    }
    }

    }

LEAVE A REPLY

Please enter your comment!
Please enter your name here