A stack is a simple data structure for storing data. In stack, the order in which the data arrives is important. A pile of books is a good example of stack.
A stack is an ordered list in which insertion and deletion are done at one end, where end is called top. The last element inserted is the first one to be deleted. Hence, it is called Last in First Out (LIFO) or First in Last Out (FILO) list
In computer science, a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop. Often a peek or top operation is also implemented, returning the value of the top element without removing it.
Stack Operations
Main operations
Implementation of stack
In this implementation, we add element from left to right and use a variable to keep track of the index of the top element.
The array storing the stacks may become full. A push operation will the throw error or message of stack over flow. Similarly, if we try to deleting an element from empty stack then it will throw error or message Stack is empty.
false
true
Pop() : 45
peek() : 13
Pop() : 13
Stack Overflow
Performance and Limitations
Performance : Let n be the number of elements in the stack.
Limitations : The size of the stack must be defined in prior and cannot be changed.
Applications
Stacks have numerous applications. We see stacks in everyday life, from the books in our library, to the blank sheets of paper in our printer tray. All of them follow the Last In First Out (LIFO) logic, that is when we add a book to a pile of books, we add it to the top of the pile, whereas when we remove a book from the pile, we generally remove it from the top of the pile.
A stack is an ordered list in which insertion and deletion are done at one end, where end is called top. The last element inserted is the first one to be deleted. Hence, it is called Last in First Out (LIFO) or First in Last Out (FILO) list
In computer science, a stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection, known as push and removal of an entity, known as pop. Often a peek or top operation is also implemented, returning the value of the top element without removing it.
Stack Operations
Main operations
- void push(int data) : Insert data onto stack.
- int pop() : Removes and returned last inserted element from the stack
Auxiliary operations
- int top() or peek() : Returns the last inserted elements without removing it.
- int size() : Returns the number of elements stored in stack.
- boolean isStackFull() : Check whether stack is full or not.
- boolean isEmpty() : Check whether stack is empty or not.
Implementation of stack
In this implementation, we add element from left to right and use a variable to keep track of the index of the top element.
The array storing the stacks may become full. A push operation will the throw error or message of stack over flow. Similarly, if we try to deleting an element from empty stack then it will throw error or message Stack is empty.
false
true
Pop() : 45
peek() : 13
Pop() : 13
Stack Overflow
Performance and Limitations
Performance : Let n be the number of elements in the stack.
- Space Complexity for n push operations : O(n)
- Time Complexity of push : O(1)
- Time Complexity of pop : O(1)
- Time Complexity of isEmpty : O(1)
- Time Complexity of isStackFull : O(1)
- Time Complexity of deleteStack : O(1)
Limitations : The size of the stack must be defined in prior and cannot be changed.
Applications
Stacks have numerous applications. We see stacks in everyday life, from the books in our library, to the blank sheets of paper in our printer tray. All of them follow the Last In First Out (LIFO) logic, that is when we add a book to a pile of books, we add it to the top of the pile, whereas when we remove a book from the pile, we generally remove it from the top of the pile.
- Converting a decimal number into a binary number.
- Towers of Hanoi
- Expression evaluation and syntax parsing
- Backtracking
- Implementing functions calls
- Page-visited history in a Web browser.
- Undo sequence in a text editor.
- Matching tags ing HTML and XML
please add advantages and disadvantages
ReplyDelete