Trang chủ Data structures vs algorithms - Cấu trúc dữ liệu Giới thiệu về cấu trúc dữ liệu Stack

Data structures vs algorithms - Cấu trúc dữ liệu

[CTDL] Giới thiệu về cấu trúc dữ liệu Stack

Stack Data Structure (Introduction and Program)

Bởi

8 Tháng Mười, 2020

2395

🔥CHỌN LỌC TOP NHỮNG KHOÁ HỌC LẬP TRÌNH ONLINE NHIỀU NGƯỜI THEO HOC TẠI ĐÂY🔥

Chào ace, phần tiếp theo trong series tự học về cấu trúc dữ liệu và giải thuật đó là Stack, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng…) về nó cho ace.

Nội dung chính

1. Khái niệm về Stack

Stack là một cấu trúc dữ liệu tuyến tính với các hoạt động được thực hiện theo một thứ tự cụ thể. Thứ tự có thể là LIFO (Last In First Out – vào sau lại ra trước) hoặc FILO (First In Last Out – vào đầu tiên nhưng ra lại sau cùng). Hiểu đơn giản hơn, Stack là ngăn xếp, bạn có thể tưởng tượng nó như một chồng sách và sách nào để lên sau cùng sẽ được lấy ra trước…

Chủ yếu Stack có ba hàm cơ bản sau được thực hiện:

Push: Thêm một mục(phần tử, thành phần) trong stack. Nếu stack đầy, thì nó được cho là điều kiện Tràn.
Pop: Loại bỏ một mục khỏi stack. Các mục được xuất hiện theo thứ tự đảo ngược mà chúng được Push. Nếu stack trống, thì nó được cho là điều kiện trống.
Peek hoặc Top: Trả về phần tử trên cùng của stack.
isEmpty: Trả về true nếu stack trống, ngược lại là false.

2. Cách hoạt động của một stack trong thực tế như thế nào?

Có rất nhiều ví dụ thực tế về ngăn xếp. Hãy xem xét ví dụ đơn giản về những chiếc đĩa xếp chồng lên nhau trong căng tin. Đĩa ở trên cùng là đĩa đầu tiên được lấy ra, tức là đĩa được đặt ở vị trí dưới cùng vẫn nằm trong ngăn xếp trong khoảng thời gian dài nhất. Vì vậy, có thể thấy đơn giản, stack làm theo thứ tự LIFO / FILO. Cái đĩa nào vào trước sẽ ra sau cùng, hoặc cái nào vào sau cùng sẽ được lấy ra đầu tiên.

3. Độ phức tạp của các hàm trong Stack

push(), pop(), isEmpty() và peek() đều mất O(1) thời gian. Chúng ta không chạy bất kỳ vòng lặp nào trong bất kỳ hàm nào trong số này.

4. Ứng dụng của Stack là gì?

Chuyển đổi Infix to Postfix
Tính năng undo(hoàn lại) ở nhiều nơi như chỉnh sửa, photoshop.
Tính năng chuyển tiếp và lùi trong trình duyệt web
Được sử dụng trong nhiều thuật toán như Tower of Hanoi, duyệt cây, bài toán nhịp cổ phiếu, bài toán biểu đồ.
Các ứng dụng khác có thể là Backtracking, Knight tour problem, N queen problem và sudoku solver
Trong các thuật toán đồ thị như Sắp xếp theo cấu trúc liên kết và các thành phần được kết nối mạnh mẽ

5. Cách xây dựng một stack

Có hai cách để triển khai và xây dựng một stack đó là:

Sử dụng mảng
Sử dụng danh sách liên kết

5.1 Cài đặt Stack sử dụng mảng


// C program for array implementation of stack 
#include <limits.h> 
#include <stdio.h> 
#include <stdlib.h> 
  
// A structure to represent a stack 
struct Stack { 
    int top; 
    unsigned capacity; 
    int* array; 
}; 
  
// function to create a stack of given capacity. It initializes size of 
// stack as 0 
struct Stack* createStack(unsigned capacity) 
{ 
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); 
    stack->capacity = capacity; 
    stack->top = -1; 
    stack->array = (int*)malloc(stack->capacity * sizeof(int)); 
    return stack; 
} 
  
// Stack is full when top is equal to the last index 
int isFull(struct Stack* stack) 
{ 
    return stack->top == stack->capacity - 1; 
} 
  
// Stack is empty when top is equal to -1 
int isEmpty(struct Stack* stack) 
{ 
    return stack->top == -1; 
} 
  
// Function to add an item to stack.  It increases top by 1 
void push(struct Stack* stack, int item) 
{ 
    if (isFull(stack)) 
        return; 
    stack->array[++stack->top] = item; 
    printf("%d pushed to stack\n", item); 
} 
  
// Function to remove an item from stack.  It decreases top by 1 
int pop(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top--]; 
} 
  
// Function to return the top from stack without removing it 
int peek(struct Stack* stack) 
{ 
    if (isEmpty(stack)) 
        return INT_MIN; 
    return stack->array[stack->top]; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    struct Stack* stack = createStack(100); 
  
    push(stack, 10); 
    push(stack, 20); 
    push(stack, 30); 
  
    printf("%d popped from stack\n", pop(stack)); 
  
    return 0; 
}

C++


/* C++ program to implement basic stack 
   operations */
#include <bits/stdc++.h> 
  
using namespace std; 
  
#define MAX 1000 
  
class Stack { 
    int top; 
  
public: 
    int a[MAX]; // Maximum size of Stack 
  
    Stack() { top = -1; } 
    bool push(int x); 
    int pop(); 
    int peek(); 
    bool isEmpty(); 
}; 
  
bool Stack::push(int x) 
{ 
    if (top >= (MAX - 1)) { 
        cout << "Stack Overflow"; 
        return false; 
    } 
    else { 
        a[++top] = x; 
        cout << x << " pushed into stack\n"; 
        return true; 
    } 
} 
  
int Stack::pop() 
{ 
    if (top < 0) { 
        cout << "Stack Underflow"; 
        return 0; 
    } 
    else { 
        int x = a[top--]; 
        return x; 
    } 
} 
int Stack::peek() 
{ 
    if (top < 0) { 
        cout << "Stack is Empty"; 
        return 0; 
    } 
    else { 
        int x = a[top]; 
        return x; 
    } 
} 
  
bool Stack::isEmpty() 
{ 
    return (top < 0); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    class Stack s; 
    s.push(10); 
    s.push(20); 
    s.push(30); 
    cout << s.pop() << " Popped from stack\n"; 
  
    return 0; 
}

Java


/* Java program to implement basic stack 
operations */
class Stack { 
    static final int MAX = 1000; 
    int top; 
    int a[] = new int[MAX]; // Maximum size of Stack 
  
    boolean isEmpty() 
    { 
        return (top < 0); 
    } 
    Stack() 
    { 
        top = -1; 
    } 
  
    boolean push(int x) 
    { 
        if (top >= (MAX - 1)) { 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else { 
            a[++top] = x; 
            System.out.println(x + " pushed into stack"); 
            return true; 
        } 
    } 
  
    int pop() 
    { 
        if (top < 0) { 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else { 
            int x = a[top--]; 
            return x; 
        } 
    } 
  
    int peek() 
    { 
        if (top < 0) { 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else { 
            int x = a[top]; 
            return x; 
        } 
    } 
} 
  
// Driver code 
class Main { 
    public static void main(String args[]) 
    { 
        Stack s = new Stack(); 
        s.push(10); 
        s.push(20); 
        s.push(30); 
        System.out.println(s.pop() + " Popped from stack"); 
    } 
}

Python


# Python program for implementation of stack 
  
# import maxsize from sys module  
# Used to return -infinite when stack is empty 
from sys import maxsize 
  
# Function to create a stack. It initializes size of stack as 0 
def createStack(): 
    stack = [] 
    return stack 
  
# Stack is empty when stack size is 0 
def isEmpty(stack): 
    return len(stack) == 0
  
# Function to add an item to stack. It increases size by 1 
def push(stack, item): 
    stack.append(item) 
    print(item + " pushed to stack ") 
      
# Function to remove an item from stack. It decreases size by 1 
def pop(stack): 
    if (isEmpty(stack)): 
        return str(-maxsize -1) # return minus infinite 
      
    return stack.pop() 
  
# Function to return the top from stack without removing it 
def peek(stack): 
    if (isEmpty(stack)): 
        return str(-maxsize -1) # return minus infinite 
    return stack[len(stack) - 1] 
  
# Driver program to test above functions     
stack = createStack() 
push(stack, str(10)) 
push(stack, str(20)) 
push(stack, str(30)) 
print(pop(stack) + " popped from stack")


// C# program to implement basic stack 
// operations 
using System; 
  
namespace ImplementStack { 
class Stack { 
    private int[] ele; 
    private int top; 
    private int max; 
    public Stack(int size) 
    { 
        ele = new int[size]; // Maximum size of Stack 
        top = -1; 
        max = size; 
    } 
  
    public void push(int item) 
    { 
        if (top == max - 1) { 
            Console.WriteLine("Stack Overflow"); 
            return; 
        } 
        else { 
            ele[++top] = item; 
        } 
    } 
  
    public int pop() 
    { 
        if (top == -1) { 
            Console.WriteLine("Stack is Empty"); 
            return -1; 
        } 
        else { 
            Console.WriteLine("{0} popped from stack ", ele[top]); 
            return ele[top--]; 
        } 
    } 
  
    public int peek() 
    { 
        if (top == -1) { 
            Console.WriteLine("Stack is Empty"); 
            return -1; 
        } 
        else { 
            Console.WriteLine("{0} popped from stack ", ele[top]); 
            return ele[top]; 
        } 
    } 
  
    public void printStack() 
    { 
        if (top == -1) { 
            Console.WriteLine("Stack is Empty"); 
            return; 
        } 
        else { 
            for (int i = 0; i <= top; i++) { 
                Console.WriteLine("{0} pushed into stack", ele[i]); 
            } 
        } 
    } 
} 
  
// Driver program to test above functions 
class Program { 
    static void Main() 
    { 
        Stack p = new Stack(5); 
  
        p.push(10); 
        p.push(20); 
        p.push(30); 
        p.printStack(); 
        p.pop(); 
    } 
} 
}

Ưu điểm: Dễ thực hiện. Bộ nhớ được lưu vì con trỏ không liên quan.
Nhược điểm: Nó không năng động. Nó không phát triển và thu nhỏ tùy theo nhu cầu trong thời gian chạy.

Kết quả

10 pushed into stack
20 pushed into stack
30 pushed into stack
30 popped from stack

5.2 Cài đặt Stack sử dụng danh sách liên kết


// C program for linked list implementation of stack 
#include <limits.h> 
#include <stdio.h> 
#include <stdlib.h> 
  
// A structure to represent a stack 
struct StackNode { 
    int data; 
    struct StackNode* next; 
}; 
  
struct StackNode* newNode(int data) 
{ 
    struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode)); 
    stackNode->data = data; 
    stackNode->next = NULL; 
    return stackNode; 
} 
  
int isEmpty(struct StackNode* root) 
{ 
    return !root; 
} 
  
void push(struct StackNode** root, int data) 
{ 
    struct StackNode* stackNode = newNode(data); 
    stackNode->next = *root; 
    *root = stackNode; 
    printf("%d pushed to stack\n", data); 
} 
  
int pop(struct StackNode** root) 
{ 
    if (isEmpty(*root)) 
        return INT_MIN; 
    struct StackNode* temp = *root; 
    *root = (*root)->next; 
    int popped = temp->data; 
    free(temp); 
  
    return popped; 
} 
  
int peek(struct StackNode* root) 
{ 
    if (isEmpty(root)) 
        return INT_MIN; 
    return root->data; 
} 
  
int main() 
{ 
    struct StackNode* root = NULL; 
  
    push(&root, 10); 
    push(&root, 20); 
    push(&root, 30); 
  
    printf("%d popped from stack\n", pop(&root)); 
  
    printf("Top element is %d\n", peek(root)); 
  
    return 0; 
}

C++

// C++ program for linked list implementation of stack 
#include <bits/stdc++.h> 
using namespace std; 
  
// A structure to represent a stack 
class StackNode { 
public: 
    int data; 
    StackNode* next; 
}; 
  
StackNode* newNode(int data) 
{ 
    StackNode* stackNode = new StackNode(); 
    stackNode->data = data; 
    stackNode->next = NULL; 
    return stackNode; 
} 
  
int isEmpty(StackNode* root) 
{ 
    return !root; 
} 
  
void push(StackNode** root, int data) 
{ 
    StackNode* stackNode = newNode(data); 
    stackNode->next = *root; 
    *root = stackNode; 
    cout << data << " pushed to stack\n"; 
} 
  
int pop(StackNode** root) 
{ 
    if (isEmpty(*root)) 
        return INT_MIN; 
    StackNode* temp = *root; 
    *root = (*root)->next; 
    int popped = temp->data; 
    free(temp); 
  
    return popped; 
} 
  
int peek(StackNode* root) 
{ 
    if (isEmpty(root)) 
        return INT_MIN; 
    return root->data; 
} 
  
int main() 
{ 
    StackNode* root = NULL; 
  
    push(&root, 10); 
    push(&root, 20); 
    push(&root, 30); 
  
    cout << pop(&root) << " popped from stack\n"; 
  
    cout << "Top element is " << peek(root) << endl; 
  
    return 0; 
}

Java


// Java Code for Linked List Implementation 
  
public class StackAsLinkedList { 
  
    StackNode root; 
  
    static class StackNode { 
        int data; 
        StackNode next; 
  
        StackNode(int data) 
        { 
            this.data = data; 
        } 
    } 
  
    public boolean isEmpty() 
    { 
        if (root == null) { 
            return true; 
        } 
        else
            return false; 
    } 
  
    public void push(int data) 
    { 
        StackNode newNode = new StackNode(data); 
  
        if (root == null) { 
            root = newNode; 
        } 
        else { 
            StackNode temp = root; 
            root = newNode; 
            newNode.next = temp; 
        } 
        System.out.println(data + " pushed to stack"); 
    } 
  
    public int pop() 
    { 
        int popped = Integer.MIN_VALUE; 
        if (root == null) { 
            System.out.println("Stack is Empty"); 
        } 
        else { 
            popped = root.data; 
            root = root.next; 
        } 
        return popped; 
    } 
  
    public int peek() 
    { 
        if (root == null) { 
            System.out.println("Stack is empty"); 
            return Integer.MIN_VALUE; 
        } 
        else { 
            return root.data; 
        } 
    } 
  
    public static void main(String[] args) 
    { 
  
        StackAsLinkedList sll = new StackAsLinkedList(); 
  
        sll.push(10); 
        sll.push(20); 
        sll.push(30); 
  
        System.out.println(sll.pop() + " popped from stack"); 
  
        System.out.println("Top element is " + sll.peek()); 
    } 
}

Python

# Python program for linked list implementation of stack 
  
# Class to represent a node 
class StackNode: 
  
    # Constructor to initialize a node 
    def __init__(self, data): 
        self.data = data  
        self.next = None
  
class Stack: 
      
    # Constructor to initialize the root of linked list 
    def __init__(self): 
        self.root = None
  
    def isEmpty(self): 
        return True if self.root is None else  False 
  
    def push(self, data): 
        newNode = StackNode(data) 
        newNode.next = self.root  
        self.root = newNode 
        print "% d pushed to stack" %(data) 
      
    def pop(self): 
        if (self.isEmpty()): 
            return float("-inf") 
        temp = self.root  
        self.root = self.root.next 
        popped = temp.data 
        return popped 
      
    def peek(self): 
        if self.isEmpty(): 
            return float("-inf") 
        return self.root.data 
  
# Driver program to test above class  
stack = Stack() 
stack.push(10)         
stack.push(20) 
stack.push(30) 
  
print "% d popped from stack" %(stack.pop()) 
print "Top element is % d " %(stack.peek())

// C# Code for Linked List Implementation 
using System; 
  
public class StackAsLinkedList { 
  
    StackNode root; 
  
    public class StackNode { 
        public int data; 
        public StackNode next; 
  
        public StackNode(int data) 
        { 
            this.data = data; 
        } 
    } 
  
    public bool isEmpty() 
    { 
        if (root == null) { 
            return true; 
        } 
        else
            return false; 
    } 
  
    public void push(int data) 
    { 
        StackNode newNode = new StackNode(data); 
  
        if (root == null) { 
            root = newNode; 
        } 
        else { 
            StackNode temp = root; 
            root = newNode; 
            newNode.next = temp; 
        } 
        Console.WriteLine(data + " pushed to stack"); 
    } 
  
    public int pop() 
    { 
        int popped = int.MinValue; 
        if (root == null) { 
            Console.WriteLine("Stack is Empty"); 
        } 
        else { 
            popped = root.data; 
            root = root.next; 
        } 
        return popped; 
    } 
  
    public int peek() 
    { 
        if (root == null) { 
            Console.WriteLine("Stack is empty"); 
            return int.MinValue; 
        } 
        else { 
            return root.data; 
        } 
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
  
        StackAsLinkedList sll = new StackAsLinkedList(); 
  
        sll.push(10); 
        sll.push(20); 
        sll.push(30); 
  
        Console.WriteLine(sll.pop() + " popped from stack"); 
  
        Console.WriteLine("Top element is " + sll.peek()); 
    } 
}

Kết quả:

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20

Ưu điểm: Việc triển khai danh sách liên kết của ngăn xếp có thể phát triển và thu nhỏ theo nhu cầu trong thời gian chạy.
Nhược điểm: Yêu cầu thêm bộ nhớ do sự tham gia của con trỏ.

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

Chào thân ái và quyết thắng!

[CTDL] Giới thiệu về cấu trúc dữ liệu Stack

1. Khái niệm về Stack

2. Cách hoạt động của một stack trong thực tế như thế nào?

3. Độ phức tạp của các hàm trong Stack

4. Ứng dụng của Stack là gì?

5. Cách xây dựng một stack

5.1 Cài đặt Stack sử dụng mảng

5.2 Cài đặt Stack sử dụng danh sách liên kết

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!

BÀI VIẾT TIÊU BIỂU

Học JavaScript từ cơ bản đến nâng cao | Hiểu về...

Học JavaScript từ cơ bản đến nâng cao | Chi sẻ...

Học JavaScript từ cơ bản đến nâng cao | Top các...

BÀI VIẾT PHỔ BIẾN

Tổng hợp toàn bộ tài liệu học hướng đối tượng và...

[Tự học C++] Số dấu phẩy động(float, double,…) trong C++

Tổng hợp và chọn lọc bài tập SQL full hướng dẫn...

MỤC XEM NHIỀU