Stacks

View Code

A stack is a simple container that follows LIFO for adding or removing data. The Last one In is the First on Out. It works just like a stack of plates. When a plate is added it goes on the top. When one taken taken off it also comes off the top. Elements are said to be pushed on and popped off.

stack: a container that follows a LIFO rule for adding and removing elements
LIFO: Last In First Out
top: the end of the stack that recieves and removes data
push: adding an element to the top of the stack
pop: removing an element from the top of the stack

A stack can implement all the container functions escept add(), remove(), and get(). These are replaced respectively with push(), pop(), and top() (which returns the top element). Sometimes top() is called peek() or get(). Sometimes it isn't even there. pop() would be used instead and defined so that it would remove and return the element. However if all the programmer wants to look at is the top, popping and imediate pushing back the value becomes redundant.

Now how to implement the stack. It could be done with an array but a Linked List is more appropriate. It can increase and decrease in size as need. Also ince only the top is concerned, there are no long searches from the head. All that is needed for the stack is manipulation of the head Node.


class Stack
{
   public:
      Stack() : head(NULL), size(0) {}
      Stack(const Stack& s);
			~Stack();
			
      void push(int);
      void pop();
      void clear();
      
			int top();
      bool empty();
      int size();
			
      Stack& operator=(const Stack& s);

   private:
      Node* head;   //direct manipulation of the Nodes are required
      int size;     //so a Node rather than a LinkList is used			
};

With the preexisting function implementation shouldn't be too hard. Here is an evaluation of the functions.

Function Evaluation Order
Stack() Two simple data member declarations O(1)
Stack(Stack) Same as the assigment operator O(n)
~Stack() Simple deletion traversal O(n)
push() Simple Node creation and pointer manipulation O(1)
pop() Simple Node deletion O(1)
clear() Linear deletetion. O(n)
top() Simple return O(1)
empty() Simple return. O(1)
size() Simple return. O(1)
= Same as listCopy() O(n)

Function	Evaluation	Order
Stack()	Two simple data member declarations	O(1)
Stack(Stack)	Same as the assigment operator	O(n)
~Stack()	Simple deletion traversal	O(n)
push()	Simple Node creation and pointer manipulation	O(1)
pop()	Simple Node deletion	O(1)
clear()	Linear deletetion.	O(n)
top()	Simple return	O(1)
empty()	Simple return.	O(1)
size()	Simple return.	O(1)
=	Same as listCopy()	O(n)

Prev -- Back to Portal -- Next