Saturday, August 11, 2018

About of Algorithms and Stack Data structure..

DATA STRUCTURE & ALGORITHMS - STACK DATA STRUCTURE & ALGORITHMS



What is a Data Structure Stack?

An Abstract Data Type (ADT) used in the programming languages is known as a Stack. As the name implies it works as a real stack like a deck of cards or pile of plates.
Stack Example
A real-world stack allows operations at one end only. For instance, a card or plate can be placed or removed from the top of the stack only. Even Stack ADT allows the data operations at only on end. Only the top element of a stack can be accessed at any time.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. The element placed last is accessed first. In Stack, operation is called PUSH operation and removal operation is called POP operation.

How Data Structure Stack is represented?

The following diagram depicts a stack and its operations −
Stack Representation
Array, structure, pointer and Linked list can implement a Stack. Stack may be of a fixed size or a have an option of dynamic resizing. In this tutorial stacks are implemented using arrays and hence makes it a fixed stack implementation.

What are the basic operations supported by Stack?

The operations supported by stack involve initializing of the stack, de-initializing. Apart from these, the other operations supported by Stack are:
  • push() − Pushing (storing) an element on the stack.
  • pop() − Removing (accessing) an element from the stack.
By checking the status of the tack, the stack is used efficiently for which some of the functions are added to the 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.
At all times, a pointer is maintained to the last PUSHed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.

What are the procedures to support Stack functions?

Procedures to support stack functions are−

peek()

Algorithm of peek() function −
1
begin procedure peek
2
return stack[top]
3
end procedure
4
​
5
​
Implementation of peek() function in C programming language −
Example
1
int peek() {
2
return stack[top];
3
}
4
​

isfull()

Algorithm of isfull() function −
1
begin procedure isfull
2
if top equals to MAXSIZE
3
return true
4
else
5
return false
6
endif
7
end procedure
8
​
9
​
Implementation of isfull() function in C programming language −
Example
1
bool isfull() {
2
if(top == MAXSIZE)
3
return true;
4
else
5
return false;
6
}
7
​

isempty()

Algorithm of isempty() function −
1
begin procedure isempty
2
if top less than 1
3
return true
4
else
5
return false
6
endif
7
end procedure
8
​
9
​
Implementation of isempty() function in C programming language is slightly different. Top is initialized at -1 and the index in array starts from 0. Check if the stock is zero or -1 and determine that the stack is empty. The code for this is:
Example
1
bool isempty() {
2
if(top == -1)
3
return true;
4
else
5
return false;
6
}
7
​

What are the steps involved in a Stack 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.
Stack Push Operation
If the linked list is used to implement the stack, then in step 3, allocate space dynamically.

Algorithm for PUSH Operation

A simple algorithm for Push operation can be derived as follows −
1
begin procedure push: stack, data
2
if stack is full
3
return null
4
endif
5
top ← top + 1
6
stack[top] ← data
7
end procedure
8
​
9
​
Implementation of this algorithm in C, is very easy by the code −
Example
1
void push(int data) {
2
if(!isFull()) {
3
top = top + 1;  
4
stack[top] = data;
5
} else {
6
printf("Could not insert data, Stack is full. \n");
7
}
8
}
9
​

What are the steps involved in a Stack Pop Operation?

Pop operation is to access the content while removing it from the stack. In an array implementation of pop() operation, top is decremented to a lower position in the stack to point to the next value and the data element is not actually removed.But in linked-list implementation, pop() actually removes data element and deallocates memory space.
The steps in the Pop operation are −
  • 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.

Stack Pop Operation

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −
1
begin procedure pop: stack
2
if stack is empty
3
return null
4
endif
5
data ← stack[top]
6
top ← top - 1
7
return data
8
end procedure
9
​
10
​
Implementation of this algorithm in C, is as follows −
Example
1
int pop(int data) {
2
if(!isempty()) {
3
data = stack[top];
4
top = top - 1;  
5
return data;
6
} else {
7
printf("Could not retrieve data, Stack is empty. \n");
8
}
9
}
10
​
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)