Unit 2: Stack
Table of Content :
2.1 Definition
2.1 Stack as Abstract Data Type (ADT)
2.3 Stack operation
2.4 Stack application : Conversion from infix to post-fix / prefix expression, Evaluation of post-fix/prefix expressions.
Lab: Write a program to implement stack operations.
Definition:
The stack is an abstract data type (ADT) commonly used in most programming languages. It is named as stack as it behaves like a real-world stack. For example, a deck of cards or a pile of plates, etc.
Stack as Abstract Data Type (ADT):
A real-world stack allows operation at one end only. 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 the stack.
This feature makes it LIFO data structure, LIFO stands for Last-In-First-Out. Here, the element which is a place (inserted or added), is accessed first. In stack terminology, insertion operation is called PUSH operation, and removal operation is called POP operation.
Representation of Stack
A stack can be implemented by using Array, Structure, pointer, and linked list. The stack can be a fixed size or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays which makes it a fixes size stack implementation.
Stack Operation:
Stack operations may involve initializing the stack, using it, and then de-initializing it. Apart from this basic stuff, 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.
when data is PUSHED into the stack.
To use a stack efficiently, we need to check the status of the stack as well. for the same purpose, the following functionality is 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, we maintain a pointer to the PUSHED data on the stack. This pointer always represents the top of the stack, hence named top. The top pointer provides the top value of the stack without actually removing it.
First, we should learn about procedures about stack functions.
peek()begin procedure peek return stack[top] end procedure
Implementation in C language:-
int peek() { return stack[top]; }
isFull()begin procedure isfull if top equals to MAXSIZE return true else return false endif end procedure
Implementation in C language:-
bool isfull() { if(top == MAXSIZE) return true; else return false; }
PUSH Operation:isEmpty()Algorithm of isEmpty() function:-begin procedure isempty if top less than 1 return true else return false endif end procedureImplementation in C language is lightly different. We initialize top at -1, as index check array starts from 0. So we check if top is below zero or -1 to determine if stack is empty:-bool isempty() { if(top == -1) return true; else return false; }
The process of putting a new data element into a stack is known as PUSH Operation. It involves a series of steps.
- step 1 - check if the stack is full
- step 2 - if the stack is full, produce an error and exit.
- step 3 - if the stack is not full, increment top to point next empty space.
- step 4 - add data emblem to the stack location, where the top is pointing.
- step 5 - return success.
If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.
Algorithm for PUSH Operation
A simple algorithm for push operation can be derived as follows -
begin procedure push: stack, data if stack is full return null endif top ← top + 1 stack[top] ← data end procedure
Implementation of PUSH operation in the C programming language.
void push(int data) { if(!isFull()) { top = top + 1; stack[top] = data; } else { printf("Could not insert data, Stack is full.\n"); } }
PUSH Operation:
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of the pop() operation, the data is not actually removed, instead top is decrement to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data elements and deallocated memory space.
A pop() operation may involve the following steps:-
- step 1 - check if the stack is empty
- step 2 - if the stack is empty, produce an error and exit.
- step 3 - if the stack is not empty, access the data element at which the top is pointing.
- step 4 - decreases the value of the top by 1.
- step 5 - return success.
Algorithm for POP Operation
A simple algorithm for push operation can be derived as follows -
begin procedure pop: stack if stack is empty return null endif data ← stack[top] top ← top - 1 return data end procedure
Implementation of this algorithm in C is as follows:-
int pop(int data) { if(!isempty()) { data = stack[top]; top = top - 1; return data; } else { printf("Could not retrieve data, Stack is empty.\n"); } }
Program to implement stack operations:
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
int isempty() {
if(top == -1)
return 1;
else
return 0;
}
int isfull() {
if(top == MAXSIZE)
return 1;
else
return 0;
}
int peek() {
return stack[top];
}
int pop() {
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
int push(int data) {
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
int main() {
// push items on to the stack
push(3);
push(5);
push(9);
push(1);
push(12);
push(15);
printf("Element at top of the stack: %d\n" ,peek());
printf("Elements: \n");
// print stack data
while(!isempty()) {
int data = pop();
printf("%d\n",data);
}
printf("Stack full: %s\n" , isfull()?"true":"false");
printf("Stack empty: %s\n" , isempty()?"true":"false");
return 0;
}If we compile and run the above code, it will produce the following result:-
Element at top of the stack: 15 Elements: 15 12 1 9 5 3 Stack full: false Stack empty: true
0 Comments