Stack

What is stack?

“Stack is a collection of elements arranged in a linear order.”

Stack Example

Consider the stack of books, where we can add or remove the book from the top. Now, if we want to remove the 5^th green book in the Image 1, we must have to remove top 4 books to really rank the green book as top of the stack. In the given scenario, someone can remove the top book, which is cyan in colour.

This proves that the stack shows the LIFO(Last In First Out) behaviour.

Means, cyan book was the last book to be added in the stack, but in case of removal, it’ll be the 1^st book to be removed.

Important Interface methods of the Stack

Following are the important methods in stack.

Working of the stack with the help of Diagram

Given image shows the working of stack.

As the image shows that the “top” pointer is always pointing to the top of the stack. And “push()” adds the element to stack and fix “top” pointer to this newly added element.

Stack Implementation using Array

The stack can be implemented as array. The interface will remain same as “push” and “pop” methods. User doesn’t need to know about the internal implementation of stack whether it’s implemented using array or linked list.

Worst case

We face worst case when we delete or add the elements at the beginning of the array.

• Push(): We’ve to shift all the elements of array to the right.
• Pop(): We’ve to shift all the elements of array to the left.

Best case

We face best case when we delete or remove the elements at the end of array.

• Push(): We push elements at the end of array.
• Pop(): We pop element at the end of array.

NOTE: Before calling the push(x), the user should call isFull() method. And before calling pop(), the user should call isEmpty().

• isFull(): Returns false if the stack/array isn’t full and an elements can be inserted.
• isEmpty(): Returns True of the stack/array is empty.

Stack Methods using C++

pop() method

int pop() {
	return A[current--];
}

push() method

void push(int x) {
	A[++current] = x;
}

top() method

int top() {
	return A[current];
}

isEmpty() method

When the stack is created, the value of current will be -1. If the user calls the isEmpty() method before pushing any element, it will return true.

int isEmpty() {
	return (current == -1);
}

isFull() method

int isFull() {
	return (current == size - 1);
}

Final Example

class Stack {
	public:
	Stack() { size = 10; current = -1; }
	int pop() { return A[current--]; }
	void push(int x) { A[++current] = x; }
	int top() { return A[current]; }
	int isEmpty() { return (current == -1); }
	int isFull() { return (current == size - 1); }

	private:
	int object;
	int current;
	int size;
	int A[10];
}
int main() {
	Stack stack;
	// pushing 10 elements to the stack
	for (int i = 0; i < 12; i++) {
		if (!stack.isFull()) stack.push(i);
		else cout << "Stack is full, no more insertion!" << endl;
	}

	// pop the elements at the stack
	for (int i = 0; i < 12; i++) {
		if(!stack.isEmpty())
		cout<<"The popped element = "<<stack.pop();
		else 
		cout << "Stack is empty, can't pop"; 
	}
}

REFERENCE: CS301 Handouts (page 49 to 55)