Tiêu đề Stacks.pdf ✅

Stacks Topics 1. Introduction to Stacks 2. Implementation of a Stack using Array in C/C++ 3. Implementation of a Stack using Linked List in C/C++ 4. Details of Inbuilt Stack library in C++, Java & Python 5. Problems & Solutions
Introduction Stack is a Linear Data Structure which follows a particular order in which the operations are performed. The order may be LIFO [Last In First Out] or FILO [First In Last Out]. LIFO says that, whatever was the last inserted element onto the stack, will be the first element to be popped out of the stack. FILO is just the same saying as LIFO, but the other way around. Stacks primarily support the following three basic operations :- 1. Push: Adds/Pushes an item on to the top of the stack. If the stack is full while pushing an element, then it is said to be a Stack Overflow condition i.e., we can’t push any more items onto the stack. Complexity : O(1) 2. Pop: Removes/Pops an item from the top of the stack. The item that is popped first, is the most recent item that has been pushed on to the stack. If the stack is empty while popping, then it is said to be a Stack Underflow condition i.e., There are no more items in the stack to be popped. Complexity : O(1) 3. Top: Get the topmost item. If the stack is empty, just return -1 (or INT_MIN). Complexity : O(1) How to understand a stack practically? There are many real life examples of stack. Consider the simple example of plates stacked over one another in a restaurant. The plate which is at the top is the first one to be removed, i.e., the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it simply follows LIFO/FILO order. In terms of programming, the browser has a forward and backward button to go back to the previously visited page. This functionality of going back/forward is same as popping/pushing an element from/to the top of the stack. Therefore, every browser uses the stack data structure in this manner. Implementation There are two ways to implement a stack :- ● Using an Array. ● Using a Linked List.
Implementation of a Stack using an Array in C/C++ #include #include #include // 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 get top item from stack int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return stack->array[stack->top]; } int main() { struct Stack* stack = createStack(100); push(stack, 10); push(stack, 20); push(stack, 30); printf("%d popped from stack\n", pop(stack)); printf("Top item is %d\n", peek(stack)); return 0; }