Algorithms - Stack Data Structure

bogotobogo.com site search:

Stacks

Abstract Data Types (ADT)

Abstract Data Types (ADT) is a mathematically specified entity that defines a set of its instances through the following two elements:

a specific interface
a collection of signatures of operations that can be invoked on an instance.
a set of axioms(preconditions and postconditions) that define the semantics of the operations such as what the operations do to instances of the ADT, not not how.

In other words, an ADT is a data type (a set of values and a collection of operations on those values) that is accessed only through an interface.

The type of operations we're taking here are:

Constructors
Access functions
Manipulation procedures

Why should we talk about ADTs in Data Structure tutorial?
That's because:

They serve as specifications of requirements for the building blocks of solutions to algorithmic problems.
They provide a language to talk on a higher level of abstraction.
ADTs encapsulate data structure and algorithms that implement them.
Separate the issues of correctness and efficiency.

Pushdown Stacks

Of the data types that support insert and remove for collections of objects, the most important is called the pushdown stack.

A pushdown stack is an Abstract Data Types (ADT) that comprises two basic operations: insert (push) a new item, and remove (pop) the item that was most recently inserted. Items of this pushdown stack are removed according to a last-in, first-out (LIFO) discipline.

In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are typically those that have been in the list the longest.

I'll start to implement stack for integer data type using structure with array member. Then, it will be converted to generic implementation of stack.

Stack Implementation for Integer Data

Summary of this example.

C implementation.
Mimic the C++ stack using struct.
Reallocate memory using doubling strategy.
Data type of the stack is integer.
Methods are:
Constructor - void createStack(Stack *)
Destructor - void deleteStack(Stack *)
pushStack(Stack *, int)
int popStack(Stack *)
void printStack(Stack *)

#include <iostream>
#include <memory>
#include <cassert>

using namespace std;

typedef struct 
{
	int *elems;
	int logLength;
	int allocLength;
} Stack;

void createStack(Stack *s) 
{
	s->logLength = 0;
	s->allocLength = 4;
	s->elems = (int *)malloc(4 * sizeof(int));
	assert(s->elems != NULL);
}

void deleteStack(Stack *s) 
{
	free(s->elems);
	s->logLength = 0;
	/* free(s) - Don't do this. 
	  The structure is not dynamically allocated */
}

void pushStack(Stack *s, int value) 
{
	if(s->logLength == s->allocLength) {
		/* doubling stratege */
		s->allocLength *= 2;
		s->elems = (int *)realloc(s->elems,s->allocLength * sizeof(int));
		assert(s->elems != NULL);
	}

	s->elems[s->logLength] = value;
	s->logLength++;
}

int popStack(Stack *s) 
{
	assert(s->logLength > 0);
	s->logLength--;
	return s->elems[s->logLength];
}

void printStack(Stack *s) 
{
	for(int i = 0; i < s->logLength; i++) {
		cout << s->elems[i] << " ";
	}
	cout << endl;
	return;
}

int main()
{
	Stack s;
	createStack(&s;);
	for(int i = 0; i < 10; i++) {
		pushStack(&s;,i);
	}
	printStack(&s;);
	cout << "Pop: " << popStack(&s;) << endl;
	printStack(&s;);
	cout << "Pop: " << popStack(&s;) << endl;
	printStack(&s;);

	cout << "Stack disposed" << endl;
	deleteStack(&s;);
	printStack(&s;);
}

Output from the run is:

0 1 2 3 4 5 6 7 8 9
Pop: 9
0 1 2 3 4 5 6 7 8
Pop: 8
0 1 2 3 4 5 6 7
Stack disposed

Generic Stack Implementation

Summary of this example.

Generic stack implementation using void*.
Data type of the stack is integer.
Methods are:
void createStack(Stack *, int)
void deleteStack(Stack *)
void pushStack(Stack *, void *)
void popStack(Stack *, void *)
void printStack(Stack *)
static void increaseStack(Stack *)

#include <iostream>
#include <memory>
#include <cassert>
#include <cmath>

using namespace std;

#define MYTYPE float

typedef struct {
	void *elems;
	int elemSize;
	int logLength;
	int allocLength;
} Stack;

void createStack(Stack *s, int elemSize) 
{
	s->elemSize = elemSize;
	s->logLength = 0;
	s->allocLength = 4;
	s->elems = (int *)malloc(4 * elemSize);
	assert(s->elems != NULL);
}

void deleteStack(Stack *s) 
{
	free(s->elems);
	s->logLength = 0;
	/* free(s) - Don't do this. 
	  The structure is not dynamically allocated */
}

/* make it local or internal */
static void increaseStack(Stack *s)
{
	s->allocLength *= 2;
	s->elems = realloc(s->elems, s->allocLength * s->elemSize);
}

void pushStack(Stack *s, void *elemAddr) 
{
	if(s->logLength == s->allocLength) 
	increaseStack(s);
	void *target = (char *)s->elems +
				s->logLength * s->elemSize;
	memcpy(target, elemAddr, s->elemSize);
	s->logLength++;
}

void popStack(Stack *s, void *elemAddr) 
{
	void *source =
		(char *)s->elems +
			(s->logLength-1) * s->elemSize;
	memcpy(elemAddr, source, s->elemSize);
	s->logLength--;
}

void printStack(Stack *s) 
{
	for(int i = 0; i < s->logLength; i++) {
		cout << *( (MYTYPE*)((char *)s->elems + i * s->elemSize) )<< " ";
	}
	cout << endl;
	return;
}

int main()
{
	Stack s;
	createStack(&s;, sizeof(MYTYPE));
	for(int i = 1; i <= 10; i++) {
		MYTYPE f = sqrt(float(i));
		pushStack(&s;,&f;);
	}
	void *vp = (MYTYPE *)malloc(sizeof(MYTYPE));
	printStack(&s;);
	popStack(&s;, vp);
	cout << "Pop: " << *((MYTYPE *)vp) << endl;
	printStack(&s;);
	popStack(&s;, vp);
	cout << "Pop: " << *((MYTYPE *)vp) << endl;
	printStack(&s;);

	cout << "Stack disposed" << endl;
	deleteStack(&s;);
	printStack(&s;);

	free(vp);
}

Output from the run is:

1 1.41421 1.73205 2 2.23607 2.44949 2.64575 2.82843 3 3.16228
Pop: 3.16228
1 1.41421 1.73205 2 2.23607 2.44949 2.64575 2.82843 3
Pop: 3
1 1.41421 1.73205 2 2.23607 2.44949 2.64575 2.82843
Stack disposed

Generic Stack Implementation with Array of Strings

Summary of this example.

Generic stack implementation using void*.
Handles array of strings.
Methods are:
void createStack(Stack *, int, void(*freefn)(void *))
void deleteStack(Stack *)
void pushStack(Stack *, void *)
void popStack(Stack *, void *)
void freeString(void *)
static void increaseStack(Stack *)

#include <iostream>
#include <memory>
#include <cassert>

using namespace std;

#define MYTYPE float

typedef struct {
	void *elems;
	int elemSize;
	int logLength;
	int allocLength;
	void (*freefn)(void *);
} Stack;

void freeString(void *elem)
{
	free(*(char **)elem);
}

void createStack(Stack *s, int elemSize, void(*freefn)(void *)) 
{
	s->elemSize = elemSize;
	s->logLength = 0;
	s->allocLength = 4;
	s->elems = (int *)malloc(4 * elemSize);
	assert(s->elems != NULL);
}

void deleteStack(Stack *s) 
{
	if(s->freefn != NULL) {
		for(int i = 0; i < s->logLength; i++){
			s->freefn((char *)s->elems +
				i * s->elemSize);
		}
	}

	free(s->elems);
	s->logLength = 0;
}

/* make it local or internal */
static void increaseStack(Stack *s)
{
	s->allocLength *= 2;
	s->elems = realloc (s->elems, s->allocLength * s->elemSize);
}

void pushStack(Stack *s, void *elemAddr) 
{
	if(s->logLength == s->allocLength) 
	increaseStack(s);
	void *target = (char *)s->elems +
				s->logLength * s->elemSize;
	memcpy(target, elemAddr, s->elemSize);
	s->logLength++;
}

void popStack(Stack *s, void *elemAddr) 
{
	void *source =
		(char *)s->elems +
			(s->logLength-1) * s->elemSize;
	memcpy(elemAddr, source, s->elemSize);
	s->logLength--;
}

int main()
{
	const char *friends[] = {"Al", "Bob", "Carl"};
	Stack stringStack;
	createStack(&stringStack;, sizeof(char *), freeString);

	for(int i = 0; i < 3; i++) {
		char *cpy = strdup(friends[i]);
		pushStack(&stringStack;, &cpy;);
	}

	char *name;
	for(int i = 0; i < 3 ; i++) {
		popStack(&stringStack;, &name;);
		cout << name << endl;
		free(name);  // mem allocated by strdup()
	}
	deleteStack(&stringStack;);
}

Output is:

Carl
Bob
Al

Stack Class - Implementation with Array

#include <iostream>
using namespace std;

class Stack
{
public:
	Stack();
	~Stack();
        explicit Stack(int);
	void push(int);
	int pop();
	bool isEmpty();
	void print();
private:
	int top;  // kind of a stack pointer: 1 up from the current top array index
	int *stackArray;
};

Stack::Stack()
{
	top = 0;
	stackArray = 0;
}

Stack::Stack(int sz)
{
	stackArray = new int[sz];
	top = 0;
}

Stack::~Stack()
{
	delete[] stackArray;
}

void Stack::push(int n)
{
	stackArray[top++] = n;
}

int Stack::pop()
{
	return stackArray[--top];
}

bool Stack::isEmpty()
{
	if(top == 0) return true;
	return false;
}

void Stack::print()
{
	int n = top;
	while(n)
		cout << stackArray[--n] << " ";
	    
	cout << endl;
}

int main()
{
	Stack *st = new Stack(10);
	st->push(10);
	st->push(20);
	st->push(30);
	st->push(40);
	st->push(50);
	st->print();
	st->pop();st->print();
	st->pop();st->print();
	st->pop();st->print();
	cout << "empty:" << st->isEmpty() << endl;
	st->pop();st->print();
	st->pop();st->print();
	cout << "empty:" << st->isEmpty() << endl;
	return 0;
}

Output:

50 40 30 20 10
40 30 20 10
30 20 10
20 10
empty:0
10

empty:1

Generic Stack Class - Implementation with Array

#include <iostream>
using namespace std;

template <class T>
class stack
{
private:
	T *stackArray;
	int top;

public:
	stack(int max)
	{
		stackArray = new T[max];
		top = 0;
	}

	void push(T data)
	{
		stackArray[top++] = data;
	}

	T pop()
	{
		return stackArray[--top];
	}

	int empty() const
	{
		return top = 0;
	}
};
		
int main()
{
	int i;
	stack<int> intStack(10);
	for(i = 0; i < 10; i++) {
		intStack.push(i);
	}
	for(i = 0; i < 10; i++) {
		cout << intStack.pop() << ' ';
	}
	cout << endl;

	stack<char> charStack(10);
	charStack.push('O');
	charStack.push('L');
	charStack.push('I');
	charStack.push('F');
	for(i = 0; i < 4; i++) {
		cout << charStack.pop() << ' ';
	}

	return 0;
}

Output is:

9 8 7 6 5 4 3 2 1 0
F I L O

Retrieving the Minimum Element in Constant Time - Linked List Implementation

This sample code is to design a stack, which does push, pop, and also, retrieve the minimum element in constant time (O(1))

The code has a Stack class and it has two pointers to the stacks with linked list implementation. One for regular stack (top) and the other (topMin) for book keeping of minimum values of the regular stack. So, whenever changes made to the regular stack, the minimum stack adjusts to those changes.

The function getMinValue() just returns the value pointed by topMin which is the top of the minimum value stack:

#include <iostream>

using namespace std;

typedef struct Element {
		int data;
		Element* next;
}Element;

class Stack 
{
private:
	Element *top;      // Pointer to the top of regular stack
	Element *topMin;   // Pointer to the top minimum value stack

public:
	Stack();
	~Stack();
	void push(int);
	int pop();
	int getMinValue();
	void print();
};

Stack::Stack()
{
	top = NULL;
	topMin = NULL;
}

Stack::~Stack()
{
	Element* elm;
	while(top) {
		elm = top->next;
		delete top;
		top = elm;
	}
	while(topMin) {
		elm = topMin->next;
		delete topMin;
		topMin = elm;
	}
}

void Stack::push(int n)
{
	Element *elm = new Element;
	elm->data = n;
	elm->next = top;
	top = elm;

	if(topMin == NULL) {
		elm = new Element;
		elm->data = n;
		elm->next = topMin;
		topMin = elm;
		return;
	}

	if(top->data < topMin->data) {
		elm = new Element;
		elm->data = n;
		elm->next = topMin;
		topMin = elm;
	}
	return;
}

int Stack::pop()
{
	int value;
	Element *elm = top;
	Element *elmMin = topMin;

	if(top == NULL) return NULL;
	elm = top;
	value = elm->data;
	top = elm->next;
	delete elm;

	if(value == topMin->data) {
		elmMin = topMin;
		topMin = elmMin->next;
		delete elmMin;
	}

	return value;
}

int Stack::getMinValue()
{
	if(top) return topMin->data;
	return -1; 
}

void Stack::print()
{
	Element *elm;

	elm = top;
	cout << "Regular stack: ";
	while(elm) {
		cout << elm->data << ' ';
		elm = elm->next;
	}
	cout << endl;

	elm = topMin;
	cout << "Minimum stack: ";
	while(elm) {
		cout << elm->data << ' ';
		elm = elm->next;
	}
	cout << endl;
	return;
}

int main()
{
	Stack *st = new Stack;

	st->push(80);
	st->push(70);
	st->push(60);
	st->push(100);
	st->push(40);
	st->push(50);
	st->push(90);
	st->push(10);
	st->push(20);
	st->push(30);

	st->print();
	cout << "Min Value = " << st->getMinValue() << endl << endl;

	for(int i = 0; i < 10; i++) {
		cout << "Popped: " << st->pop() << endl;
		st->print();
		cout << "Min Value = " << st->getMinValue() << endl << endl;
	}

	delete st;

	return 0;
}

Output from the run is:

Regular stack: 30 20 10 90 50 40 100 60 70 80
Minimum stack: 10 40 60 70 80
Min Value = 10

Popped: 30
Regular stack: 20 10 90 50 40 100 60 70 80
Minimum stack: 10 40 60 70 80
Min Value = 10

Popped: 20
Regular stack: 10 90 50 40 100 60 70 80
Minimum stack: 10 40 60 70 80
Min Value = 10

Popped: 10
Regular stack: 90 50 40 100 60 70 80
Minimum stack: 40 60 70 80
Min Value = 40

Popped: 90
Regular stack: 50 40 100 60 70 80
Minimum stack: 40 60 70 80
Min Value = 40

Popped: 50
Regular stack: 40 100 60 70 80
Minimum stack: 40 60 70 80
Min Value = 40

Popped: 40
Regular stack: 100 60 70 80
Minimum stack: 60 70 80
Min Value = 60

Popped: 100
Regular stack: 60 70 80
Minimum stack: 60 70 80
Min Value = 60

Popped: 60
Regular stack: 70 80
Minimum stack: 70 80
Min Value = 70

Popped: 70
Regular stack: 80
Minimum stack: 80
Min Value = 80

Popped: 80
Regular stack:
Minimum stack:
Min Value = -1

Retrieving the Minimum Element in Constant Time - Array Implementation

#include <iostream>
using namespace std;

template <class T>
class stack
{
private:
	T *stackArray;
	T *stackArrayMin;
	int top, topMin;

public:
	stack() {}

	stack(int max)
	{
		stackArray = new T[max];
		stackArrayMin = new T[max];
		top = 0;
		topMin = 0;
	}

	void push(T data)
	{
		if(top == 0 ) {
			stackArray[top++] = data;
			stackArrayMin[topMin++] = data;
			return;
		}
		if(data < stackArrayMin[topMin-1])
			stackArrayMin[topMin++] = data;
		stackArray[top++] = data;
	}

	T pop()
	{
		if(stackArray[top-1] == stackArrayMin[topMin-1]) topMin--;
		return stackArray[--top];
	}

	T getArrayMinimum() 
	{
		return stackArrayMin[topMin-1];
	}

	T empty() const
	{
		return top = 0;
		return topMin = 0;
	}

	void print()
	{
		cout << "stackArray: ";
		for(int i = 0; i < top; i++) {
			cout << stackArray[i] << ' ';
		}
		cout << endl;
		cout << "stackArrayMin: ";
		for(int i = 0; i < topMin; i++) {
			cout << stackArrayMin[i] << ' ';
		}
		cout << endl;
	}
};
		
int main()
{
	const int Max = 10;
	stack<int> intStack(Max);
	intStack.push(50);
	intStack.push(60);
	intStack.push(40);
	intStack.push(70);
	intStack.push(30);
	intStack.push(80);
	intStack.push(20);
	intStack.push(90);
	intStack.push(0);
	intStack.push(10);

	intStack.print();
	cout << "Minimum: " << intStack.getArrayMinimum() << endl << endl;

	for(int i = 0; i < Max - 1; i++) {
		cout << "pop: " << intStack.pop() << endl;
		intStack.print();
		cout << "Minimum: " << intStack.getArrayMinimum() << endl << endl;
	}

	return 0;
}

Output is:

stackArray: 50 60 40 70 30 80 20 90 0 10
stackArrayMin: 50 40 30 20 0
Minimum: 0

pop: 10
stackArray: 50 60 40 70 30 80 20 90 0
stackArrayMin: 50 40 30 20 0
Minimum: 0

pop: 0
stackArray: 50 60 40 70 30 80 20 90
stackArrayMin: 50 40 30 20
Minimum: 20

pop: 90
stackArray: 50 60 40 70 30 80 20
stackArrayMin: 50 40 30 20
Minimum: 20

pop: 20
stackArray: 50 60 40 70 30 80
stackArrayMin: 50 40 30
Minimum: 30

pop: 80
stackArray: 50 60 40 70 30
stackArrayMin: 50 40 30
Minimum: 30

pop: 30
stackArray: 50 60 40 70
stackArrayMin: 50 40
Minimum: 40

pop: 70
stackArray: 50 60 40
stackArrayMin: 50 40
Minimum: 40

pop: 40
stackArray: 50 60
stackArrayMin: 50
Minimum: 50

pop: 60
stackArray: 50
stackArrayMin: 50
Minimum: 50

For additional linked list based stack implementation, go to