Đề Xuất 12/2022 # Giới Thiệu Về Cấu Trúc Dữ Liệu Stack / 2023 # Top 16 Like | Comforttinhdauthom.com

Đề Xuất 12/2022 # Giới Thiệu Về Cấu Trúc Dữ Liệu Stack / 2023 # Top 16 Like

Cập nhật nội dung chi tiết về Giới Thiệu Về Cấu Trúc Dữ Liệu Stack / 2023 mới nhất trên website Comforttinhdauthom.com. Hy vọng thông tin trong bài viết sẽ đáp ứng được nhu cầu ngoài mong đợi của bạn, chúng tôi sẽ làm việc thường xuyên để cập nhật nội dung mới nhằm giúp bạn nhận được thông tin nhanh chóng và chính xác nhất.

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

struct Stack { int top; unsigned capacity; int* array; }; struct Stack* createStack(unsigned capacity) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); return stack; } int isFull(struct Stack* stack) { } int isEmpty(struct Stack* stack) { } void push(struct Stack* stack, int item) { if (isFull(stack)) return; printf("%d pushed to stackn", item); } int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; } int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; } 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 */ using namespace std; #define MAX 1000 class Stack { int top; public: int a[MAX]; Stack() { top = -1; } bool push(int x); int pop(); int peek(); bool isEmpty(); }; bool Stack::push(int x) { 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); } 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]; boolean isEmpty() { return (top < 0); } Stack() { top = -1; } boolean push(int x) { 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; } } } 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#

using System; namespace ImplementStack { class Stack { private int[] ele; private int top; private int max; public Stack(int size) { ele = new int[size]; 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]); } } } } class Program { static void Main() { Stack p = new Stack(5); p.push(10); p.push(20); p.push(30); p.printStack(); p.pop(); } } }

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

struct StackNode { int data; struct StackNode* next; }; struct StackNode* newNode(int data) { struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode)); return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data); *root = stackNode; printf("%d pushed to stackn", data); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN; struct StackNode* temp = *root; free(temp); return popped; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN; } 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++

using namespace std; class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); return stackNode; } int isEmpty(StackNode* root) { return !root; } void push(StackNode** root, int data) { StackNode* stackNode = newNode(data); *root = stackNode; cout << data << " pushed to stackn"; } int pop(StackNode** root) { if (isEmpty(*root)) return INT_MIN; StackNode* temp = *root; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return INT_MIN; } 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

public class StackAsLinkedList { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { chúng tôi = 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; chúng tôi = 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): chúng tôi = data chúng tôi = None class Stack: # Constructor to initialize the root of linked list def __init__(self): chúng tôi = None def isEmpty(self): return True if chúng tôi is None else False def push(self, data): newNode = StackNode(data) chúng tôi = chúng tôi chúng tôi = newNode print "% d pushed to stack" %(data) def pop(self): if (self.isEmpty()): return float("-inf") temp = chúng tôi chúng tôi = chúng tôi popped = chúng tôi return popped def peek(self): if self.isEmpty(): return float("-inf") return chúng tôi # 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#

using System; public class StackAsLinkedList { StackNode root; public class StackNode { public int data; public StackNode next; public StackNode(int data) { chúng tôi = 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; chúng tôi = 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; } } 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ỏ.

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!

Stack Và Queue Trong Cấu Trúc Dữ Liệu / 2023

Cấu trúc dữ liệu có thật sự quan trọng?

Ở thời đại công nghệ số, lượng dữ liệu được sinh ra và trao đổi ngày càng tăng cao. Nếu không được lưu trữ một cách khoa học thì việc truy vẫn đến dữ liệu về sau này sẽ vô cùng khó khăn.

Mỗi máy tính đều có giới hạn nhất định về bộ vi xử lý. Mặc dù hàng triệu phép tính có thể được giải quyết trong vòng một giây nhưng khi bài toán cần giải quyết trở nên phức tạp với hàng tỉ phép tính thì việc tổ chức dữ liệu vẫn cực kỳ quan trọng.

Bởi vậy, có thể nói cấu trúc dữ liệu đóng vai trò chủ chốt trong các ứng dụng, phần mềm… hiện nay.

Định nghĩa

Có nhiều loại cấu trúc dữ liệu, ví dụ như danh sách liên kết (linked list), cây (tree), đồ thị (graph), … Trong bài này, mình sẽ giới thiệu với mọi người 2 loại cấu trúc dữ liệu mà thường được sử dụng nhất đó là ngăn xếp (stack) và hàng đợi (queue).

Stack

Giới thiệu stack

Stack, được hiểu theo nghĩa Tiếng Việt là ngăn xếp, xếp chồng. Đây là cấu trúc dữ liệu hoạt động theo nguyên tắc: vào sau ra trước (Last in first out – LIFO). Để trực quan, các bạn có thể hiểu nó là một chồng bát, bạn chồng các chiếc bát lên cao thì chiếc bạn chồng vào sau cùng sẽ là chiếc bạn lấy ra đầu tiên và ngược lại, chiếc bát đầu tiên, ở dưới cùng sẽ là chiếc bạn lấy ra sau cùng. Các thao tác với cấu trúc dữ liệu kiểu stack là:

push: thêm bản ghi, tương tự với việc bạn thêm một chiếc bát vào chồng.

pop: lấy bản ghi, tương tự lấy bát ra khỏi chồng

length: trả về số lượng bản ghi, tương ứng với chiều cao chồng bát.

peak: trở về bản ghi đầu tiên, tương ứng với việc bạn chạm tay vào chiếc bát trên cùng

Ứng dụng của stack:

Chuyển đổi số thập phân sang nhị phân: Khi chuyển đổi số thập phân sang nhị phân, chúng ta sẽ thưc hiện thao tác chia số thập phân này cho 2 và viết phần dư ngược lại thứ tự mà nó được sinh ra. Sử dụng stack, ta lưu lần lượt phần dư sau mỗi lần chia và sau khi kết thúc thao tác chia, đọc stack vừa rồi sẽ cho ra biểu diễn nhị phân cần tìm.

Tính giá trị biểu thức đại số hậu tố: Biểu thức đại số hậu tố là biểu thức có toán tử nằm sau 2 toán hạng của nó, cũng không có dấu ngoặc. Ví dụ như biểu thức hậu tố của ((4 + 2) / 3) + 5 sẽ là 4 2 + 3 / 5 +. Đầu tiên, duyệt biểu thức theo thứ tự từ trái sang phải, khi gặp toán hạng thì đẩy vào stack. Sau đó, khi gặp toán tử, ta lấy 2 toán hạng trên cùng trong stack ra và thực hiện phép toán rồi lại đẩy kết quả vào stack. Đối với ví dụ này, các thao tác được thực hiện là:

Kết quả cuối cùng là 7.

Queue

Giới thiệu queue

Queue, được hiểu là hàng đợi và là cấu trúc dữ liệu hoạt động theo nguyên tắc: vào trước ra trước (First in first out – FIFO). Một cách trực quan thì các bạn có thể liên tưởng đến lúc bạn xếp hàng mua vé xem phim, ai đến xếp hàng trước thì sẽ được bán vé trước và tương tự, ai xếp hàng sau thì sẽ được phục vụ sau. Các thao tác với cấu trúc dữ liệu queue:

EnQueue: Thêm một bản ghi vào cuối hàng đợi, tương tự như việc có thêm người đến xếp hàng đợi mua vé.

DeQueue: Lấy ra bản ghi đầu tiên, tương tự việc người đứng đầu hàng đang được nhân viên bán vé.

IsEmpty: Kiểm tra hàng đợi có rỗng hay không, tương tự việc người khác hỏi bạn xem có ai đang xếp hàng mua vé hay không và bạn trả lời.

Front: Trở về bản ghi đầu tiên

Ứng dụng của queue

Kiểm tra chuỗi Palindrome: Một chuỗi được gọi là có tính chất Palindrome nếu nó có tính chât đối xứng, tức là viết xuôi cũng giống viết ngược, ví dụ như “aaAaa”. Để kiểm tra tính chất này của một chuỗi bất kì, ta đọc chuỗi bởi 2 cấu trúc riêng biệt là stack và queue. Sau đó, lấy ra từng phần tử trong stack và queue để so sánh với nhau. Nếu tất cả các phần tử trong stack đều giống với phần tử trong queue ở vị trí tương ứng thì chuỗi đó có tính chất Palindrome.

Amazon Web Services là gì?

Amazon Web Services hay AWS là nền tảng dịch vụ công nghệ thông tin điện toán đám mây toàn diện với các dịch vụ cho thuê máy chủ, lưu trữ cơ sở dữ liệu, hạ tầng mạng, phân phối nội dung và nhiều giải pháp phần mềm khác giúp nhà phát triển phần mềm cũng như doanh nghiệp triển khai và mở rộng hệ thống thông tin dễ dàng và nhanh chóng.

Các dịch vụ AWS đưa đưa ra vào năm 2006 với mục đích ban đầu để quản lý và điều hành hoạt động bán hàng online của website chúng tôi Sau đó, AWS chính là công ty đầu tiên tiên phong dịch vụ điện toán đám mấy với khái niệm pay-as-you-go trên nền tảng AWS này, tức là doanh nghiệp chỉ trả chi phí thực sự với nhu cầu bạn sử dụng, giúp doanh nghiệp dễ dàng đầu tư cũng như mở rộng hạ tầng công nghệ thông tin với máy tính, dịch vụ lưu trữ dữ liệu với chi phí phù hợp và hiệu quả nhất

Trong phần này, mình sẽ không phân tích chi tiết mà chỉ nêu khái quát về vai trò của stack và queue trong 2 dịch vụ của AWS, đó là AWS CloudFormation và Amazon Simple Queue Service.

AWS CloudFormation

AWS CloudFormation là một dịch vụ hỗ trợ việc thiết lập các tài nguyên của Amazon Web Service, nhờ đó bạn chỉ cần bỏ ra ít thời gian để quản lý các tài nguyên đó và có thể tập trung vào phát triển ứng dụng chạy trên AWS. Bạn tạo ra một template (thường là các đoạn mã Json hoặc Yaml) để mô tả tài nguyên AWS mà bạn muốn (như là Amazon EC2 innstance hoặc Amazon RDS DB instance), và AWS CloudFormation xử lý việc cung cấp và thiết lập các tài nguyên đó giúp bạn. Bạn không cần thiết phải tạo, thiết lập từng tài nguyên một, cũng không cần phải quan tâm phần nào phụ thuộc vào phần nào, AWS CloudFormation sẽ làm giúp bạn.

Cấu trúc cơ bản của Amazon CloudFormation

Cấu trúc cơ bản của một Amazon CloudFormation sẽ gồm 2 phần:

Cơ chế hoạt động của Amazon CloudFormation

Vai trò của stack được thể hiện rõ ràng nhất trong bước roll-back này. Khi tạo các tài nguyên, các lệnh sẽ được đưa vào một stack. Nếu có lỗi xảy ra thì cần lần lượt xóa bỏ các tài nguyên vừa tạo, dựa vào thứ tự lệnh trong stack và quy tắc vào trước ra sau, các tài nguyên sẽ được xóa bỏ một cách an toàn nhất

Amazon Simple Queue Service

Amazon Simple Queue Service (SQS) là một dịch vụ giúp lưu trữ thông điệp (message), thường là dữ liệu văn bản, dưới dạng hàng đợi (queue). Ưu điểm của Amazon SQS là tính nhanh chóng, đáng tin cậy, có khả năng mở rộng và quản lý một cách đầy đủ.

Cấu trúc cơ bản của Amazon SQS

Cấu trúc cơ bản của một Amazon SQS sẽ gồm 3 phần:

Các thành phần của hệ thống phân tán.

Hàng đợi

Các thông điệp trong hàng đợi

Cơ chế hoạt động của Amazon SQS

Thành phần 1 gửi thông điệp A tới một hàng đợi. Hàng đợi này sẽ lưu trữ thông điệp này.

Khi thành phần nào đó trong hệ thống (ở đây là thành phần 2) sẵn sàng xử lý thông điệp thì nó sẽ gọi tới hàng đợi, lúc này, một thông điệp sẽ được trả lại (ở đây giải sử là thông điệp A).

Sau khi thành phần 2 xử lý xong thông điệp A, nó sẽ xóa A khỏi hàng đợi để tránh các thành phần sau sẽ gọi tới thông điệp này.

Ở đây, có thể thấy rõ vai trò của hàng đợi là rất quan trọng. Nó giúp sắp xếp và tổ chức các thông điệp bài bản, có trật tự, làm cho các thông điệp được xử lý theo thứ tự, thông điệp nào được gửi trước thì sẽ được xử lý trước và ngược lại. Từ đó không có thông điệp nào phải chờ quá lâu.

Thanks!

Phần AWS CloudFormation: https://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/Welcome.htmlhttps://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/cfn-whatis-concepts.htmlhttps://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/cfn-whatis-howdoesitwork.html

Phần AWS queue: https://docs.aws.amazon.com/AWSSimpleQueueService/latest/SQSDeveloperGuide/welcome.htmlhttps://docs.aws.amazon.com/AWSSimpleQueueService/latest/SQSDeveloperGuide/sqs-basic-architecture.html

All Rights Reserved

Cấu Trúc Dữ Liệu Và Giải Thuật: Ngăn Xếp (Stack) Trong Swift / 2023

1. Ngăn xếp(stack) là gì

Ngăn xếp là 1 dạng đặc biệt của danh sách liên kết mà việc bổ sung hay loại bỏ 1 phần tử đều thực hiện ở 1 đầu của danh sách gọi là đỉnh.

Ngăn xếp có 2 thao tác cơ bản: thêm phần tử vào được gọi là push và loại bỏ phần tử được gọi là pop.

Việc loại bỏ phần tử sẽ tiến hành loại bỏ phần tử mới nhất được đưa vào danh sách, chính vì tính chất này mà ngăn xếp còn được gọi là kiểu dữ liệu LIFO(last in first out – Vào sau ra trước)

2. Khởi tạo stack

2.1 . Định nghĩa kiểu dữ liệu stack

Vì stack là 1 dạng đặc biệt của danh sách liên kết nên ta có thể dùng kiểu dữ liệu Node đã trình bày ở bài danh sách liên kết để biểu diễn kiểu dữ liệu của stack

1

2

3

4

5

6

    

var

key

:

T

!

    

var

next

:

Node

?

}

Định nghĩa 1 class Stack với kiểu dữ liệu generic T và 1 node trên cùng gọi là top

1

2

3

4

5

}

2.2. Thêm 1 phần tử vào ngăn xếp (push)

Kiểm tra xem ngăn xếp có nil không, nếu nil thì gán đỉnh ngăn xếp vào phần tử muốn thêm vào.

Nếu đỉnh ngăn xếp không nil, tạo 1 nút mới, gán phần tử muốn thêm vào nút đó, gán đỉnh ngăn xếp vào nút vừa tạo.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

func

push

(

key

:

T

)

{

        

// neu ngan xep chua co dinh

        

if

top

==

nil

{

        

}

        

// neu dinh ngan xep rong

        

if

top

.

key

==

  

nil

{

            

top

.

key

=

key

            

return

        

}

else

{

// khong thi tao 1 nut moi roi gan nut do vao dinh

            

newNode

.

key

=

key

            

newNode

.

next

=

top

            

top

=

newNode

        

}

    

}

2.3. Lấy 1 phần tử ra khỏi danh sách(pop)

Kiểm tra danh sách đỉnh có rỗng không, nếu rỗng thì kết thúc.

Nếu đỉnh danh sách không rỗng, kiểm tra nút đỉnh trỏ đến có rỗng không nếu rỗng thì gán đỉnh danh sách bằng nil( trường hợp danh sách chỉ có 1 phần sau khi lấy 1 phần tử ra thì danh sách trở thành rỗng), còn không gán đỉnh của danh sách vào nút tiếp theo.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

        

// kiem tra xem dinh danh sach co rong khong

        

// neu rong thi ket thuc

        

guard

let

popItem

=

  

top

.

key

else

{

            

return

        

}

        

// kiem tra xem nut tiep theo cua dinh co rong khoong

        

if

let

nextNode

=

top

.

next

{

            

top

=

nextNode

        

}

else

{

            

top

=

nil

        

}

        

return

popItem

    

}

2.4. Xem phần tử đầu danh sách

Kiểm tra xem đỉnh của danh sách có rỗng không, nếu rỗng thì trả về nil còn không trả về giá trị của đỉnh danh sách.

1

2

3

4

5

6

7

8

9

10

11

12

        

// kiem tra xem dinh dach sach co rong khong

        

guard

let

topItem

=

top

.

key

else

{

            

// neu rong thi tra ve nil

            

return

nil

        

}

        

// con khong tra ve gia tri dinh danh sach

        

return

topItem

    

}

2.5. Test thử danh sách

2.5.1. Test build stack

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

func

buildStack

(

)

{

        

let

numberList

=

[

1

,

4

,

7

,

9

,

10

,

12

,

20

]

        

for

number

in

numberList

{

            

stack

.

push

(

number

)

        

}

        

printStack

(

)

    

}

    

func

printStack

(

)

{

        

var

top

=

stack

.

top

        

print

(

top

.

key

)

        

while

top

.

next

!=

nil

{

            

top

=

top

.

next

            

print

(

top

.

key

)

        

}

    

}

2.5.2. Test push stack

1

2

3

4

5

6

7

func

pushStack

(

)

{

        

stack

.

push

(

40

)

        

printStack

(

)

    

}

2.5.3 Test pop stack

1

2

3

4

5

6

func

popStack

(

)

{

        

let

item

=

stack

.

pop

(

)

        

print

(

item

)

    

}

3. Một số ứng dụng của ngăn xếp

3.1. Đảo ngược xâu ký tự

Bài toán đảo ngược xâu ký tự yêu cầu hiển thị các ký tự của 1 xâu ký tự theo chiều ngược lại.

Ký tự cuối cùng của xâu sẽ được hiển thị trước, tiếp theo là ký tự sát ký tự cuối … và ký tự đầu tiên sẽ được hiển thị đầu tiên.

Để giải quyết bài toán, ta chỉ cần duyệt từ đầu đến cuối xâu, lần lượt cho các ký tự vào ngăn xếp.

Khi đó, các ký tự đầu tiên sẽ vào trước, tiếp theo đến ký tự thứ 2 … ký tự cuối cùng vào sau cùng. Sau khi đã cho toàn bộ ký tự của xâu vào ngăn xếp, lần lượt lấy các phần tử ra khỏi ngăn xếp và hiển thị lên màn hình.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

        

for

s

in

stringInput

.

characters

{

            

stringStack

.

push

(

String

(

s

)

)

        

}

        

var

newString

=

“”

        

var

item

=

stringStack

.

top

        

newString

+=

item

.

key

        

while

item

.

next

!=

nil

{

            

item

=

item

.

next

            

newString

+=

item

.

key

        

}

        

return

newString

    

}

3.2. Tính giá trị biểu thức dạng hậu tố

3.2.1. Bài toán

Một biểu thức toán học thông thường bao gồm các toán tử: + – * / , các toàn hạng và dấu ngoặc cho biết thứ tụ tính toán.

Chẳng hạn 1 biểu thức toán học: (3 * (((5 – 2) * (7 + 1)) – 6)) Như chúng ta đã thấy trong biểu thức trên , các toán tử bao h cũng nằm giữa 2 toàn hạng. Do vậy, cách viết trên được gọi là cách viết trung tố (infix). Để tính toán giá trị biểu thức trên, ta phải tính toán giá trị các phép toán trong ngoặc trước. Đôi khi ta cần lưu các kết quả tính toán này như 1 kết quả trung gian, sau đó sử dụng chúng như toán hạng tiếp theo. Ví dụ ở biểu thức trên, đầu tiên ta tính 5 – 2 = 3, lưu kết quả này lại. Trong các biểu thức dạng này, vị trí dấu ngoặc rất quan trọng. Nếu vị trí các dấu ngoặc thay đổi thì giá trị biểu thức cũng thay đổi theo. Đối với con người, cách trình bày biểu thức toán học theo dạng này có vẻ như là hợp lý nhất, nhưng đối với máy tính, việc tính toán nhũng biểu thức như vậy là tương đối phức tạp. Để dễ dạng cho máy tính trong việc tính toán các biểu thức, người ta đưa ra 1 cách trình bày khác cho biểu thức toán học, đó là dạng hậu tố (postfix).

Theo cách trình bày nay, toán tử không nằm giữa 2 toán hạng mà nằm ở ngay phía sau 2 toán hạng. Chẳng hạn ở biểu thức trên ta có thể viết dưới dạng hậu tố như sau: 3 5 2 – 7 1 + * 6 – * Toán tử – nằm ngay sau 2 toán hạng 5 và 2 nên lấy 5 – 2 = 3, lưu kết quả 3. Toán tử + nằm ngay sau 2 toán hạng 7 và 1 nên lấy 7 + 1 = 8, lưu kết quả 8. Toán tử * nằm ngay sau 2 kết quả vừa lưu nên lấy 3 * 8 = 24, lưu kết quả 24. Toán tử – nằm ngay sau kết quả vừa lưu và 6 nên lấy 24 – 6 = 18 Toán tử * nằm ngay sau kết quả vừa lưu và 3 nên lấy 3 * 18 = 54 là kết quả cuối cùng của biểu thức.

3.2.2. Cách thực hiện

Chuyển đổi biểu thức tiền tố sang hậu tố:

Duyệt từ trái qua phải.

Nếu gặp dấu mở ngoặc thì bỏ qua.

Nếu gặp số thì đưa vào biểu thức mới.

Nếu gặp toán tử thì đưa vào ngăn xếp.

Nếu gặp dấu đóng ngoặc thì lấy toán tử ra đưa vào biểu thức mới.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

        

var

postfixExpression

=

“”

        

for

s

in

infixExpression

.

characters

{

            

let

x

=

String

(

s

)

            

if

numbers

.

rangeOfString

(

x

)

!=

nil

{

                

postfixExpression

+=

x

            

}

else

if

operators

.

rangeOfString

(

x

)

!=

nil

{

                

stackOperator

.

push

(

x

)

            

}

else

if

x

==

“)”

{

// gap dau dong ngoac lay toan tu ra dua vao bieu thuc moi

                

let

_operator

=

stackOperator

.

pop

(

)

                

postfixExpression

+=

_operator

!

            

}

else

{

// dau mo ngoac bo qua

            

}

        

}

        

return

postfixExpression

    

}

Tính toán biểu thức hậu tố:

Tính toán biểu thức hậu tố:

Duyệt biểu thức từ trái qua phải.

Nếu gặp toán hạng thì đưa vào ngăn xếp.

Nếu gặp toán tử, lấy ra 2 toán hạng từ ngăn xếp, sử dụng toán tử để tính, sau đó đưa kết quả vào ngăn xếp.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

func

calculateInfixExpression

(

)

{

        

let

infixExpression

=

“(3*(((5-2)*(7+1))-6))”

        

let

postfixExpression

=

convertInfixToPostfixExpression

(

infixExpression

)

        

for

s

in

postfixExpression

.

characters

{

            

let

x

=

String

(

s

)

            

if

numbers

.

rangeOfString

(

x

)

!=

nil

{

                

resultStack

.

push

(

Int

(

x

)

!

)

            

}

else

if

operators

.

rangeOfString

(

x

)

!=

nil

{

                

let

number1

=

resultStack

.

pop

(

)

!

                

let

number2

=

resultStack

.

pop

(

)

!

                

let

result

=

calculate

(

number1

,

number2

:

number2

,

_operator

:

x

)

                

resultStack

.

push

(

result

)

            

}

else

{

            

}

        

}

        

print

(

resultStack

.

top

.

key

)

    

}

4. Demo

https://github.com/pqhuy87it/MonthlyReport

5. Tài liệu tham khảo

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html

Via Viblo

DVMS chuyên:

– Tư vấn, xây dựng, chuyển giao công nghệ Blockchain, mạng xã hội,… – Tư vấn ứng dụng cho smartphone và máy tính bảng, tư vấn ứng dụng vận tải thông minh, thực tế ảo, game mobile,… – Tư vấn các hệ thống theo mô hình kinh tế chia sẻ như Uber, Grab, ứng dụng giúp việc,… – Xây dựng các giải pháp quản lý vận tải, quản lý xe công vụ, quản lý xe doanh nghiệp, phần mềm và ứng dụng logistics, kho vận, vé xe điện tử,… – Tư vấn và xây dựng mạng xã hội, tư vấn giải pháp CNTT cho doanh nghiệp, startup,…

Kiểu Dữ Liệu Và Cấu Trúc Dữ Liệu Trong Javascript / 2023

Tất cả các ngôn ngữ lập trình đều có cấu trúc dữ liệu dựng sẵn, nhưng mỗi ngôn ngữ thường có những kiểu cấu trúc dữ liệu khác nhau. Bài viết này sẽ cố gắng liệt kê những kiểu dữ liệu dựng sẵn trong Javascript và những thuộc tính của chúng. Chúng có thể được dùng để xây dựng những kiểu cấu trúc dữ liệu khác. Khi có thể, rút ra so sánh với những ngôn ngữ khác.

JavaScript là một ngôn ngữ định kiểu yếu hay động. Điều đó nghĩa là không cần phải khai báo kiểu của các biến trước khi dùng. Kiểu sẽ được xác định tự động trong khi chương trình được thực thi. Điều đó cũng có nghĩa là một biến có thể chứa giá trị của các kiểu dữ liệu khác nhau:

Tiêu chuẩn ECMAScript mới nhất xác định chín kiểu:

Sáu kiểu Dữ liệu sơ khai (primitive), có thể kiểm tra với toán tử typeof:

Kiểu null: typeof instance === "object". Một kiểu sơ khai mà giá trị của nó có thêm một vai trò đặc biệt: nếu object không kế thừa từ đối tượng nào khác, null sẽ được hiển thị ở cuối chuỗi Prototype

Object: typeof instance === "object". Kiểu phi dữ liệu nhưng có cấu trúc cho các đối tượng được khởi tạo và được dùng như cấu trúc dữ liệu: new Object, new Array, new Map, new Set, new WeakMap, new WeakSet, new Date hay bất kỳ đối tượng nào được tạo ra với từ khóa new.

Kiểu phi dữ liệu Function, mặc dù khi gọi với typeof nó có nhãn riêng: typeof instance === "function". Giá trị trả về từ typeof này là một nhãn đặc biệt cho các function, cho dù constructor của Function phát sinh từ Object constructor.

Lưu ý: vai trò có giá trị duy nhất của toán tử typeof là dùng để kiểm tra các kiểu Dữ liệu (sơ khai). Nếu bạn muốn kiểm tra các kiểu Cấu trúc phát sinh từ Object, typeof sẽ chẳng có ích gì vì nó sẽ luôn trả về "object". Cách đúng đắn để kiểm tra một Object thuộc loại nào là dùng từ khóa instanceof. Tuy nhiên, ngay cả với cách này cũng có một vài ngoại lệ.

Tất cả các kiểu trừ đối tượng đều được xác định giá trị bất biến (giá trị không có khả năng thay đổi). Ví dụ (và không như ngôn ngữ C), các chuỗi là bất biến. Ta gọi chúng là “giá trị sơ khai” (“primitive”).

Có duy nhất một giá trị: null. Xem và Null để biết thêm chi tiết.

Một biến chưa được gán giá trị có giá trị undefined. Xem và Undefined để biết thêm chi tiết.

Theo tiêu chuẩn ECMAScript, chỉ có duy nhất một kiểu số: the double-precision 64-bit binary format IEEE 754 value (có giá trị từ -(2 53 -1) đến 2 53 -1). Không có kiểu số nguyên. Ngoài việc có thể chứa giá trị dấu phẩy động, kiểu số có ba giá trị biểu tượng: +Infinity, -Infinity, and (not-a-number).

Để kiểm tra lớn hơn hay nhỏ hơn +/-Infinity, bạn có thể xem Number.MAX_VALUE hoặc Number.MIN_VALUE và bất đầu từ ECMAScript 6, bạn cũng có thể kiểm tra một số có nằm trong khoảng double-precision floating-point bằng cách dùng Number.isSafeInteger() cũng như Number.MAX_SAFE_INTEGER và Number.MIN_SAFE_INTEGER. Ngoài phạm vi này, một số trong Javascript không còn an toàn nữa.

Có một số nguyên duy nhất có hai đại diện: 0 được đại diện bởi -0 và +0. (“0” là một bí danh của +0). Trong thực tế, điều này hầu như không có tác động. Ví dụ +0 === -0 là true. Tuy nhiên, có thể nhân thấy điều này khi chia một số cho không:

Mặc dù một số thường chỉ đại diện cho giá trị của nó, JavaScript cung cấp một vài toán tử nhị phân. Chúng có thể được sử dụng như một chuỗi boolean bằng cách dùng bit masking. Điều này thường được xem như là một cách tệ, tuy nhiên, JavaScript không cung cấp bất kỳ phương tiện nào khác để trình bày một tập hợp các boolean (như một mảng các boolean hay một đối tượng với các thuộc tính boolean). Bit masking cũng có xu hướng làm mã khó đọc, hiểu, và duy trì hơn. Nó có thể cấn thiết trong một môi trường rất hạn chế, giống như khi cố gắng để đối phó với hạn chế lưu trữ lưu trữ cục bộ hoặc trong trường hợp nặng khi mỗi chút so với đếm mạng. Kỹ thuật này chỉ nên được xem xét khi nó là biện pháp cuối cùng có thể được thực hiện để tối ưu hóa kích thước.

Kiểu là một kiểu giá trị số sơ khai trong JavaScript, đại diện cho các giá trị số nguyên với độ chính xác (precision) bất kỳ. Với BigInt, bạn có thể lưu và tính toán trên các số nguyên lớn mà nó có thể lớn hơn cả giới hạn an toàn của kiểu Number.

Một số BigInt được tạo ra bằng cách thêm n vào cuối giá trị literal số nguyên hoặc bằng cách sử dụng constructor.

Bạn có thể lấy giá trị nguyên an toàn lớn nhất của kiểu Number bằng cách sử dụng constant Number.MAX_SAFE_INTEGER. Với sự ra đời của kiểu BigInt, giờ đây bạn có thể tính toán với những con số còn lớn hơn Number.MAX_SAFE_INTEGER.

Trong ví dụ sau, khi tăng dần giá trị Number.MAX_SAFE_INTEGER, bạn vẫn nhận được kết qua như mong muốn với BigInt:

Bạn có thể sử dụng các toán tử +, *, -, **, và % với BigInt như với Number. Một số BigInt không hoàn toàn bằng (===) một số Number, nhưng có thể bằng khi ép kiểu (==).

Số BigInt không thể dùng chung với số Number để tính toán. Khi đó, lỗi sẽ xảy ra.

Kiểu được dùng để biểu diễn dữ liệu dạng văn bản. Nó là một dãy “các phần tử” số nguyên 16-bit. Mỗi phần tử có một vị trí trong chuỗi. Phần tử đầu tiên có chỉ số 0, tiếp theo là 1, … . Độ dài của chuỗi là số phần tử của nó.

Không giống với những ngôn ngữ như C, Chuỗi trong Javascript là bất biến. Nghĩa là một khi chuỗi được tạo thì không thể chỉnh sửa. Tuy nhiên, vẫn có thể tạo một chuỗi mới dựa vào các thao tác trên chuỗi cũ. Ví dụ:

Cẩn thận với việc “lưu mọi thứ bằng chuỗi” trong code của bạn!

Chuỗi có thể được dùng để biểu diễn dữ liệu với cấu trúc phức tạp. Điều này mang tới một vài lợi ích ngắn hạn:

Rất dễ để xây dựng một chuỗi bằng phép nối.

Dễ debug (những gì bạn thấy khi in luôn là tất cả những thứ có trong chuỗi).

Chuỗi là mẫu số chung của rất nhiều API (nhập, local storage values, XMLHttpRequest phản hồi khi dùng responseText, …) và điều này có thể khiến việc chỉ làm việc với chuỗi được yêu thích.

Chuỗi có thể biểu diễn bất kì kiểu dữ liệu nào. Những đây không được xem là một ý hay. Ví dụ, đối với một separator, có thể bắt trước một chuỗi (trong khi một mảng sẽ thích hợp hơn). Thật không may, khi separator được dùng trong một “danh sách” các phần tử, danh sách bị hỏng. Một escape character có thể được chọn, ….. Tất cả những điều này yêu cầu một quy ước và tạo ra gánh nặng bảo trì không cần thiết.

Chỉ nên dùng chuỗi để lưu trữ dữ liệu văn bản. Khi biểu diễn một cấu trúc phức tạp, phân tích chuỗi thành các cấu trúc dữ liệu với mức trừu tưỡng cao hơn.

Kiểu Symbol là một kiểu mới trong Javascript tiêu chuẩn ECMAScript 6. Mỗi Symbol là một giá trị sơ khai đơn nhất và bất biến và có thể được dùng như một khóa của một Object (xem bên dưới). Trên một số ngôn ngữ lập trình, Symbol còn được gọi là “atom” (nguyên tử). Ta cũng có thể so sánh với các enumeration (enum) trong C. Xem Symbol và để biết thêm chi tiết.

Trong khoa học máy tính, một đối tượng là một giá trị trong bộ nhớ được tham chiếu bởi một định danh.

Trong Javascript, đối tượng có thể được xem là tập hợp các thuộc tính. Với object literal syntax, một tập hợp hữu hạn các thuộc tính được khởi tạo; sau đó thuộc tính có thể được thêm hoặc loại bỏ. Giá trị thuộc tính thuộc bất kỳ kiểu dữ liệu, bao gồm những đối tượng khác (kể cả chính đối tượng đó), điều này cho phép xây những những cấu trúc dữ liệu phức tạp. Thuộc định được định danh bằng khóa. Một khóa phải là một chuỗi hoặc một Symbol.

Có hai loại thuộc tính với các đặc điểm nhất định: Chứa dữ liệu và accessor.

Thuộc tính chứa dữ liệu

Liên kết một khóa với một giá trị có các đặc điểm sau:

Các đặc điểm của thuộc tính chứa dữ liệu

Accessor

Liên kết một khóa với một hoặc hai hàm accessor (get và/hoặc set):

[[Get]]

Hàm hoặc undefined

Hàm được gọi không đối số và trả về giá trị mỗi khi có truy cập tới thuộc tính. Xem .

undefined

[[Set]]

Hàm hoặc undefined

Hàm được gọi với một đối số mỗi khi thuộc tính được gán một giá trị. Xem .

undefined

[[Enumerable]]

Boolean

Nếu là true, khóa của giá trị có thể được liệt kê bằng vòng lặp for…in.

false

[[Configurable]]

Boolean

Nếu là false, thuộc tính không thể bị xóa cũng như không thể thay đổi các đặc điểm của nó.

false

Mội đối tượng là một bảng các khóa và giá trị. Khóa là một chuỗi và giá trị có thể là bất kỳ thứ gì. Điều này khiến đối tượng phù hợp với hashmaps.

Hàm là một đối tượng với khả năng có thể gọi.

Để biểu diễn một thời điểm hay ngày tháng, Lựa chọn tốt nhất là sử dụng .

Mảng là một đối tượng có một quan hệ đặc biệt giữa các thuộc tính có khóa nguyên và thuộc tính ‘length’. Thêm vào đó, mảng thừa kế các thuộc tính của Array.prototype cung cấp một số ít các hàm xeur lý danh sách. Ví dụ, (tìm giá trị trên một mảng) hay (thêm một phần tử vào cuối danh sach), …. Điều này biến mảng trở thành ứng cử viên hoàn hào cho danh sách hoặc tập hợp.

Mảng đã định kiểu là loại mới trong ECMAScript 6 và biểu diễn dữ liệu nhị phân như một mảng. Bảng sau đây giúp bạn so sánh với kiểu dữ liệu trong C:

TypedArray objects

These data structures take object references as keys and are introduced in ECMAScript Edition 6. and represent a set of objects, while and associate a value to an object. The difference between Maps and WeakMaps is that in the former, object keys can be enumerated over. This allows garbage collection optimizations in the latter case.

One could implement Maps and Sets in pure ECMAScript 5. However, since objects cannot be compared (in the sense of “less than” for instance), look-up performance would necessarily be linear. Native implementations of them (including WeakMaps) can have look-up performance that is approximately logarithmic to constant time.

Usually, to bind data to a DOM node, one could set properties directly on the object or use data-* attributes. This has the downside that the data is available to any script running in the same context. Maps and WeakMaps make it easy to privately bind data to an object.

JSON (JavaScript Object Notation) is a lightweight data-interchange format, derived from JavaScript but used by many programming languages. JSON builds universal data structures. See JSON and for more details.

JavaScript has a standard library of built-in objects. Please have a look at the reference to find out about more objects.

The typeof operator can help you to find the type of your variable. Please read the reference page for more details and edge cases.

Bạn đang đọc nội dung bài viết Giới Thiệu Về Cấu Trúc Dữ Liệu Stack / 2023 trên website Comforttinhdauthom.com. Hy vọng một phần nào đó những thông tin mà chúng tôi đã cung cấp là rất hữu ích với bạn. Nếu nội dung bài viết hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!