Stack is an ordered group of homogeneous items. —Items are added to and removed from the top of the stack (the most recently added items are at the top of the stack). —The last item to be added is the first to be removed (LIFO: Last In, First Out). A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end called the TOP of the stack.

—The implementation of stack provides for the insertion and deletion of items (at run time), so that a stack is a dynamic, constantly changing object.—

—How does a stack change? —New items may be put on top of the stack. In which case the top of the stack moves upward to correspond to the new highest element. —Items which are at the top of the stack may be removed. In which case the top of the stack moves downward to correspond to the new highest element.

Which end is top? We must decide which end of the stack is designated as its top. —A common data structure in computing. —Data items are “popped” and “pushed” (retrieved and stored) from the top of the stack. —Stacks normally have a maximum size. It is an error to push items onto a full stack, or pop items off an empty stack.

—Applications of Stack

  • Parsing of algebraic expression
  • Banking Transaction View (You view the last transaction first)

Insertion and Deletion in Stack

—C is the current top element of the stack. If any new items are added to the stack, they are placed on top of C
—If any new items are deleted C is deleted first.

Operations on Stack

A Stack normally has the following methods:

  • push(item)    //Push an item onto the stack
  • pop( )              //Pop the top item off the stack
  • isEmpty()     //Return true if stack is empty
  • isFull()           // Return true if stack is full
  • top( )              //Return value of top item

There are several ways to implement a Stack in C++.

Implementing a Stack in C++

—First, if we want to store letters, we can use type char. —Next, since a stack usually holds a bunch of items with the same type (e.g., char), we can use an array to hold the contents of the stack. —At some point we’ll have to decide how big this array is; keep in mind that a normal array has a fixed size.

—Let’s choose the array to be of size 4 for now. So, an array getting A, then B, will look like:

A B
[0] [1] [2] [3]
—How do we know that which element to pop when user asks a pop operation. As not all the spaces of array are filled. —We need another variable (usually Int) to keep track of last pushed index. —So for each push we add one to top and for each pop we deduct one from top.
A B
[0] [1] [2] [3]

What if the stack is full or what if the stack is empty?—

—Solution: Before any push check if the stack is already filled or not. If it is filled then generate error message e.g Stack Overflow. Before pop check if stack is not already empty

Sample Program (Push Pop using Array)

#include<conio.h>
#include <iostream.h>
#define length 10
int top=-1;
int stack[length];

void main()
{
 int ch;
 do{
 cout << endl << "1: push";
 cout << endl << "2: pop";
 cout << endl << "3: exit";
 cout << endl << "enter choice";
 cin >> ch;
 switch(ch)
	{
	case 1:
		push();
		listStack();
		break;
	case 2:
		cout << "data poped= " << pop();
		listStack();
		break;
	case 3:exit(0);
	}

} while(1);

getch();
}

void push(int data)
{
	if(top+1==length)
	{
	   cout << "stack overflow\n Cannot enter new data";
		return;
	}
	top++;
	stack[top]=data;
}

int pop()
{
	int tempVar;
	if(top==-1)//we can also make isEmpty()
	{
	   cout << "stack is underflow (Empty)";
	    return(-1);
	}
	tempVar = stack[top];
	top--;
	return tempVar;
}

void listStack()
{
	cout << endl << "The stack is" << endl ;
	for(int i=top;i>=0;i--)
	   cout << stack[i] << endl;
}

Stacks in Problem Solving

—Consider a mathematical expression that includes several sets of nested parenthesis, e.g

    ( x + (y – (a +b)) )

—We want to ensure that parenthesis are nested correctly and the expression is valid.

—Validation

  1. There is an equal number of right and left parentheses
  2. Every right parenthesis is preceded by a matching left parenthesis

Expressions

—(A+B) * C  Valid
—A + B)  Invalid
(A+B]  Invalid

Rules

  • —Each left parentheses is the opening scope
  • —Each right parenthesis is a closing scope

—Parentheses count = 0 at the end means that no scopes have been left open and left and right parentheses exactly match. —The parentheses count at any time should never become negative. IF negative then it means expression is invalid.

Applications of Stacks in Data Structure

Click here to see applications of stack data structure in real life.


Tagged with: C/C++ languageData structures
 

3 Responses to Implementing Stack Data Structure in C++

  1. M.Usman says:

    Thanks alot ! it is very helpful

  2. s.ranade says:

    it was quite helpful

  3. Asim ch says:

    its very helpfull… but here my compiler gives error you cannot use this as function >> stack[top]=data;…?? any idea

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.