# Implementing Stack Data Structure in C++

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

### 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] |

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**

- There is an equal number of right and left parentheses
- 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.

### Related Posts

- Queues in C++
- Applications of Stack in Data Structures
- Queue Implementation in C++
- Linked lists in C++
- Operations on Binary Search Trees (BST)
- Data Structures Tutorial using C++
- Introduction to Graph data structure
- Insertion Sort: A Graphical Explanation
- Circular Linked Lists
- Implementation of Priority Queue using Heap data structure in C++
- Introduction to Tree Data Structure
- Binary Trees and Binary Search Trees

### 3 Responses to *Implementing Stack Data Structure in C++*

### Leave a Reply Cancel reply

### Popular Posts (last 30 days)

- Circular Linked Lists 1300 view(s)
- Attendance Management Sys… 1065 view(s)
- Applications of Stack in … 1058 view(s)
- Graph Implementation in C… 904 view(s)
- Implementing Stack Data S… 775 view(s)
- Simple Currency Converter… 661 view(s)
- GRASP Design Patterns 501 view(s)
- Recursive Factorial funct… 490 view(s)
- Finding Minimum, Maximum … 364 view(s)
- Implementation of Priorit… 310 view(s)

### Related Links

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books

Thanks alot ! it is very helpful

it was quite helpful

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