Data Structures: Lecture 9

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203 

Faculty        : Avinash Kumar

Syllabus covered in  this blog

STACK (Infix to Post-fix, Evaluation of Post-fix)

Infix to Postfix Conversion

X is an arithmetic expression written in infix notation.

This algorithm finds the equivalent post-fix expression Y.

  

1.    Scan X from left to right and repeat Step 2 to 5 for each element of X until the Stack is empty.

2.    If an operand is encountered, add it to Y.

3.    If a left parenthesis is encountered, push it onto Stack.

4.    If an operator is encountered ,then:

a.    Pop from Stack and add each operator which has the same precedence as or higher precedence than scanned operator to Y.

b.    Add the scanned operator to Stack.

5.    If a right parenthesis is encountered ,then:

a.    Pop each operator from the Stack until a left parenthesis is encountered and add it to Y.

b.    Remove the left Parenthesis

Let’s take an example to better understand the algorithm

Infix Expression: 

 

    A+ (B*C-(D/E^F)*G)*H

  where ^ is an exponential operator.

Evaluation of Post-fix expression

·         While reading the expression from left to right, push the element in the stack if it is an operand.

·         Pop the two operands from the stack, if the element is an operator and then evaluate it.

·         Push back the result of the evaluation. Repeat it till the end of the expression.

Algorithm

1.    Add ) to postfix expression.

2.    Read postfix expression Left to Right until ) encountered

3.    If operand is encountered, push it onto Stack

4.    If operator is encountered, Pop two elements

a.    A -> Top element

b.    B-> Next to Top element

c.    Evaluate B operator A

d.    Push B operator A onto Stack

Example

Expression:  456*+

Data Structures : Lecture 8

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203 

Faculty        : Avinash Kumar

Syllabus covered in  this blog

STACK (Checking expressions)

Checking expressions using STACK 

Consider an example using the expression:

{(a + b) × (c + d) + (c × d)]}

Scan the expression from left to right. 

·         The first entry to be scanned is ‘{’, which is a left parenthesis.

·         Push it into the stack.

·         The next entry to be scanned is ‘(’, which is a left parenthesis.

·         Push it into the stack.

·         The next entry is ‘a’, which is an operand. Therefore, it is discarded.

·         The next entry is ‘+’, which is an operator. Therefore, it is discarded.

·         The next entry is ‘b’, which is an operand. Therefore, it is discarded.

·         The next entry to be scanned is ‘)’, which is a right parenthesis

·         POP the topmost entry from the stack.

·         Match the two brackets.

·         The next entry to be scanned is ‘×’, which is an operator. Therefore, it is discarded.

·         The next entry to be scanned is ‘(’, which is a left parenthesis

·         Push it into the stack

·         The next entry to be scanned is ‘c’, which is an operand. Therefore it is discarded

·         The next entry to be scanned is ‘+’, which is an operator. Therefore it is discarded

·         The next entry to be scanned is ‘d’, which is an operand. Therefore it is discarded

·         The next entry to be scanned is ‘)’, which is a right parenthesis.

·         POP the topmost element from the stack.

·         Match the two brackets.

·         The next entry to be scanned is ‘+’, which is an operator. Therefore, it is discarded.

·         The next entry to be scanned is ‘(’, which is a left parenthesis.

·         Push it into the stack.

·         The next entry to be scanned is ‘c’, which is an operand. Therefore, it is discarded.

·         The next entry to be scanned is ‘×’, which is an operator. Therefore, it is discarded.

·         The next entry to be scanned is ‘d’, which is an operand. Therefore, it is discarded.

·         The next entry to be scanned is ‘)’, which is a right parenthesis.

·         POP the topmost element from the stack.

·         Match the two brackets.

·         The next entry to be scanned is ‘]’, which is a right parenthesis.

·         POP the topmost element from the stack.

·         Match the two brackets

Since the brackets do not match,

it is an INVALID expression.

Data Structures : Lecture7

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203 

Faculty        : Avinash Kumar

Syllabus covered in  this blog

STACK (Linked List Implementation) 

Linked list implementation of stack

Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflow/full if the space left in the memory heap is not enough to create a node.

 

The structure Node is used to create the linked list that is implemented as a stack.

struct Node

{

   int data;

   struct Node *next;

};

The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.

Push operation

Pushing an element to a stack in linked list implementation is different from that of an array implementation. In order to push an element onto the stack, the following steps are involved.

• Create a node first and allocate memory to it.
• If the list is empty then the item is to be pushed as the start node of the list. This includes assigning value to the data part of the node and assign null to the address part of the node.
• If there are some nodes in the list already, then we have to add the new element in the beginning of the list (to not violate the property of the stack). For this purpose, assign the address of the starting element to the address field of the new node and make the new node, the starting node of the list.

The push() function takes argument val i.e. value to be pushed into the stack. Then a new node is created and val is inserted into the data part. This node is added to the front of the linked list and top points to it.

The algorithm for PUSH operation is as follows:

1.    Allocate memory for the new node.

2.    Assign value to the data field of the new node.

3.    Make the next field of the new node point to top.

4.    Make top point to the new node.

void push(int val)

{

   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));  

   newnode->data = val;

   newnode->next = top;

   top = newnode;

}

POP operation

Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :

• Check for the underflow condition: The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.
• Adjust the head pointer accordingly: In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.

The pop() function pops the topmost value of the stack, if there is any value. If the stack is empty then underflow is printed.

The algorithm for POP operation is as follows:

1.    Make a variable/pointer that point to the topmost node.

2.    Retrieve the value contained in the topmost node.

3.    Make top point to the next node in sequence.

4.    Release memory allocated to the node marked by variable/pointer.

void pop()

{

   if(top==NULL)

      cout<<"Stack Underflow"<<endl;

   else {

      cout<<"The popped element is "<< top->data <<endl;

      top = top->next;

   }

}

Data Structures: Lecture 6

Department: MCA
Semester    : II

Subject       : Data Structures through C++

Paper          : CCMCA 203 

Faculty        : Avinash Kumar

Syllabus covered in  this blog

STACK (Introduction, Operations) 

Stack

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc. A real-world stack allows operations at one end only. 

For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.

This feature makes it LIFO(Last-in-first-out) data structure. Here, the element which is inserted last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.

Basic Operations

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations −

·        push() − Pushing (storing) an element on the stack.

·        pop() − Removing (accessing) an element from the stack.

To use a stack efficiently, we need to check the status of stack. For the same purpose, the following functionality is added to stacks −

·        peek() − get the top data element of the stack, without removing it.

·        isFull() − check if stack is full.

·        isEmpty() − check if stack is empty.

We maintain a pointer to that always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.

Push Operation

The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps −

·        Step 1 − Checks if the stack is full.

·        Step 2 − If the stack is full, produces an error and exit.

·        Step 3 − If the stack is not full, increments top to point next empty space.

·        Step 4 − Adds data element to the stack location, where top is pointing.

·        Step 5 − Returns success.

Algorithm for PUSH Operation:

push:(stack, data) 

   if stack is full

      return null     

   top = top + 1

   stack[top] = data

Example

void push(int data)

{

   if(!isFull())

   {

      top = top + 1;   

      stack[top] = data;

   } 

   else 

   {

      cout<<"Could not insert data, Stack is full.\n";

   }

}

Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.

A Pop operation may involve the following steps:

•  Step 1 − Checks if the stack is empty.
•  Step 2 − If the stack is empty, produces an error and exit.
• Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
•  Step 4 − Decreases the value of top by 1.
• Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

pop: (stack) 

   if stack is empty

      return null      

   data = stack[top]

   top = top - 1

   return data 

Example

int pop(int data) 

{

   if(!isempty()) 

   {

      data = stack[top];

      top = top - 1;   

      return data;

   } 

   else 

   {

      cout<<"Could not retrieve data, Stack is empty.\n";

   }

}