1. Definition
Ordered list in which all insertions and deletions are made at one end, called the top.E.g. If the elements A,B,C,D and E are inserted into the stack in the same order, then the first element that can be removed is E.Since, the last element to be inserted is the first element to be deleted, the stack is also called as Last In, First Out (LIFO) Order.Similarly, since the first element to be inserted is the last element to be deleted, the stack is also called as First In, Last Out (FILO) Order.2. Implementation of the Stack:
There are two main ways to implement Stacks:- Using One-dimensional Array.
- Using Linked List.
2.1 Using One-dimensional Array.
| Variables: | |
| top | points to the top element in the stack. |
| capacity | maximum number of elements that can be stored in the stack. |
| stack[0 : capacity-1] | Stack representation as one dimensional array |
Conditions: | |
| if( top< 0 ) | Indicates that the stack is empty. |
| stack[top] | topmost element of the stack. |
| if (top >= n-1) | Tests whether the stack is full. |
Operations:Two fundamental operations : | |
| Insertion | Adds an item to the stack. |
| Deletion | Removes / Deletes an item from the stack |
Remarks: Each operation of Insertion or Deletion takes a constant time and is independent of the number of elements in the stack, O(1).
2.1.1 Representation of the stack:
2.1.2 Algorithm:
Algorithm Add(item)
// Push an element into the stack.
// Return true if successfull; else return false.
// Input: item
{
if( top >= n-1 ) then
{
write("Stack is full!"); return false;
}
else
{
top := top + 1;
stack[top] := item;
return true;
}
}
Algorithm Delete(item)
// Pop the top element from the stack.
// Return true if successfull; else return false.
// Output: item
{
if( top < 0 ) then
{
write("Stack is empty!"); return false;
}
else
{
item := stack[top];
top := top-1;
return true;
}
}
2.1.3 Codes:
Let us look at C++ implementation of Stacks. We will look at following:
- Stacks provided as default STL (Standard template Library).
- Stack Implementation as one-dimensional Integer array.
- Extending our Integer stack to a more generalized form using templates.
2.1.3.1 C++ STL Stacks.
More information can be found in the reference: C++ STL stack reference .Let us look at a simple example as demonstration of its use.
#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> myStack1, myStack2;
myStack1.push(40);
myStack1.push(30);
myStack1.push(20);
myStack1.push(10);
myStack2.push(100);
myStack2.push(90);
myStack2.push(80);
myStack2.push(70);
myStack1.swap(myStack2); // Swap myStack1 and myStack2
while(false == myStack1.empty())
{
cout << "Top most element of the stack: " << myStack1.top() << endl;
cout << "Stack Size: " << myStack1.size() << endl << endl;
myStack1.pop();
}
return EXIT_SUCCESS;
}
2.1.3.2 C++ Program for one Dimensional array representation of Integer Stack
Simple representation of stack in C++, where the elements to be put into stack are Integers. This representation can be easily be extended to be more generalized representation using templates. We will see that next
// Example program: Stack items to be inserted or deleted are Integers
#include <iostream>
#include <climits>
using namespace std;
class Stack
{
// Variables:
int top;
unsigned capacity;
int* array;
// Conditions:
bool IsFull(void);
bool IsEmpty(void);
public:
Stack(unsigned capacity); // Constructor to create a stack of given capacity
~Stack(void); // Destructor
// Operations:
void Push(int item); // Add item to the stack. It increases the top by 1
int Pop(void); // Remove an item from the stack. Decreases the top by 1
int Peek(void); // Check the top item from the stack
};
// Implementation of the class
// Create Stack of the given capacity
Stack::Stack(unsigned capacity)
{
this->capacity = capacity;
this->top = -1;
array = new int[capacity];
}
Stack::~Stack(void)
{
delete[] array;
array = nullptr;
}
bool Stack::IsFull(void)
{
if(top == static_cast<int>(capacity - 1))
{
return true;
}
return false;
}
bool Stack::IsEmpty(void)
{
if(-1 == top)
{
return true;
}
return false;
}
void Stack::Push(int item)
{
if(true == IsFull())
{
return;
}
array[++top] = item;
}
int Stack::Pop(void)
{
if(true == IsEmpty())
{
return INT_MIN;
}
return array[top--];
}
int Stack::Peek(void)
{
if(true == IsEmpty())
{
return INT_MIN;
}
return array[top];
}
// Test Program
int main()
{
Stack stack(100);
stack.Push(10);
stack.Push(20);
stack.Push(30);
cout << "Popping from the stack: "<< stack.Pop() << endl;
cout << "Top most element of the stack: " << stack.Peek() << endl;
return EXIT_SUCCESS;
}
2.1.3.3 C++ Program for Implementation of stacks using templates
This implementation uses templates to facilitate Generic Programming. We extend implementation given in 2.1.3.2 to now implement stack using templates. This implementation allows to implement stack operations on any data. Some modifications / enhancements have been made to the Integer stack :
- Modifying the function: Peek(). This function can now be used to return an element at 'depth' levels from the top.
- Done away with separate functions like IsEmpty and IsFull. Instead we use the macros provided by assert.h header file for error-checking conditions.
- The code is now more C++ class stylized, with inline and const and reference variables included.
But of course there are scope of improvement on the code. One example would be to provide copy constructors. Let's use them during the linked list implementation of stack in the next blog.
// Example program: Generic Stack implemented using Templates
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;
template <class Elem>
class Stack
{
protected:
Elem *dataArray; // The actual Data Array
int top; // The current number of elements in the array.
const int MAX_NUM; // Maximum number of elements
public:
Stack(unsigned capacity=500);
~Stack(void);
// Operations
inline void Push(const Elem &item); // Adds an item to the top
inline Elem Pop(void); // Returns item from the top
inline const Elem &Peek(int depth) const; // Peek an item at 'depth' downwards.
};
// Implementation of Stack class
// Stack Constructor - Create Stack of the given capacity
template<class Elem>
Stack<Elem>::Stack(unsigned capacity):
MAX_NUM(capacity) // Initialize the constant
{
dataArray = new Elem[MAX_NUM];
top = 0;
}
// Stack Destructor
template<class Elem>
Stack<Elem>::~Stack(void)
{
delete[] dataArray;
}
// Push() Function
template <class Elem>
inline void Stack<Elem>::Push(const Elem &item)
{
// Error Check: Make sure we dont exceed the maximum storage space
assert(top < MAX_NUM);
dataArray[top++] = item;
}
// Pop() Function
template <class Elem>
inline Elem Stack<Elem>::Pop(void)
{
// Error check: Make sure we aren't popping from an empty stack
assert(top > 0);
return dataArray[--top];
}
// Peek Function
template <class Elem>
inline const Elem &Stack<Elem>::Peek(int depth) const
{
// Error Check: Make sure the depth doesn't exceed the number of elements
assert(depth < top);
return dataArray[top - (depth+1)];
}
int main()
{
Stack<int> stack_int(100);
stack_int.Push(10);
stack_int.Push(20);
stack_int.Push(30);
cout << "Popping from the stack: " << stack_int.Pop() << endl;
cout << "Top most element of the stack: " << stack_int.Peek(0) << endl;
Stack<string> stack_str(100);
stack_str.Push("abc");
stack_str.Push("def");
stack_str.Push("ghi");
cout << "Popping from the stack: " << stack_str.Pop() << endl;
cout << "Top most element of the stack: " << stack_str.Peek(1) << endl;
return EXIT_SUCCESS;
}
Output:
Popping from the stack: 30
Top most element of the stack: 20
Popping from the stack: ghi
Top most element of the stack: abc
No comments:
Post a Comment