Chuyển tới nội dung

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

  • bởi

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.

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

// 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 stackn”, 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 stackn”, 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 stackn”; 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 stackn”; 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)) { Tanggiap.nettln(“Stack Overflow”); return false; } else { a[++top] = x; Tanggiap.nettln(x + ” pushed into stack”); return true; } } int pop() { if (top < 0) { Tanggiap.nettln(“Stack Underflow”); return 0; } else { int x = a[top-]; return x; } } int peek() { if (top < 0) { Tanggiap.nettln(“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); Tanggiap.nettln(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): Tanggiap.netnd(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 Tanggiap.net() # 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#

// 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) { Tanggiap.neteLine(“Stack Overflow”); return; } else { ele[++top] = item; } } public int pop() { if (top == -1) { Tanggiap.neteLine(“Stack is Empty”); return -1; } else { Tanggiap.neteLine(“{0} popped from stack “, ele[top]); return ele[top-]; } } public int peek() { if (top == -1) { Tanggiap.neteLine(“Stack is Empty”); return -1; } else { Tanggiap.neteLine(“{0} popped from stack “, ele[top]); return ele[top]; } } public void printStack() { if (top == -1) { Tanggiap.neteLine(“Stack is Empty”); return; } else { for (int i = 0; i <= top; i++) { Tanggiap.neteLine(“{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

// 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 stackn”, 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 stackn”, pop(&root)); printf(“Top element is %dn”, 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 stackn”; } 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 stackn”; 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) { Tanggiap.net = 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; Tanggiap.net = temp; } Tanggiap.nettln(data + ” pushed to stack”); } public int pop() { int popped = Tanggiap.net_VALUE; if (root == null) { Tanggiap.nettln(“Stack is Empty”); } else { popped = Tanggiap.net; root = Tanggiap.net; } return popped; } public int peek() { if (root == null) { Tanggiap.nettln(“Stack is empty”); return Tanggiap.net_VALUE; } else { return Tanggiap.net; } } public static void main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); Tanggiap.net(10); Tanggiap.net(20); Tanggiap.net(30); Tanggiap.nettln(sll.pop() + ” popped from stack”); Tanggiap.nettln(“Top element is ” + Tanggiap.net()); } }

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): Tanggiap.net = data Tanggiap.net = None class Stack: # Constructor to initialize the root of linked list def __init__(self): Tanggiap.net = None def isEmpty(self): return True if Tanggiap.net is None else False def push(self, data): newNode = StackNode(data) Tanggiap.net = Tanggiap.net Tanggiap.net = newNode print “% d pushed to stack” %(data) def pop(self): if (self.isEmpty()): return float(“-inf”) temp = Tanggiap.net Tanggiap.net = Tanggiap.net popped = Tanggiap.net return popped def peek(self): if Tanggiap.netpty(): return float(“-inf”) return Tanggiap.net # Driver program to test above class stack = Stack() Tanggiap.net(10) Tanggiap.net(20) Tanggiap.net(30) print “% d popped from stack” %(stack.pop()) print “Top element is % d ” %(stack.peek())

C#

// 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) { Tanggiap.net = 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; Tanggiap.net = temp; } Tanggiap.neteLine(data + ” pushed to stack”); } public int pop() { int popped = Tanggiap.netalue; if (root == null) { Tanggiap.neteLine(“Stack is Empty”); } else { popped = Tanggiap.net; root = Tanggiap.net; } return popped; } public int peek() { if (root == null) { Tanggiap.neteLine(“Stack is empty”); return Tanggiap.netalue; } else { return Tanggiap.net; } } // Driver code public static void Main(String[] args) { StackAsLinkedList sll = new StackAsLinkedList(); Tanggiap.net(10); Tanggiap.net(20); Tanggiap.net(30); Tanggiap.neteLine(sll.pop() + ” popped from stack”); Tanggiap.neteLine(“Top element is ” + Tanggiap.net()); } }

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:

  • w3schools
  • Geeksforgeeks
  • codechef
  • dev.to

Tài liệu từ cafedev:

  • Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
  • Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
  • Các series tự học lập trình khác

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:

  • Group Facebook
  • Fanpage
  • Youtube
  • Instagram
  • Twitter
  • Linkedin
  • Pinterest
  • Trang chủ

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