StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Friday, July 11, 2008

C++ Stacks

 July 11, 2008     Data Structures     No comments   

Stack Introduction

This article explains about basics of the stack data structure and demonstrates implementation of stack using arrays and linked lists.
  • Stack is a last-in, first-out (LIFO) data structure. i.e. the element added last to the stack will be the one to be removed first.
  • Typical use cases of stacks include:- (1) During debugging it is quite common to examine the function call stack during panics. (2) In RTOS like Symbian there are concepts like cleanup stack to avoid memory leaks.
  • Some of the common terminology associated with stacks include PUSH, POP and TOP of the stack.
  • PUSH refers to adding an element to the stack.
  • POP refers to removing an element from the stack.
  • TOP refers to the first element that could be POPed (or) the last element PUSHed.
  • Diagram below explains the stack.

Implementation of a simple stack using arrays

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;

class StackOverFlowException 
{
    public:
        StackOverFlowException() 
        {
            cout << "Stack overflow" << endl;
        }
};

class StackUnderFlowException 
{
    public:
        StackUnderFlowException() 
        {
            cout << "Stack underflow" << endl;
        }
};

class ArrayStack 
{    
    private:        
        int data[MAX_SIZE];        
        int top;    
  public:        
      ArrayStack() 
      {            
          top = -1;        
    }        
    
    void Push(int element)
    {            
        if ( top >= MAX_SIZE ) 
            {            
                throw new StackOverFlowException();
            }                   
            data[++top] = element;        
    }        
            
    int Pop()
    {            
        if ( top == -1 ) 
            {            
                throw new StackUnderFlowException();            
            }            
            return data[top--];        
    }        
    
    int Top() 
    {            
        return data[top];        
    }
    
    int Size() 
    {
        return top + 1;
    }
    
    bool isEmpty() 
    {
        return ( top == -1 ) ? true : false;
    }
};

int main()
{    
    ArrayStack s; 
    try {
        if ( s.isEmpty() ) 
            {
            cout << "Stack is empty" << endl;    
            }
        // Push elements    
        s.Push(100);    
        s.Push(200);    
        // Size of stack
        cout << "Size of stack = " << s.Size() << endl;
        // Top element    
        cout << s.Top() << endl;    
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:-
Stack is empty
Size of stack = 2
200
200
100
Stack underflow
Some exception occured

Implementation of a simple stack using linked lists

#include <iostream>
using namespace std;

class StackUnderFlowException 
{
    public:
        StackUnderFlowException() 
        {
            cout << "Stack underflow" << endl;
        }
};

struct Node 
{
    int data;
    Node* link;
};

class ListStack 
{
    private:                 
        Node* top;
        int count;
            
  public:        
      ListStack() 
      {            
          top = NULL;
          count = 0;        
    }        
    
    void Push(int element)
    { 
        Node* temp = new Node();
        temp->data = element;
        temp->link = top;
        top = temp;     
        count++;          
    }        
            
    int Pop()
    {            
        if ( top == NULL ) 
            {            
                throw new StackUnderFlowException();            
            }        
            int ret = top->data;    
            Node* temp = top->link;
            delete top;
            top = temp;
            count--;
            return ret;        
    }        
    
    int Top() 
    {            
        return top->data;        
    }
    
    int Size() 
    {
        return count;
    }
    
    bool isEmpty() 
    {
        return ( top == NULL ) ? true : false;
    }
};

int main()
{    
    ListStack s; 
    try {
        if ( s.isEmpty() ) 
        {
            cout << "Stack is empty" << endl;    
        }
        // Push elements    
        s.Push(100);    
        s.Push(200);    
        // Size of stack
        cout << "Size of stack = " << s.Size() << endl;
        // Top element    
        cout << s.Top() << endl;    
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
        // Pop element    
        cout << s.Pop() << endl;
    }
    catch (...) {
        cout << "Some exception occured" << endl;
    }
}

OUTPUT:-
Stack is empty
Size of stack = 2
200
200
100
Stack underflow
Some exception occured
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk