Stack

 What is a Stack? 

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.


Some key points related to stack

  • It is called as stack because it behaves like a real-world stack, piles of books, etc.
  • A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size.
  • It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.

Working of Stack

Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in the stack; therefore, the size of the stack is 5.

Suppose we want to store the elements in a stack and let's assume that stack is empty. We have taken the stack of size 5 as shown below in which we are pushing the elements one by one until the stack becomes full.

Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes from the top to the bottom when we were entering the new element in the stack. The stack gets filled up from the bottom to the top.10 SJDK, JRE, and JVM

When we perform the delete operation on the stack, there is only one way for entry and exit as the other end is closed. It follows the LIFO pattern, which means that the value entered first will be removed last. In the above case, the value 5 is entered first, so it will be removed only after the deletion of all the other elements.

Standard Stack Operations

The following are some common operations implemented on the stack:

  • push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
  • pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
  • isEmpty(): It determines whether the stack is empty or not.
  • isFull(): It determines whether the stack is full or not.'
  • peek(): It returns the element at the given position.
  • count(): It returns the total number of elements available in a stack.
  • change(): It changes the element at the given position.
  • display(): It prints all the elements available in the stack.

PUSH operation

The steps involved in the PUSH operation is given below:

  • Before inserting an element in a stack, we check whether the stack is full.
  • If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
  • When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
  • When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
  • The elements will be inserted until we reach the max size of the stack.

POP operation

The steps involved in the POP operation is given below:

  • Before deleting the element from the stack, we check whether the stack is empty.
  • If we try to delete the element from the empty stack, then the underflow condition occurs.
  • If the stack is not empty, we first access the element which is pointed by the top
  • Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.


Popular posts from this blog

DATA STRUCTURES-II

 UNIT – I  Tree: Header nodes, Threads, Binary search trees, Searching, Insertion and deletion in aBinary search tree , AVL search trees, Insertion and deletion in AVL search tree , m-waysearch tree, Searching, Insertion and deletion in an m-way search tree , B-trees, Searching,Insertion and deletion in a B-tree, B+tree , Huffman’s algorithm , General trees.  UNIT – II  Graphs: Warshall’s algorithm for shortest path , Dijkstra algorithm for shortest path , Operations on graphs , Traversal of graph , Topological sorting .  UNIT – III  Sorting: Internal & external sorting , Radix sort , Quick sort , Heap sort , Merge sort . Searching: Liner search, binary search, merging , Comparison of various sorting and searching algorithms on the basis of their complexity .  UNIT – IV  Files: Physical storage devices and their characteristics , Attributes of a file viz fields, records,Fixed and variable length records, Primary and secondary keys , Clas...
Read more

DATA STRUCTURES FOR BCA

UNIT – I  Introduction: Elementary data organization, Data Structure definition , Data type vs. data structure , Categories of data structures, Data structure operations, Applications of data structures, Algorithms complexity and time-space tradeoff, Big-O notataion.   Strings: Introduction, Storing strings, String operations, Pattern matching algorithms.  UNIT – II  Arrays: Introduction, Linear arrays, Representation of linear array in memory, address calculations, Traversal, Insertions, Deletion in an array, Multidimensional arrays, Parallel arrays, Sparse arrays.  Linked List: Introduction, Array vs. linked list, Representation of linked lists in memory, Traversal, Insertion, Deletion, Searching in a linked list, Header linked list, Circular linked list, Two-way linked list, Threaded lists, Garbage collection, Applications of linked lists.  UNIT – III  Stack: Introduction, Array and linked representation of stacks, Operations on stacks, Ap...
Read more

DATA STRUCTURES FOR B.TECH

DATA STRUCTURES Unit 1: Introduction :   Basic Terminologies:   C oncept of Data Structure, Choice of right Data Structure , Algorithms , how to design and develop algorithm, Complexity of algorithm.   Operations: insertion, deletion, traversal etc,   Analysis of an Algorithm. Searching:  Linear Search and Binary Search Techniques and their complexity analysis. Unit 2: Stacks  and  Queues : Stack  and  its  operations: Algorithms and their complexity analysis, Applications of Stacks: Expression       Conversion and evaluation -corresponding algorithms and complexity analysis. queue, Types of Queue: Simple  Queue, Circular Queue, Priority Queue ; Operations on each types of Queues: Algorithms and their analysis.   Unit 3 : Linked Lists:      Singly   linked  lists: Representation in memory, Algorithms of several operations:...
Read more