Trong hướng dẫn này, bạn sẽ tìm hiểu về cấu trúc dữ liệu ngăn xếp và cách triển khai của nó trong Python, Java và C / C ++.
Ngăn xếp là một cấu trúc dữ liệu hữu ích trong lập trình. Nó chỉ giống như một đống đĩa chồng lên nhau.
Biểu diễn ngăn xếp tương tự như một chồng đĩa
Hãy nghĩ về những điều bạn có thể làm với một đống đĩa như vậy
- Đặt một đĩa mới lên trên
- Bỏ tấm trên cùng
Nếu bạn muốn đĩ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ách sắp xếp như vậy được gọi là Last In First Out - mục cuối cùng là mục đầu tiên ra ngoài.
Nguyên tắc LIFO của Ngăn xếp
Theo thuật ngữ lập trình, đặt một mục lên trên ngăn xếp được gọi là đẩy và loại bỏ một mục được gọi là pop .
Hoạt động đẩy và bật ngăn xếp
Trong hình trên, mặc dù mục 2 được giữ sau cùng, nhưng nó đã được loại bỏ trước - vì vậy nó tuân theo nguyên tắc Cuối cùng vào trước (LIFO) .
Chúng ta có thể triển khai một ngăn xếp bằng bất kỳ ngôn ngữ lập trình nào như C, C ++, Java, Python hoặc C #, nhưng đặc điểm kỹ thuật là khá giống nhau.
Các hoạt động cơ bản của ngăn xếp
Ngăn xếp là một đối tượng (kiểu dữ liệu trừu tượng - ADT) cho phép các hoạt động sau:
- Đẩy : Thêm một phần tử vào đầu ngăn xếp
- Pop : Xóa một phần tử khỏi đầu ngăn xếp
- IsEmpty : Kiểm tra xem ngăn xếp có trống không
- IsFull : Kiểm tra xem ngăn xếp đã đầy chưa
- Peek : Nhận giá trị của phần tử trên cùng mà không cần xóa nó
Hoạt động của cấu trúc dữ liệu ngăn xếp
Các hoạt động hoạt động như sau:
- Một con trỏ được gọi là TOP được sử dụng để theo dõi phần tử trên cùng trong ngăn xếp.
- Khi khởi tạo ngăn xếp, chúng tôi đặt giá trị của nó thành -1 để có thể kiểm tra xem ngăn xếp có trống không bằng cách so sánh
TOP == -1. - Khi đẩy một phần tử, chúng tôi tăng giá trị của TOP và đặt phần tử mới vào vị trí mà TOP chỉ đến.
- Khi bật một phần tử, chúng tôi trả về phần tử được trỏ đến bởi TOP và giảm giá trị của nó.
- Trước khi đẩy, chúng tôi kiểm tra xem ngăn xếp đã đầy chưa
- Trước khi xuất hiện, chúng tôi 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
Triển khai ngăn xếp bằng Python, Java, C và C ++
Cách triển khai ngăn xếp phổ biến nhất là sử dụng mảng, nhưng nó cũng có thể được triển khai bằng cách sử dụng danh sách.
Python Java C C + # 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))
// 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("OverFlowProgram Terminated"); 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("After popping out"); stack.printStack(); ) )
// Stack implementation in C #include #include #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(" STACK EMPTY "); ) else ( printf("Item popped= %d", s->items(s->top)); s->top--; ) count--; printf(""); ) // Print elements of stack void printStack(st *s) ( printf("Stack: "); for (int i = 0; i items(i)); ) printf(""); ) // 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("After popping out"); printStack(s); )
// Stack implementation in C++ #include #include 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)) ( printf("STACK FULL"); ) else ( s->top++; s->items(s->top) = newitem; ) size++; ) // Remove element from stack void pop(st *s) ( if (isempty(s)) ( printf(" STACK EMPTY "); ) else ( printf("Item popped= %d", 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
Stack Time Complexity
For the array-based implementation of a stack, the push and pop operations take constant time, i.e. O(1).
Applications of Stack Data Structure
Although stack is a simple data structure to implement, it is very powerful. The most common uses of a stack are:
- To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
- In compilers - Compilers use the stack to calculate the value of expressions like
2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
- In browsers - The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed.
