Stack Data Structure

Stack Data Structure

The stack data structure is considered as a collection of elements of similar data type that are arranged in a linear order. We can add and remove elements in stack data structure in a particular order. Whenever we add elements in a stack data structure, the element goes on the top of the stack.

In stack data structure we can only remove that element which is on the top of the stack. In real life stack is just like: a stack of books, stack of plates, etc. Consider the following figure in which stack data structure is illustrated:

Basic features of Stack:

The following are some of the features of stack:

1. A stack is considered as an ordered list of elements of similar data type.
2. Stack follows LIFO structure that is last in first out. The last element to go into stack is the first to come out.
3. The two basic functions of stack are push () and pop (). The push () function is used to insert elements into stack and the pop () function is used to delete an element from the stack. We can insert or delete any element from the stack at only one end of the stack that is TOP.
4. When stack is completely full it is said to be in overflow state and if the stack is completely empty, it is said to be in underflow state.

Applications of Stack:

A stack is used to reverse a word that is when a string of characters are entered into a stack and the user wants to reverse this string then he will pop the characters of the string and in this way the characters entered last will be popped out first and we will get our word or string reversed. The stack data structure is also used for conversion from postfix to infix or from infix to postfix, etc.

Implementation of Stack:

A stack can be implemented either by using linked list or by using array. We do not use arrays to implement stack because they are quick but are limited in size. This is the reason linked lists are widely used to implement stack data structure as they are not limited in size. Consider the following code in which we have implemented stack using an array in C++ programming language:

CODE:

# include <iostream>

using namespace std;

# include <conio.h>

class stack

{

private:

int array [5];

int top;

public:

stack ();

void push  (int d);

int pop ();

};

stack :: stack ()

{

array [top] =0;

}

void stack :: push (int d)

{

array [top] =d;

top++;

}

int stack :: pop ()

{

–top;

return array [top];

}

void main ()

{

stack s;

1. push (1);
2. push (2);
3. push (3);

cout << s.pop ();

cout <<  s.pop ();

getch ();

}

Working of the above program:

The above program follows the concept of undo that is first user enters data and then pops out in back direction. There are three member functions; stack () is the constructor used to initialize the values of data members to zero to avoid garbage values. The function void push (int d) is used to enter the data.

Now take a look on the main () function the line s. push (1) means that the function is called using the object and 1 is passed. 1 is stored in int d. the top of array or array [top] is at zero location, when 1 is passed, the zero location of array has 1 value. After this the value of top is incremented, it means that now the location of array [top] is 1. Again through main function (2) is passed, and this process is repeated thrice. Now the three locations of arrays have three values 1, 2 and 3 respectively.

After the push function, pop () function is called in the cout statement. The control is transferred to pop () it decrements the value of top and returns the value of array[top] which has the value 3. This value (3) is printed on the screen and the process is continued.

When the value or position of top is -1 then the stack is considered as empty. When the value or position of top is 0 then stack has one element in it. When the value or position of top is n-1, stack is considered to be full. When the value or position of top is n, stack is completely full (overflow).

Analysis of Stack:

The following are the time complexities for the basic operations that can be applied on stack data structure:

Push operation:

The time complexity for push operation is O (1).

Pop operation:

The time complexity for pop operation is O (1).

Top operation:

The time complexity for top operation is O (1).

Search operation:

The time complexity for search operation is O (n).

---