Data Structure ‘Stack’

Features of Data Structure ‘Stack’

  • ‘To Stack’ means ‘To Pile’.
  • Stack is a linear data structure – it is linear in the vertical.
  • It represents a linear collection which is visualized in the vertical.
  • Size of the collection represented by stack is known either before or during runtime.
  • Each of the two size related specifications of stack has a different kind of software implementation.
  • Collection represented by stack is implemented using array as a tool if the size of its collection is known before run time.
  • Collection represented by stack is implemented using linked list as a tool if the size of its collection is known during run time.
  • Each tool of implementation of stack has its own implementation related requirement.
  • Implementation requirement for array is an index variable.
  • Implementation requirement of a linked list is a pointer member.
  • End where the collection represented by stack begins is called ‘Bottom of Stack’.
  • End where collection represented by stack ends is called ‘Top of Stack’.
  • Collection represented by stack goes from bottom to top of stack.
  • Stack is a non recursive data structure.
  • Bottom end of the stack is fixed.
  • Top end of the stack is operational.
  • Process of adding a node in the collection represented by stack is called ‘PUSH’ operation.
  • During PUSH process, only one value is added in the collection at a time.
  • Process of deleting a node from the collection represented by stack is called ‘POP’ operation.
  • Node PUSH-ed last is POP-ed first. Stack follows LIFO (Last In First Out) protocols in both PUSH and POP processes and in the implementations of its both size related specifications.
  • During POP process, only one value is deleted from the collection at a time.
  • Both PUSH and POP operate at the end representing top of the stack.
  • From PUSH and POP, only one operation takes place at one time.
  • With each PUSH operation, size of collection represented by stack increases by one.
  • With each POP operation, size of collection represented by stack decreases by one.
  • POP has a precondition in the implementation of both kinds of specifications of stack.
  • PUSH has a precondition in the implementation of that specification of stack in which the size of the collection represented by stack is known before run time.
  • Valid address allocation is the precondition in that specification of stack in which the size of the collection represented by stack is known during run time.
  • Stack is classified as ‘Static Stack’ if the size of its collection is known before run time.
  • Stack is classified as ‘Dynamic Stack’ if the size of its collection is known during run time.
  • Node through which we access collection represented by a stack is called ‘Representative Node’ of stack.
  • Node representing top of the stack is the ‘Representative Node’ of its collection.
  • Top of the stack moves away from the bottom of the stack after each PUSH process.
  • Top of the stack moves towards from the bottom of the stack after each POP process.
  • Top of the stack oscillates during successive PUSH and POP processes.

All the Stack points taken from my Sir’s Notes. All credit to him.

What is Stack?

A common question asked to any programmer during any interview or viva. Just remember a few points of these and you are through. 😀

Happy Programming… 🙂

Advertisements

What is a Data Structure?

What is a Data Structure???

  • A DS Represents a finite collection of data.
    • Size of the collection is known before execution i.e static DS & is fixed e.g-Arrays
    • Size of the collection will be known during execution i.e variable or dynamic DS e.g-Linked List
  • It demonstrates relationship among the members- fits collection
  • It has methods to process members. i.e addition, deletion- fits collection

The entire triplet is called a Data Structure.

Example of Data Structures are Stack, Queue, Linked List, Trees, Arrays, Files etc.

Simple Definition for anyone to understand. I suggest every one to explore this topic more and more to become a good programmer.

Searching-Linear Search

Searching

Searching is an operation which finds the location of a given element in a list. The search is said to be successful or unsuccessful depending on whether the element that is to be searched is found or not.

Two Standard Searching Techniques are Linear Search and Binary Search

Linear Search

This is the simplest method of searching. In this method, the element to be searched is sequentially searched in the list. This method can be applied to a sorted or an unsorted list.

Searching in case of sorted list starts from 0th element and continues until the element is found or an element whose value is greater (assuming the list is sorted in ascending order) than the value being searched is reached.

List sorted in ascending order

1 5 7 8 9 12 15

Search for 10 in the above list

We reached 12. Since 12>10 Searching stops.

Search for 9. When 9 will be found the search stops.

List sorted in descending order

15 12 11 9 6 4

Search for 10. We reached 9. 9<10. Searching stops

Searching in case of unsorted list starts from the 0th element and continues until the element is found or the end of list is reached.

Performance of Linear search algorithm can be measured by counting the comparisons done to find out an element. The number of comparisons is O(n).