Cấu trúc dữ liệu và thuật toán -CHƯƠNG II CẤU TRÚC DỮ LIỆU-NGĂN XẾP

Cấu trúc dữ liệu và thuật toán -CHƯƠNG II CẤU TRÚC DỮ LIỆU-NGĂN XẾP

2.1. Cấu trúc dữ liệu ngăn xếp

Một ngăn xếp là một cấu trúc dữ liệu tuyến tính tuân theo nguyên tắc Vào sau ra trước (LIFO). Điều này có nghĩa là phần tử cuối cùng được chèn vào bên trong ngăn xếp sẽ được lấy ra trước.

Bạn có thể nghĩ về cấu trúc dữ liệu ngăn xếp như một chồng đĩa chồng lên nhau.

Biểu diễn ngăn xếp tương tự như một đống đĩa

Ở đây, bạn có thể:

1. Đặt một đĩa mới lên trên
2. Lấy đĩa trên cùng ra

Và nếu bạn muốn có đĩa ở dưới cùng, trước tiên bạn phải loại bỏ tất cả các đĩa ở trên cùng. Đây chính xác là cách cấu trúc dữ liệu ngăn xếp hoạt động.

2.1.1.Nguyên lý LIFO của ngăn xếp

Trong thuật ngữ lập trình, việc đặt một phần tử lên đầu ngăn xếp được gọi là Push (Đẩy) và việc xóa một phần tử được gọi là Pop (Xoá).

Các thao tác đẩy và bật ngăn xếp

Trong hình ảnh trên, mặc dù mục 3 được giữ lại cuối cùng, nhưng nó đã bị xóa đầu tiên. Đây chính xác là cách Nguyên tắc LIFO (Vào sau ra trước) hoạt động.

Chúng ta có thể triển khai ngăn xếp trong bất kỳ ngôn ngữ lập trình nào như C, C++, Java, Python hoặc C#, nhưng thông số kỹ thuật thì khá giống nhau.

2.1.2.Các hoạt động cơ bản của Ngăn xếp:

Có một số thao tác cơ bản cho phép chúng ta thực hiện các hành động khác nhau trên một ngăn xếp.

1. Push: Thêm một phần tử vào đầu ngăn xếp
2. Pop: Xóa một phần tử khỏi đầu ngăn xếp
3. IsEmpty: Kiểm tra xem ngăn xếp có rỗng không
4. IsFull: Kiểm tra xem ngăn xếp có đầy không
5. Peek: Lấy giá trị của phần tử trên cùng mà không xóa nó

2.1.3.Hoạt động của cấu trúc dữ liệu ngăn xếp

Các hoạt động diễn ra như sau:

1. Con trỏ có tên TOP được sử dụng để theo dõi phần tử trên cùng trong ngăn xếp.
2. Khi khởi tạo ngăn xếp, chúng ta đặt giá trị của nó thành -1 để chúng ta có thể kiểm tra xem ngăn xếp có trống không bằng cách so sánh TOP == -1.
3. Khi đẩy một phần tử, chúng ta tăng giá trị của TOP và đặt phần tử mới vào vị trí được TOP trỏ tới.
4. Khi bật một phần tử, chúng ta trả về phần tử được TOP trỏ tới và giảm giá trị của nó.
5. Trước khi đẩy (Push), chúng ta kiểm tra xem ngăn xếp đã đầy chưa
6. Trước khi xoá(Pop), chúng ta kiểm tra xem ngăn xếp đã trống chưa

Hoạt động của cấu trúc dữ liệu ngăn xếp

2.1.4. Triển khai Ngăn xếp trong Python, Java, C và C++

Python

# Stack implementation in python

# Creating a stack
def create_stack():
    stack = []
    return stack

# Creating an empty stack
def check_empty(stack):
    return len(stack) == 0

# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)

# Removing an element from the stack
def pop(stack):
    if (check_empty(stack)):
        return "stack is empty"

    return stack.pop()

stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("popped item: " + pop(stack))
print("stack after popping an element: " + str(stack))
 

Java

// Stack implementation in Java

class Stack {
  private int arr[];
  private int top;
  private int capacity;

  // Creating a stack
  Stack(int size) {
    arr = new int[size];
    capacity = size;
    top = -1;
  }

  // Add elements into stack
  public void push(int x) {
    if (isFull()) {
      System.out.println("OverFlow\nProgram Terminated\n");
      System.exit(1);
    }

    System.out.println("Inserting " + x);
    arr[++top] = x;
  }

  // Remove element from stack
  public int pop() {
    if (isEmpty()) {
      System.out.println("STACK EMPTY");
      System.exit(1);
    }
    return arr[top--];
  }

  // Utility function to return the size of the stack
  public int size() {
    return top + 1;
  }

  // Check if the stack is empty
  public Boolean isEmpty() {
    return top == -1;
  }

  // Check if the stack is full
  public Boolean isFull() {
    return top == capacity - 1;
  }

  public void printStack() {
    for (int i = 0; i <= top; i++) {
      System.out.println(arr[i]);
    }
  }

  public static void main(String[] args) {
    Stack stack = new Stack(5);

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    stack.pop();
    System.out.println("\nAfter popping out");

    stack.printStack();

  }
}
 

#C

// Stack implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int count = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("STACK FULL");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("\n STACK EMPTY \n");
  } else {
    printf("Item popped= %d", s->items[s->top]);
    s->top--;
  }
  count--;
  printf("\n");
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < count; i++) {
    printf("%d ", s->items[i]);
  }
  printf("\n");
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  printf("\nAfter popping out\n");
  printStack(s);
}
 

#C++

// Stack implementation in C++

#include <stdlib.h>
#include <iostream>

using namespace std;

#define MAX 10
int size = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    cout << "STACK FULL";
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  size++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    cout << "\n STACK EMPTY \n";
  } else {
    cout << "Item popped= " << s->items[s->top];
    s->top--;
  }
  size--;
  cout << endl;
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < size; i++) {
    cout << s->items[i] << " ";
  }
  cout << endl;
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  cout << "\nAfter popping out\n";
  printStack(s);
}

Độ phức tạp của thời gian ngăn xếp

Đối với việc triển khai ngăn xếp dựa trên mảng, các thao tác đẩy và lấy ra mất thời gian không đổi, tức là O(1).

Ứng dụng của cấu trúc dữ liệu ngăn xếp

Mặc dù stack là một cấu trúc dữ liệu đơn giản để triển khai, nhưng nó rất mạnh mẽ. Những cách sử dụng phổ biến nhất của stack là:

1. Để đảo ngược một từ - Đặt tất cả các chữ cái vào một chồng và bật chúng ra. Do thứ tự LIFO của chồng, bạn sẽ nhận được các chữ cái theo thứ tự đảo ngược.
2. Trong trình biên dịch - Trình biên dịch sử dụng chồng để tính giá trị của các biểu thức như 2 + 4 / 5 * (7 - 9) bằng cách chuyển đổi biểu thức sang dạng tiền tố hoặc hậu tố.
3. Trong trình duyệt - Nút quay lại trong trình duyệt lưu tất cả các URL bạn đã truy cập trước đó vào một chồng. Mỗi lần bạn truy cập một trang mới, trang đó sẽ được thêm vào đầu chồng. Khi bạn nhấn nút quay lại, URL hiện tại sẽ bị xóa khỏi chồng và URL trước đó sẽ được truy cập.

ĐỌC CHƯƠNG I CẤU TRÚC DỮ LIỆU & THUẬT TOÁN TẠI ĐÂY :

1.Cấu trúc dữ liệu và thuật toán -CHƯƠNG I :Giới thiệu DSA

2.Cấu trúc dữ liệu và thuật toán -CHƯƠNG I :Giới thiệu DSA (tiếp theo...)

3.Cấu trúc dữ liệu và thuật toán -CHƯƠNG I :Giới thiệu DSA (Phần 3...)